Select（快速选择顺序统计量）原理及C++代码实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Select（快速选择顺序统计量）原理及C++代码实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1632字，纯文字阅读大概需要3分钟。
内容图文
SELECT算法利用快排中的partition思想来进行无序数组的快速选择。
寻找第i个顺序统计量可以简单理解为寻找第i小的元素。
该算法通过为partition选择一个好的主元，来保证Partition得到一个好的划分。
当然partition需要进行一些修改，把划分的主元也作为输入参数。
代码如下：（仅供参考）
1
void InsertionSort(int * const begin, int * const end) {
2int i, j, key;
3for (i = 1; i < begin - end; ++i) {
4 key = *(begin + i);
5for (j = i - 1; j >= 0 && (*(begin + j) > key); --j) {
6 *(begin + j + 1) = *(begin + j);
7 }
8 *(begin + j + 1) = key;
9 }
10}
11int Partition(int * const begin, int * const end, int x) {
12int i = -1;
13for (int j = 0; j < (end - begin); ++j) {
14if (*(begin + j) < x) {
15 ++i;
16 swap(*(begin + i), *(begin + j));
17 }
18elseif (*(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));
25return i;
26}
2728//返回第k小的元素,要求输入元素互异，最坏情况下时间复杂度为线性29int Select(int * const begin, int * const end, int k) {
30if (end - begin == 1)
31return *begin;
32int n = end - begin;
33int groupnum = n / 5; //groupnum个组，每组五个数34int medium[10000]; //因小于50000个数3536int i, j, t = groupnum;
37for (i = 0, j = 0; t--; i += 5) {
38 InsertionSort(begin + i, begin + i + 5);
39 medium[j++] = *(begin + i + 2);
40 }
41if (n > (groupnum * 5)) {
42 InsertionSort(begin + i, end);
43 medium[j++] = *(begin + i + (end - begin - i) / 2);
44 }
4546int x = Select(medium, medium + j, (j + 1) / 2);
47int m = Partition(begin, end, x) + 1;
48if (m == k)
49return x;
50elseif (m > k)
51return Select(begin, begin + m - 1, k);
52else53return Select(begin + m, end, k - m);
54 }
原文：https://www.cnblogs.com/yxsrt/p/12193807.html
内容总结
以上是互联网集市为您收集整理的Select（快速选择顺序统计量）原理及C++代码实现全部内容，希望文章能够帮你解决Select（快速选择顺序统计量）原理及C++代码实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。