随机伪快排法 求第k大数

本文主要是介绍随机伪快排法 求第k大数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

分治法求第K大数

利用快排的思想求一个数列的第k大数， 高二开始写快排，但是一直没有非常清晰的理解，知道是分治， 但不理解细节。 今天借助写这个的机会，同时阅读了《编程珠玑》里的四种快排写法，才感觉更加清晰了。 这次写的快排才真正有了一个数，其左边的数都比他小， 右边的都比他大。

/************************************************************************/
/* 随机化伪快排求第k大数                                                    */
/************************************************************************/#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;#define maxn 10100int num[maxn];int Qsort(int l, int r, int key){int mid, ll = l, rr = r + 1;mid = rand() % (r - l + 1) + l;swap(num[l], num[mid]);while(ll <= rr){do { ll ++; } while( ll <= r && num[ll] < num[l] );do { rr --; } while( num[rr] > num[l] );if(ll < rr){swap(num[ll], num[rr]);}}swap(num[l], num[rr]);if(rr - l + 1 >= key){if(rr - l + 1 == key) return num[rr];return Qsort(l, rr, key);}else{return Qsort(rr + 1, r, key - (rr - l + 1));}
}int main(){int n;while(~scanf("%d", &n)){for(int i = 0; i < n; ++ i){scanf("%d", &num[i]);}int ans = Qsort(0, n - 1, n / 2 + 1);printf("%d\n", ans);}return 0;
}

这篇关于随机伪快排法 求第k大数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---