8.3 数组划分与查找
8.3.1 奇偶元素重排
问题描述 已知线性表按顺序存储，且每个元素都是不相同的整数型元素。设计一个算法把所有奇数移动到所有偶数前边，要求时间最短，辅助空间最小。
思路分析 可以采用类似快速排序的划分思想。只需遍历一次即可，时间复杂度为 O(n)，空间复杂度为 O(1)。 假设表为 L[1..n]，基本思想是：先从前往后找到一个偶数元素 L[i]，再从后往前找到一个奇数元素 L[j]，将二者交换；重复上述过程直到 i 大于 j。
核心代码实现
void move(ElemType A[], int len) {
// 对表 A 按奇偶进行一趟划分
int i = 0, j = len - 1;
// i 表示左端偶数元素的下标；j 表示右端奇数元素的下标
while (i < j) {
while (i < j && A[i] % 2 != 0) i++; // 从前往后找到一个偶数元素
while (i < j && A[j] % 2 != 0) j--; // 从后往前找到一个奇数元素
if (i < j) {
Swap(A[i], A[j]); // 交换这两个元素
i++;
j--;
}
}
}
8.3.2 寻找第 k 小元素
问题描述 试编写一个算法，使之能够在数组 L[1...n] 中找出第 k 小的元素（即从小到大排序后处于第 k 个位置的元素）。
思路分析 最直接的做法是用排序算法对数组先进行从小到大的排序，然后直接提取 L[k]，但其平均时间复杂度将达到 O(n log n) 以上。此外，还可采用小顶堆的方法，每次堆顶元素都是最小值元素，时间复杂度为 O(n + k log n)。 这里介绍一个更精彩的算法，它基于快速排序的划分操作。主要思想如下：从数组 L[1...n] 中选择枢轴 pivot（随机或直接取第一个）进行和快速排序一样的划分操作后，表 L[1..n] 被划分为 L[1..m-1] 和 L[m+1..n]，其中 L[m]=pivot。 讨论 m 与 k 的大小关系：
- 当 m=k 时，显然 pivot 就是所要寻找的元素，直接返回 pivot 即可。
- 当 m<k 时，所要寻找的元素一定落在 L[m+1..n] 中，因此可对 L[m+1..n] 递归地查找第 k-m 小的元素。
- 当 m>k 时，所要寻找的元素一定落在 L[1..m-1] 中，因此可对 L[1..m-1] 递归地查找第 k 小的元素。 该算法的时间复杂度在平均情况下可以达到 O(n)，而所占空间的复杂度则取决于划分的方法。
核心代码实现
int kth_elem(int a[], int low, high, k) {
pivot = a[low];
low_temp = low;
high_temp = high;
(low < high) {
(low < high && a[high] >= pivot) --high;
a[low] = a[high];
(low < high && a[low] <= pivot) ++low;
a[high] = a[low];
}
a[low] = pivot;
(low == k)
a[low];
(low > k)
(a, low_temp, low - , k);
(a, low + , high_temp, k);
}
