我想对整数数组进行分区，以便负值位于正值的左侧，并且我想就地执行此操作（无需额外的辅助内存）。请注意，数组不能从小到低排序，只需将负数收集到左侧，将正数收集到右侧。
我创建了一个时间复杂度为 O(n^2) 的朴素函数，但想知道如何在线性时间内解决它？我的算法使用两个指针，开始指向数组的最左边和最右边的元素。当 ptr1 遇到正值，而 ptr2 遇到负值时，我们执行交换，指针向右/向左迭代，当它们相遇时，函数返回，因为数组已完成收集。
你能帮我想出一个更简单的算法来进行这种收集吗？
int* swaps(int* array){
int* ptr1;
ptr1 = &array[0];
int* ptr2;
ptr2 = &array[N-1];
int tmp;
for(ptr1; ptr1 <= &array[N-1]; ptr1++){
if(ptr1==ptr2){
return array;
}
if(*ptr1 >= 0){
for(ptr2; ptr2 >= &array[0]; ptr2--){
if(ptr1==ptr2){
return array;
}
// swap elements
if(*ptr2 < 0){
tmp = *ptr2;
*ptr2 = *ptr1;
*ptr1 = tmp;
ptr2--;
if(ptr1==ptr2){
return array;
}
break;
}
}
}
}
}
这是 KN King 所著《C 编程：现代方法》一书中的练习
“假设以下数组包含一周的每小时温度读数，每行包含一天的读数：
int temperatures[7][24];
编写一条语句，使用搜索函数在整个温度数组中搜索值 32。”
下面的代码包括之前练习中的搜索函数，以及我调用该函数的 main() 函数。搜索只是处理一个数组并检查是否有任何元素等于提供的参数“key”。该解决方案似乎编译并执行预期的输出，它打印“找到 32”，或者如果我注释掉分配则不打印任何内容temperatures[5][22] = 32;。
请注意该函数如何获取一维数组，但练习要求处理二维数组。
我最初尝试了这个解决方案，在函数调用中没有显式类型转换（int *），并在编译时得到了这个（我对其进行了一些重新格式化）：
1 编译器警告：“从不兼容的指针类型传递搜索参数 1”
1 注意：“预期为‘const int *’，但参数的类型为‘int * [24]’”
为什么会出现警告/注释？如果存在不兼容，为什么它们不是错误？类型转换为 int* 消除了任何编译问题，但该解决方案实际上是正确/安全的还是我对 C 的理解/实践不好？我知道该函数需要 int* 但二维数组会衰减为 int * [24] 类型的指针，而无需进行类型转换。然而，代码在任何一种情况下都有效，尽管我只有一个测试用例。我怎样才能修改我的解决方案逻辑来完全避免这个问题？不过，搜索功能应该保持不变。
#include <stdbool.h>
#include <stdio.h>
bool search(const int a[], int n, int key);
int main(void){
int temperatures[7][24] = {0};
temperatures[5][22] = 32;
bool has32 = search((int*)temperatures, 7 * 24, 32);
if(has32)
printf("32 was found");
return 0;
}
bool …