SELECT算法利用快排中的partition思想来进行无序数组的快速选择。
寻找第i个顺序统计量可以简单理解为寻找第i小的元素。
该算法通过为partition选择一个好的主元,来保证Partition得到一个好的划分。
当然partition需要进行一些修改,把划分的主元也作为输入参数。
代码如下:(仅供参考)
1 void InsertionSort(int * const begin, int * const end) {
2 int i, j, key;
3 for (i = 1; i < begin - end; ++i) {
4 key = *(begin + i);
5 for (j = i - 1; j >= 0 && (*(begin + j) > key); --j) {
6 *(begin + j + 1) = *(begin + j);
7 }
8 *(begin + j + 1) = key;
9 }
10 }
11 int Partition(int * const begin, int * const end, int x) {
12 int i = -1;
13 for (int j = 0; j < (end - begin); ++j) {
14 if (*(begin + j) < x) {
15 ++i;
16 swap(*(begin + i), *(begin + j));
17 }
18 else if (*(begin + j) == x && j != (end - begin - 1)) {
19 swap(*(begin + j), *(end - 1));
20 --j;
21 }
22 }
23 ++i;
24 swap(*(begin + i), *(end - 1));
25 return i;
26 }
27
28 //返回第k小的元素,要求输入元素互异,最坏情况下时间复杂度为线性
29 int Select(int * const begin, int * const end, int k) {
30 if (end - begin == 1)
31 return *begin;
32 int n = end - begin;
33 int groupnum = n / 5; //groupnum个组,每组五个数
34 int medium[10000]; //因小于50000个数
35
36 int i, j, t = groupnum;
37 for (i = 0, j = 0; t--; i += 5) {
38 InsertionSort(begin + i, begin + i + 5);
39 medium[j++] = *(begin + i + 2);
40 }
41 if (n > (groupnum * 5)) {
42 InsertionSort(begin + i, end);
43 medium[j++] = *(begin + i + (end - begin - i) / 2);
44 }
45
46 int x = Select(medium, medium + j, (j + 1) / 2);
47 int m = Partition(begin, end, x) + 1;
48 if (m == k)
49 return x;
50 else if (m > k)
51 return Select(begin, begin + m - 1, k);
52 else
53 return Select(begin + m, end, k - m);
54 }
原文链接: https://www.cnblogs.com/yxsrt/p/12193807.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/191946
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!