已知一个非零整数序列,请提出一种较优的算法将所有正数调整到序列的左边,所有负数调整到序列的右边,并完成以下三个问题: (1)写出这算法思路的操作步骤。 (2)用C语言实现(1)中的算法,自行设计函数名和参数。 (3)分析算法的时间复杂度
时间: 2024-03-26 22:35:13 浏览: 139
1. 算法思路的操作步骤:
- 定义两个指针,一个指向序列的开头,一个指向序列的结尾。
- 当前指针从序列开头开始扫描,如果指向的元素是正数,就将其与指向结尾的指针指向的元素交换位置,然后将指向结尾的指针向前移动一位。
- 如果指向的元素是负数,就将指向开头的指针指向的元素与其交换位置,然后将指向开头的指针向后移动一位。
- 反复执行上述操作,直到两个指针相遇,此时所有正数都在序列的左侧,所有负数都在序列的右侧。
2. C语言实现:
```c
void adjust_array(int arr[], int len) {
int *p = arr, *q = arr + len - 1; // 定义指针p和q,分别指向序列的开头和结尾
while (p < q) { // 当p和q没有相遇时
if (*p > 0) { // 如果p指向的元素是正数
if (*q < 0) { // 如果q指向的元素是负数
// 交换p和q指向的元素
int temp = *p;
*p = *q;
*q = temp;
} else { // 如果q指向的元素不是负数
q--; // 将q指针向前移动一位
}
} else { // 如果p指向的元素不是正数
p++; // 将p指针向后移动一位
}
}
}
```
3. 时间复杂度分析:
该算法只对每个元素进行了一次扫描,并且每次扫描最多只涉及一次交换操作,所以时间复杂度为O(n),其中n为序列的长度。
阅读全文