已知一个非零整数序列,请提出一种较优的算法将所有正数调整到序列的左边,所有负数调整到序列的右边,并完成以下三个问题: (1)写出这算法思路的操作步骤。 (2)用C语言实现(1)中的算法,自行设计函数名和参数。 (3)分析算法的时间复杂度。 数据结构主观题
时间: 2024-03-25 22:39:18 浏览: 64
关于数据结构的算法
算法思路操作步骤如下:
1. 定义两个指针,一个指向序列的开头,一个指向序列的结尾。
2. 从序列的开头开始,向结尾遍历序列。
3. 如果当前元素为正数,则将其与开头指针指向的元素进行交换,并将开头指针向后移动一位。
4. 如果当前元素为负数,则将其与结尾指针指向的元素进行交换,并将结尾指针向前移动一位。
5. 重复步骤2-4,直到两个指针相遇。
C语言实现代码如下:
```c
void adjustSequence(int* seq, int len) {
int left = 0, right = len - 1;
while (left < right) {
if (seq[left] > 0) {
left++;
} else if (seq[right] < 0) {
right--;
} else {
int temp = seq[left];
seq[left] = seq[right];
seq[right] = temp;
left++;
right--;
}
}
}
```
时间复杂度分析:
该算法只需要一次遍历序列,因此时间复杂度为O(n)。
阅读全文