1、排序解决法
如果是一个有序数组，那么寻找第k的大数则相当简单了，且效率为1。数组排序算法中相对较优的算法为快速排序，效率为N*lgN，将数组从到到小排列，第k大的数则为array[k-1]。
快排的思想为，从数组中取任意一个值key，将大于key的值放在key右边，小于key的值放在key左边。key的左边和右边则都是有序的了，然后递归key左边的子数组和key右边的子数组，直到每个子数组长度为1，此时，整个数组均有序了。
public static int partition(int[] array, int left, int right) { int k = array[left]; int i = left; int j = right; while (j > i) { while (array[j] < k && j > i) { j--; } if (j > i) { array[i] = array[j]; i++; } while (array[i] > k && j > i) { i++; } if (j > i) { array[j] = array[i]; j--; } } array[i] = k; return i; } public static void quickSort(int[] array, int left, int right) { if (left >= right) { return; } int i = partition(array, left, right); quickSort(array, left, i - 1); quickSort(array, i + 1, right); }
本文中快排略有差异，是按从大到小顺序排列。
快排的partition算法有两种写法，具体可查看快速排序及主定理。此解法效率为N*lgN
2、类快排解法
由于只要求找出第k大的数，没必要将数组中所有值都排序。
快排中的partition算法，返回key在数组中的位置，如果key的位置正好等于k-1，那么问题则得到解决，如果key的位置不等于k-1，可使用递归查找对应子数组。直到key的位置等于k-1，则找对问题的解。
public static int findK(int[] array, int left, int right, int k) { int i = partition(array, left, right); if (i == k - 1) { return array[k - 1]; } else if (i > k - 1) { return findK(array, left, i - 1, k); } else if (i < k - 1) { return findK(array, i + 1, right, k); } return 0; }
此解法的效率值为N*lgK，由于K是常数，所以此解法效率值为N，优于排序解法
3、最小堆解法
最小堆是一种特殊的数组结构，它实质是一个完全二叉树，且树中子节点的值均大于父节点的值，详见 堆排序及优先队列。
考虑到只需要找到第k大的数，构造一个大小为k的最小堆，堆中根节点为最小值。如果数组中最大的几个数均在堆中，那么堆中根节点的值就是问题的解。
构造最小堆
void minheapfix(int a[], int i, int n) { int temp = a[i]; int j = 2 * i + 1; while (j < n) { if (j + 1 < n&&a[j + 1] < a[j]) { j = j + 1; } if (a[j] > temp) break; a[i] = a[j]; i = j; j = i * 2 + 1; } a[i] = temp; } void buildheap(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) { minheapfix(a, i, n); } }
最小堆已构造完成，将数组中剩余的值与根节点相比，大于根节点的值则将根节点的值与之交换，同时维护最小堆的特性，遍历结束，则根结点即为问题的解。
int findK1(int a[], int l, int r, int k) { int n = r + 1; buildheap(a, k); for (int i = k; i < n; ++i) { if (a[i] > a[0]) { swap(a[i], a[0]); minheapfix(a, 0, k); } } return a[0]; }
4、BFPRT算法
面说了快排法能够使得其时间复杂度到达期望为O(n)，那能不能使得时间复杂度严格为O(n)呢？可以的，这里就引出了BFPRT算法。
首先我们可以来看一下BFPRT算法的步骤：
- 分组（5个一组）
- 小组内排序(对于每一组的排序的时间复杂度是O(1))
- 把每个组的中位数拿出来组成一个新的数组
- 使用BFPRT递归算出这个中位数组的中位数
- 用这个当做划分值进行划分
- 划分成两边以后递归调用直到找到第k个数
原理：
通过这样选到的划分数一定在0.3N-0.7N之间，如图所示
每次选取到的划分数一定都比红色的数要大，比蓝色的数要小
这样时间复杂度的迭代公式就是：
通过推导不难算出其时间复杂度严格为O(n)
#include <iostream> #include <algorithm> using namespace std; int InsertSort(int array[], int left, int right); int GetPivotIndex(int array[], int left, int right); int Partition(int array[], int left, int right, int pivot_index); int BFPRT(int array[], int left, int right, int k); int main() { int k = 8; // 1 <= k <= array.size int array[20] = { 11,9,10,1,13,8,15,0,16,2,17,5,14,3,6,18,12,7,19,4 }; cout << "原数组："; for (int i = 0; i < 20; i++) cout << array[i] << " "; cout << endl; // 因为是以 k 为划分，所以还可以求出第 k 小值 cout << "第 " << k << " 小值为：" << array[BFPRT(array, 0, 19, k)] << endl; cout << "变换后的数组："; for (int i = 0; i < 20; i++) cout << array[i] << " "; cout << endl; return 0; } /** * 对数组 array[left, right] 进行插入排序，并返回 [left, right] * 的中位数。 */ int InsertSort(int array[], int left, int right) { int temp; int j; for (int i = left + 1; i <= right; i++) { temp = array[i]; j = i - 1; while (j >= left && array[j] > temp) { array[j + 1] = array[j]; j--; } array[j + 1] = temp; } return ((right - left) >> 1) + left; } /** * 数组 array[left, right] 每五个元素作为一组，并计算每组的中位数， * 最后返回这些中位数的中位数下标（即主元下标）。 * * @attention 末尾返回语句最后一个参数多加一个 1 的作用其实就是向上取整的意思， * 这样可以始终保持 k 大于 0。 */ int GetPivotIndex(int array[], int left, int right) { if (right - left < 5) return InsertSort(array, left, right); int sub_right = left - 1; // 每五个作为一组，求出中位数，并把这些中位数全部依次移动到数组左边 for (int i = left; i + 4 <= right; i += 5) { int index = InsertSort(array, i, i + 4); swap(array[++sub_right], array[index]); } // 利用 BFPRT 得到这些中位数的中位数下标（即主元下标） return BFPRT(array, left, sub_right, ((sub_right - left + 1) >> 1) + 1); } /** * 利用主元下标 pivot_index 进行对数组 array[left, right] 划分，并返回 * 划分后的分界线下标。 */ int Partition(int array[], int left, int right, int pivot_index) { swap(array[pivot_index], array[right]); // 把主元放置于末尾 int partition_index = left; // 跟踪划分的分界线 for (int i = left; i < right; i++) { if (array[i] < array[right]) { swap(array[partition_index++], array[i]); // 比主元小的都放在左侧 } } swap(array[partition_index], array[right]); // 最后把主元换回来 return partition_index; } /** * 返回数组 array[left, right] 的第 k 小数的下标 */ int BFPRT(int array[], int left, int right, int k) { int pivot_index = GetPivotIndex(array, left, right); // 得到中位数的中位数下标（即主元下标） int partition_index = Partition(array, left, right, pivot_index); // 进行划分，返回划分边界 int num = partition_index - left + 1; if (num == k) return partition_index; else if (num > k) return BFPRT(array, left, partition_index - 1, k); else return BFPRT(array, partition_index + 1, right, k - num); }
原数组：11 9 10 1 13 8 15 0 16 2 17 5 14 3 6 18 12 7 19 4 第 8 小值为：7 变换后的数组：4 0 1 3 2 5 6 7 8 9 10 12 13 14 17 15 16 11 18 19