用C语言编程设计算法将顺序表所有正数排在所有负数前面(要求:时间复杂度为O(n))
时间: 2024-10-07 09:06:13 浏览: 29
用C语言举例讲解数据结构中的算法复杂度结与顺序表
在C语言中,你可以通过双指针法来实现这个功能,这种方法的时间复杂度确实可以达到O(n)。以下是简单的步骤:
1. 定义两个指针,一个叫`i`(初始化为0),用于遍历整个顺序表;另一个叫`j`(初始化为0),用于存储正数的位置。
2. 遍历顺序表:
- 如果当前元素`arr[i]`是正数,直接将其移动到正数部分,即`arr[j++] = arr[i++]`,然后继续检查下一个元素。
- 如果当前元素是负数,先记录下它的位置`i`,然后继续遍历。
3. 当`i`遍历完顺序表后,将剩余未处理的负数从它们保存的位置开始放到数组的剩余部分。
4. 将`arr[j:]`这部分(包含已排序的正数和未处理的负数)复制回原位置,即可完成正数在前、负数在后的排列。
下面是一个简单的伪代码示例:
```c
void separate_positive_negative(int* arr, int n) {
int j = 0;
for (int i = 0; i < n; ++i) {
if (arr[i] > 0) {
// 移动正数到已排序的部分
arr[j++] = arr[i];
} else {
// 记录负数的位置
while (arr[j] > 0 && j < i) {
++j;
}
}
}
// 复制已排序的正数部分到原数组
for (int k = 0; k < j; ++k) {
arr[k] = arr[j - k - 1];
}
}
```
阅读全文