已知线性表(a1,a2…,an-1)按顺序存储于内存,每个元素都是整数,函数GetElem(L,i,&e)能用e返回L中第i个数据元素的值,试设计用最少时间把所有值为负数的元素移到全部正数值元素前面的算法。(C语言编程实现利用上述GetElem函数并说明理由)
时间: 2024-09-11 22:10:22 浏览: 53
为了实现这个算法,我们可以使用双指针法,分别维护一个指向正数序列的“正向指针”(positive_index)和一个指向当前遍历位置的“原地指针”(current_index)。当遇到正数时,我们不做改动;遇到负数时,将它与“原地指针”处的元素交换,并将“原地指针”向前移动一位。遍历结束后,“正向指针”的位置就是新数组的起始点,其后的元素都是正数。
以下是C语言的实现:
```c
#include <stdio.h>
void moveNegativesToFront(int* arr, int n) {
int positive_index = 0; // 正向指针
for (int current_index = 0; current_index < n; ++current_index) {
if (arr[current_index] >= 0) { // 遇到正数,不动
continue;
} else { // 遇到负数,交换并前进
int temp = arr[current_index];
arr[current_index] = arr[positive_index];
arr[positive_index++] = temp;
}
}
}
// 示例
int main() {
int arr[] = {5, -3, 8, -2, 1, -7};
int n = sizeof(arr) / sizeof(arr[0]);
moveNegativesToFront(arr, n);
printf("处理后的数组(正数在前): ");
for (int i = 0; i < n; ++i) {
printf("%d ", arr[i]);
}
return 0;
}
```
理由:这种算法的时间复杂度是O(n),因为它只需要遍历一次整个数组。空间复杂度是O(1),因为我们只用到了两个额外的变量(正向指针和临时变量),并没有使用与输入大小相关的额外空间。
阅读全文