"高效移动顺序表奇偶数算法实现及优化技巧"

给定一个顺序表L，其中存储着n个互不相等的整数。现在需要设计一个算法，将所有奇数移到所有偶数的前面，要求时间复杂度最小，且辅助空间最小。 算法思想是首先初始化两个指针i和j，分别指向表的第一个元素和最后一个元素。从左向右找到第一个偶数，从右向左找到第一个奇数，将两个元素进行交换。然后继续向后移动指针i和向前移动指针j，继续进行相同的操作，直到i>j为止。 具体实现代码如下： ```c++ #include <iostream> #include <vector> using namespace std; typedef struct { vector<int> data; int length; } SqList; void move(SqList &L) { int i = 0, j = L.length - 1; while (i < j) { // 从左向右找到第一个偶数 while (i < j && L.data[i] % 2 != 0) { i++; } // 从右向左找到第一个奇数 while (i < j && L.data[j] % 2 == 0) { j--; } // 交换两个元素 if (i < j) { int temp = L.data[i]; L.data[i] = L.data[j]; L.data[j] = temp; } } } int main() { SqList L; L.data = {1, 2, 3, 4, 5, 6, 7, 8, 9}; L.length = L.data.size(); move(L); for (int i = 0; i < L.length; i++) { cout << L.data[i] << " "; } return 0; } ``` 以上代码实现了将顺序表L中的所有奇数移动到所有偶数的前面，时间复杂度为O(n)，辅助空间为常数级别。通过这个算法，我们可以很高效地对顺序表进行操作，实现了移动元素的目的。如果需要对一个顺序表中的元素进行重新排列，可以考虑使用类似的双指针交换的方法，既快速又高效。