数组第K小数问题及其对于快排和堆排的相关优化比较

题目描述

给定一个整数数组a[0,...,n-1]，求数组中第k小数

输入描述

首先输入数组长度n和k，其中1<=n<=5000, 1<=k<=n

然后输出n个整形元素，每个数的范围[1, 5000]

输出描述

该数组中第k小数

样例输入

4 2
1 2 3 4

样例输出


其实可以用 堆 来做，保证根节点为最小值，然后逐步剔除。不过当然也可以直接排序。
权当熟悉一下STL：

 1 #include <vector>
 2 #include <algorithm>
 3 #include <iostream>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n, k;
 9     cin >> n >> k;
10 
11     vector<int> a(n, 0);
12     for (int i = 0; i < n; i++)
13     {
14         cin >> a[i];
15     }
16     sort(a.begin(), a.end());
17 
18     cout << a[k-1];
19 
20     return 0;
21 }


在和 Space_Double7 讨论后（详见讨论区），于是有了想要比较 快排 和 堆排 对于这道题各自的效率的想法。
于是写了一个程序来比较它们各自的运行时间，程序主要包括 随机生成输入数据、分别用快排和堆排求解并计时、比较 这几个部分。
代码如下：

  1 #include <vector>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <stdlib.h>
  5 #include <time.h>
  6 #include <windows.h>
  7 
  8 using namespace std;
  9 
 10 // for timing
 11 clock_t start, stop;
 12 double durationOfQsort, durationOfHeapsort;
 13 
 14 vector<int> num;
 15 int k, ans, n;
 16 bool found;
 17 
 18 // 快排： 选定轴点
 19 int parti(int lo, int hi)
 20 {
 21     swap(num[lo], num[lo + rand() % (hi - lo + 1)]);
 22     int pivot = num[lo];
 23     while (lo < hi)
 24     {
 25         while ((lo < hi) && (pivot <= num[hi])) hi--;
 26         num[lo] = num[hi];
 27         while ((lo < hi) && (num[lo] <= pivot)) lo++;
 28         num[hi] = num[lo];
 29     }
 30     num[lo] = pivot;
 31     if (lo == k)
 32     {
 33         found = true; // 表征已确定找到第 k 小数
 34         ans = num[k];
 35     }
 36     return lo;
 37 }
 38 
 39 // 快排主体
 40 void quicksort(int lo, int hi)
 41 {
 42     if ((hi - lo < 2) || (found))
 43     {
 44         if ((!found) && (lo == k))
 45         {
 46             found = true;
 47             ans = num[k];
 48         }
 49         return;
 50     }
 51     int mi = parti(lo, hi - 1);
 52     quicksort(lo, mi);
 53     quicksort(mi + 1, hi);
 54 }
 55 
 56 #define InHeap(n, i)        (( (-1) < (i) ) && ( (i) < (n) ))
 57 #define Parent(i)            ((i-1)>>1)
 58 #define LastInternal(n)        Parent(n-1)
 59 #define LChild(i)            (1+((i) << 1))
 60 #define RChild(i)            ((1+(i)) << 1)
 61 #define LChildValid(n, i)    InHeap(n, LChild(i))
 62 #define RChildValid(n, i)    InHeap(n, RChild(i))
 63 #define Bigger(PQ, i, j)    ((PQ[i])<(PQ[j])? j : i)
 64 #define ProperParent(PQ, n, i) 
 65     (RChildValid(n, i) ? Bigger(PQ, Bigger(PQ, i, LChild(i)), RChild(i)):
 66     (LChildValid(n, i) ? Bigger(PQ, i, LChild(i)):i
 67     )
 68     )
 69 
 70 // 对向量前 n 个元素中的第 i 实施下滤操作
 71 int percolateDown(int n, int i)
 72 {
 73     int j;
 74     while (i != (j = ProperParent(num, n, i)))
 75     {
 76         swap(num[i], num[j]);
 77         i = j;
 78     }
 79     return i;
 80 }
 81 
 82 // Floyd 建堆算法
 83 void heapify()
 84 {
 85     for (int i = LastInternal(n); InHeap(n, i); i--)
 86         percolateDown(n, i);
 87 }
 88 
 89 // 删除堆中最大的元素
 90 int delMax(int hi)
 91 {
 92     int maxElem = num[0]; 
 93     num[0] = num[hi];
 94     percolateDown(hi, 0);
 95     return maxElem;
 96 }
 97 
 98 // 堆排主体
 99 void heapsort()
100 {
101     heapify();
102     int hi = n;
103     while (hi > 0)
104     {
105         --hi;
106         num[hi] = delMax(hi);
107         if (hi == k)
108         {
109             ans = num[k];
110             return;
111         }
112     }
113 }
114 
115 int main()
116 {
117     int scoreOfQsort = 0, scoreOfHeapsort = 0;
118 
119     for (int iter = 0; iter < 30; iter++)
120     {
121         // 确定 n 的大致最大范围，注意随机 n 会有向右 MaxN 的偏差 
122         const int MaxN = 3001;
123         
124         // 产生一个 0..n-1 的随机序列输入数组，n 最大为3000
125         cout << "**********************第" << iter + 1 << "次************************" << endl;
126         //srand(unsigned(clock()));
127         n = rand() % MaxN + MaxN;
128         vector<int> a(n, 0);
129         for (int i = 0; i < n; i++)
130             a[i] = i;
131         random_shuffle(a.begin(), a.end());
132 
133         cout << "产生一个 0.." << n - 1 << " 的随机序列输入数组：" << endl;
134         /*for (int i = 0; i < n; i++)
135             cout << a[i] << " ";*/
136         cout << endl;
137 
138         // 随机生成 k
139         //srand(unsigned(clock()));
140         k = rand() % n;
141         cout << "k = " << k << endl << endl;
142 
143         // 第 k 小的数一定是 k，因为 random_shuffle，同时避免退化情形对快排一般性的影响
144         cout << "在该数组中第 " << k << " 小的数是： " << k << endl << endl << endl;
145 
146         // qsort
147         cout << "快排：" << endl;
148         num = a; 
149         start = clock();
150         found = false;
151         quicksort(0, n);
152         stop = clock();
153         durationOfQsort = ((double)(stop - start)*1000) / CLK_TCK;
154         cout << "Ok.. 我已经找到了第 " << k << " 小的数，它是: " << ans << endl;
155         cout << "快排用时： " << durationOfQsort << "ms" << endl;
156         if (ans != k)
157         {
158             cout << "注意！！！答案错误！！！" << endl;
159             system("pause");
160         }
161         /*else
162         {
163             cout << "此时的序列情况是： ";
164             for (int i = 0; i < n; i++)
165                 cout << num[i] << " ";
166         }*/
167         cout << endl << endl;
168 
169         // heapsort
170         cout << "堆排：" << endl;
171         num = a;
172         start = clock();
173         heapsort();
174         stop = clock();
175         durationOfHeapsort = ((double)(stop - start) * 1000) / CLK_TCK;
176         cout << "Ok.. 我已经找到了第 " << k << " 小的数，它是: " << num[k] << endl;
177         cout << "堆排用时： " << durationOfHeapsort << "ms" << endl;
178         if (num[k] != k)
179         {
180             cout << "注意！！！答案错误！！！" << endl;
181             system("pause");
182         }
183         /*else
184         {
185             cout << "此时的序列情况是： ";
186             for (int i = 0; i < n; i++)
187                 cout << num[i] << " ";
188         }*/
189         cout << endl << endl;
190 
191         if (durationOfHeapsort > durationOfQsort) scoreOfQsort++;
192         else scoreOfHeapsort++;
193     }
194     cout << "*******************END***********************";
195     cout << endl << endl << "总比分（快排：堆排）： " << scoreOfQsort << " : " << scoreOfHeapsort;
196     cout << endl;
197 
198     return 0;
199 }

运行了几下，大致可以看出快排：堆排的效率比趋近于 2:1（对于每个case的耗时少则计分，计分多的效率高），这是其中 3 次的结果：

感兴趣的可以自己在本地运行一下~

然而我发现依然存在一个问题，我们主要想讨论的是对于 “一找到第k小的元素便立即退出”这件事对于整个完全排序本身优化程度的大小。

横向来看，仅仅比较优化后的排序耗时并不能确定到底是快速排序本身对于随机数据而言比堆排序性能好（从上面看，似乎是显然的），还是 “一找到第k小的元素便立即退出”这个优化在这里帮了快速排序的大忙，使其在这里表现出了更好的性能。

纵向来看，我们想看看该优化对于完全排序而言，能优化到什么程度。

所以我决定比较两种排序 优化退出的时间占完全排序的时间 的比，来看看这个优化对于完全排序的影响程度。

这是修改以后的代码，算的是百分比，百分比越小，优化越明显：

  1 #include <vector>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <stdlib.h>
  5 #include <time.h>
  6 #include <windows.h>
  7 
  8 using namespace std;
  9 
 10 // for timing
 11 clock_t start, stop, stop1;
 12 double durationOfQsort, durationOfHeapsort;
 13 
 14 vector<int> num;
 15 int k, ans, n;
 16 bool found;
 17 double time1, time2;
 18 double average1 = 0, average2 = 0;
 19 
 20 // 快排： 选定轴点
 21 int parti(int lo, int hi)
 22 {
 23     swap(num[lo], num[lo + rand() % (hi - lo + 1)]);
 24     int pivot = num[lo];
 25     while (lo < hi)
 26     {
 27         while ((lo < hi) && (pivot <= num[hi])) hi--;
 28         num[lo] = num[hi];
 29         while ((lo < hi) && (num[lo] <= pivot)) lo++;
 30         num[hi] = num[lo];
 31     }
 32     num[lo] = pivot;
 33     if ((!found)&&(lo == k))
 34     {
 35         stop1 = clock();
 36         found = true;
 37     }
 38     return lo;
 39 }
 40 
 41 // 快排主体
 42 void quicksort(int lo, int hi)
 43 {
 44     if (hi - lo < 2)
 45     {
 46         if ((!found) && (lo == k))
 47         {
 48             stop1 = clock();
 49             found = true;
 50         }
 51         return;
 52     }
 53     int mi = parti(lo, hi - 1);
 54     quicksort(lo, mi);
 55     quicksort(mi + 1, hi);
 56 }
 57 
 58 #define InHeap(n, i)        (( (-1) < (i) ) && ( (i) < (n) ))
 59 #define Parent(i)            ((i-1)>>1)
 60 #define LastInternal(n)        Parent(n-1)
 61 #define LChild(i)            (1+((i) << 1))
 62 #define RChild(i)            ((1+(i)) << 1)
 63 #define LChildValid(n, i)    InHeap(n, LChild(i))
 64 #define RChildValid(n, i)    InHeap(n, RChild(i))
 65 #define Bigger(PQ, i, j)    ((PQ[i])<(PQ[j])? j : i)
 66 #define ProperParent(PQ, n, i) 
 67     (RChildValid(n, i) ? Bigger(PQ, Bigger(PQ, i, LChild(i)), RChild(i)):
 68     (LChildValid(n, i) ? Bigger(PQ, i, LChild(i)):i
 69     )
 70     )
 71 
 72 // 对向量前 n 个元素中的第 i 实施下滤操作
 73 int percolateDown(int n, int i)
 74 {
 75     int j;
 76     while (i != (j = ProperParent(num, n, i)))
 77     {
 78         swap(num[i], num[j]);
 79         i = j;
 80     }
 81     return i;
 82 }
 83 
 84 // Floyd 建堆算法
 85 void heapify()
 86 {
 87     for (int i = LastInternal(n); InHeap(n, i); i--)
 88         percolateDown(n, i);
 89 }
 90 
 91 // 删除堆中最大的元素
 92 int delMax(int hi)
 93 {
 94     int maxElem = num[0]; 
 95     num[0] = num[hi];
 96     percolateDown(hi, 0);
 97     return maxElem;
 98 }
 99 
100 // 堆排主体
101 void heapsort()
102 {
103     heapify();
104     int hi = n;
105     while (hi > 0)
106     {
107         --hi;
108         num[hi] = delMax(hi);
109         if (hi == k) stop1 = clock();
110     }
111 }
112 
113 int main()
114 {
115     // 确定 n 的大致最大范围，注意随机 n 会有向右 MaxN 的偏差 
116     const int MaxN = 3001;
117     
118     // 计算次数
119     const int times = 30;
120 
121     int scoreOfQsort = 0, scoreOfHeapsort = 0;
122 
123     for (int iter = 0; iter < times; iter++)
124     {
125         
126         
127         // 产生一个 0..n-1 的随机序列输入数组，n 最大为3000
128         cout << "**********************第" << iter + 1 << "次************************" << endl;
129         //srand(unsigned(clock()));
130         n = rand() % MaxN + MaxN;
131         vector<int> a(n, 0);
132         for (int i = 0; i < n; i++)
133             a[i] = i;
134         random_shuffle(a.begin(), a.end());
135 
136         cout << "产生一个 0.." << n - 1 << " 的随机序列输入数组：" << endl;
137         /*for (int i = 0; i < n; i++)
138             cout << a[i] << " ";*/
139         cout << endl;
140 
141         // 随机生成 k
142         //srand(unsigned(clock()));
143         k = rand() % n;
144         cout << "k = " << k << endl << endl;
145 
146         // 第 k 小的数一定是 k，因为 random_shuffle，同时避免退化情形对快排一般性的影响
147         cout << "在该数组中第 " << k << " 小的数是： " << k << endl << endl << endl;
148 
149         // qsort
150         cout << "快排：" << endl;
151         num = a; 
152         start = clock();
153         found = false;
154         quicksort(0, n);
155         stop = clock(); 
156         time1 = (double)(stop1 - start) * 1000 / CLK_TCK;
157         time2 = (double)(stop - start) * 1000 / CLK_TCK;
158         cout << "找到 k 的时间： " << time1 << " ms" << endl;
159         cout << "完全排序 的时间： " << time2 << " ms" << endl;
160         durationOfQsort = time1 / time2 * 100;
161         average1 += durationOfQsort;
162         /*cout << "Ok.. 我已经找到了第 " << k << " 小的数，它是: " << ans << endl;*/
163         cout << "快排占比： " << durationOfQsort << " %" << endl;
164         /*if (ans != k)
165         {
166             cout << "注意！！！答案错误！！！" << endl;
167             system("pause");
168         }*/
169         /*else
170         {
171             cout << "此时的序列情况是： ";
172             for (int i = 0; i < n; i++)
173                 cout << num[i] << " ";
174         }*/
175         cout << endl << endl;
176 
177         // heapsort
178         cout << "堆排：" << endl;
179         num = a;
180         start = clock();
181         heapsort();
182         stop = clock();
183         time1 = (double)(stop1 - start) * 1000 / CLK_TCK;
184         time2 = (double)(stop - start) * 1000 / CLK_TCK;
185         cout << "找到 k 的时间： " << time1 << " ms" << endl;
186         cout << "完全排序 的时间： " << time2 << " ms" << endl;
187         durationOfHeapsort = time1 / time2 * 100;
188         average2 += durationOfHeapsort;
189         //cout << "Ok.. 我已经找到了第 " << k << " 小的数，它是: " << num[k] << endl;
190         cout << "堆排占比： " << durationOfHeapsort << " %" << endl;
191         /*if (num[k] != k)
192         {
193             cout << "注意！！！答案错误！！！" << endl;
194             system("pause");
195         }*/
196         /*else
197         {
198             cout << "此时的序列情况是： ";
199             for (int i = 0; i < n; i++)
200                 cout << num[i] << " ";
201         }*/
202         cout << endl << endl;
203 
204         if (durationOfHeapsort > durationOfQsort) scoreOfQsort++;
205         else scoreOfHeapsort++;
206     }
207     cout << "*******************END***********************";
208     cout << endl << endl << "总比分（快排：堆排）： " << scoreOfQsort << " : " << scoreOfHeapsort;
209     cout << endl;
210     cout << endl << "快排平均占比： " << average1 / times << " %" << endl;
211     cout << endl << "堆排平均占比： " << average2 / times << " %" << endl;
212 
213     return 0;
214 }

运行 3 次的结果：

可见，

1、这个优化对于两种排序的影响程度是差不多的（百分比越小，优化越明显）；

2、对于完全排序而言，它大概相当于在前面加了一个 0.6 的系数，也就是只干了完全排序 0.6 倍的工作量，正如分析来看，依然是常系数级的优化。

由于数据是完全随机的（并且没有重复元素），快排也适应得很好，在实际用途中（对于近似随机数据），它的效率是可观的。

不！还没完！

来来来，现在我们回到原问题本身，回到查找数组第 k 小数这样经典而基础的问题本身上来……

尽管原问题数据规模小，水水就能过，但是既然已经鼓捣过了，干脆鼓捣完。

所以我还是决定写一个对于大规模数据具有普适意义的尽可能优化的算法来解决问题（优化到线性复杂度）。

再考虑这个问题，在写了一遍快排之后，会发现这是一个与快排中选取轴点很类似的问题。

轴点是左右集合的分界点，左集合所有元素比轴点小，右集合所有元素比轴点大，你可以发现，找第 K 小数就是找在位置 K 上的轴点（也正如上述优化所想）！

然而我们依然要向上面所写的程序一样，找到 k 就退出吗？

1、快速选取算法

考虑这样的情形，

当前选取的轴点正好是第k个，自然就退出；

当选取的轴点比 k 小时，我们实际上可以不用再对左集合排序了！因为我们只需要知道它们都比轴点要小，而且知道它们的个数，而此时轴点比 k 还要小，所以我们可以继续只对右集合分治下去！

同样的，当选取的轴点比 k 大时，我们实际上可以不用再对右集合排序了！因为我们只需要知道它们都比轴点要大，而且知道它们的个数，而此时轴点比 k 还要大，所以我们可以继续只对左集合分治下去！

这样，我们可以把每一次的向下两次递归变成一次。

用非递归版本代码大致表示如下：

 1 void quickSelect()
 2 {
 3     for (int lo = 0, hi = n-1; lo < hi; )
 4     {
 5         int i = lo, j = hi, pivot = num[lo]; 
 6         while (i < j)
 7         {
 8             while ( (i<j) && (pivot <= num[j]) ) j--;
 9             num[i] = num[j];
10             while ( (i<j) && (num[i] <= pivot) ) i++;
11             num[j] = num[i];
12         }
13         num[i] = pivot;
14         if ( k<=i ) hi = i - 1;
15         if ( i<=k ) lo = i + 1;
16     }
17 } // 结束后 num[k] 即是解

对于一般情况（数据接近随机），跟快排一样，此算法效率很高，不过快排的缺点它也一样具有。也就是当轴点把左右集合划分得极不均匀甚至某一个集合为空时，此时效率跟快排一样退化到 O(n^2)。

接下来考虑，堆排是不是也有优化空间呢？

2、堆选取算法

题目只需要我们选取第 K 小数，跟快速选取一样，无关目的的部分我们完全没必要做无用功。

基于这样的考虑，我们完全可以只维护一个规模为 K 的大根堆嘛！~

算法思考大致是：

首先将序列前 K 的元素用 Floyd 建堆（O(k)效率）维护成一个大根堆。

然后将剩下的元素依次插入堆，每插入一个，随机删除堆顶，使堆的规模保持在 k。

这样当所有的元素插入完毕，那么堆的根就是问题的解。

一般情况下，它的效率是比完全排序效率要高的，不过当 k 接近于 n/2 的时候，它的复杂度又会退化到 O( nlogn )。

难道真的不能从实质上将这个问题优化到线性效率上来吗？

3、k-选取算法

算法里面对于排序有一个丧病的思路：选定一个 k，当序列长度小于 k 时，sort 函数直接不作处理返回原序列。整个序列经过这样一次 sort 之后当然不是有序的，此时对这个序列做一次插入排序（因为插入排序在处理 “几乎” 有序的序列时，运行非常快）。根据算导的结论，这样的复杂度是 O(nk + n log(n/k)) 的。（其实就是相当于做n/k次k长的插入）

这种思想在这里我们也可以借鉴，大致的算法思想如下：

0) 选定一个数Q，Q为一个不大的常数；

select(A, k):

1) 如果序列A规模不大于 Q 时直接蛮力算法；　　　　// 递归基

2) 将A均匀划分为 n/Q 个子序列，各含 Q 个元素；

3) 各子序列分别排序（可采用任何排序算法），计算中位数，并将所有中位数组成一个序列；

4) 递归调用select()，计算出中位数序列的中位数，记作M；

5) 根据元素相对于 M 的大小，将 A 中元素分为三个子集：L（小于），E（相等）和G（大于）；

6) if ( |L| >= k ) return select(L, k);

　 else if ( |L| + |E| >= k ) return M;

else return select(G, k - |L| - |E|);

复杂度分析：（计最坏情况下运行时间为 T(n)）

2): O(n);

3): 由于Q为常数，累计也为 O(n);

4): 递归调用，T(n/Q)

5): O(n);

6): 中位数序列的中位数一定是全局中位数 M，而 L 和 G 的规模一定不会超过 3n/4。

所以可得如下递推关系：

T(n) = cn + T(n/Q) + T(3n/4)，c 为常数

如果取 Q = 5，则有：

T(n) = cn + T(n/5) + T(3n/4) = O(20cn) = O(n)

可见，复杂度是线性。虽如此，其常系数过大，且算法过程较复杂，在一般规模的应用中难以真正体现出效率的优势。

Reference : 《数据结构习题解析》，邓俊辉

数组第K小数问题 及其对于 快排和堆排 的相关优化比较

数组第K小数问题及其对于快排和堆排的相关优化比较