思路：固定一個數，把這個數放到合法的位置，然后左邊的數都是比它小，右邊的數都是比它大

固定權值選的是第一個數，或者一個隨機數

因為固定的是左端點，所以一開始需要在右端點開始，找一個小于權值的數，從左端點開始，找一個大于權值的數

那么交換他們即可、最后的話，One == two那個位置就是權值應該去到的位置，這個時候把原問題劃分為更小的子問題

就是[be, one - 1]和[one + 1, en]這兩個子問題。

下面的是有bug的，當rand去到en的時候，就會wa? （修復了）

比如數據是，4、5、1、2就很容易wa

用隨機做了一個TLE了，還沒wa就TLE了

http://codeforces.com/contest/732/problem/D

ID =?be也是TLE，不明白STL的sort是怎么來的

int myRand(int be, int en) {return be + (rand() % (en - be + 1)); }void quickSort(int a[], int be, int en) {if (be >= en) return ;int id = myRand(be, en); // 這樣不行，需要id = beint one = be, two = en;while (one != two) {while (two > one && a[two] >= a[id]) --two; // 找第一個比id小的, 必須先找小的while (one < two && a[one] <= a[id]) ++one; // 找第一個比id大的, 因為基準數是beif (one < two) swap(a[one], a[two]);//固定id = be，需要從右到左是因為，如果是從左到右，例子1、2、3、4、5//找到第一個比1大的，是2，然后找不到第一個比1小，在2中相遇//然后swap(a[1], a[2]) GG }swap(a[id], a[one]);quickSort(a, be, one - 1);quickSort(a, one + 1, en); } View Code

修復：

隨機一個id，然后和第一那個數交換，就可以了。和id =?be一樣了

int myRand(int be, int en) {return be + (rand() % (en - be + 1)); }void quickSort(int a[], int be, int en) {if (be >= en) return ;int id = myRand(be, en); // swap(a[be], a[id]);id = be;int one = be, two = en;while (one != two) {while (two > one && a[two] >= a[id]) --two; // 找第一個比id小的, 必須先找小的while (one < two && a[one] <= a[id]) ++one; // 找第一個比id大的, 因為基準數是beif (one < two) swap(a[one], a[two]);//固定id = be，需要從右到左是因為，如果是從左到右，例子1、2、3、4、5//找到第一個比1大的，是2，然后找不到第一個比1小，在2中相遇//然后swap(a[1], a[2]) GG }swap(a[id], a[one]);quickSort(a, be, one - 1);quickSort(a, one + 1, en); } View Code

?

?

?

隨機生成區間里的一個數字思路：

區間大小是len，那么就生成一個0---len-1的數，加上起始點，就是落在[be, en]的數

代碼在上面。

?O(n)找第k小的數

#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; const int maxn = 1e5 + 20; int myRand(int be, int en) {return be + (rand() % (en - be + 1)); } int findKthMin(int a[], int be, int en, int k) {if (be == en) return a[be];swap(a[be], a[myRand(be, en)]);int one = be, two = en, id = be;while (one != two) {while (two > one && a[two] >= a[id]) --two; // 找第一個比id小的, 必須先找小的while (one < two && a[one] <= a[id]) ++one; // 找第一個比id大的, 因為基準數是beif (one < two) swap(a[one], a[two]);//需要從右到左是因為，如果是從左到右，例子1、2、3、4、5//找到第一個比1大的，是2，然后找不到第一個比1小，在2中相遇//然后swap(a[1], a[2]) GG }swap(a[id], a[one]);int hasKey = one - be + 1; // 有多少個元素if (hasKey >= k) return findKthMin(a, be, one, k);else return findKthMin(a, one + 1, en, k - hasKey); } int a[maxn]; void work() {int n;scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%d", a + i);}printf("%d\n", findKthMin(a, 1, n, 4)); }int main() { #ifdef localfreopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endifwork();return 0; } View Code

?

最熱門K串

找前k大的數，首先找到第n - k + 1小的數，那么這些數的右邊，都是比它大的，這個時候就是前k大了，直接排序一下就好

#include <cstring> #include <cstdio> #include <cstdlib> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; const int maxn = 1000000 + 20; int myRand(int be, int en) {return be + (rand() % (en - be + 1)); } int findKthMin(int a[], int be, int en, int k) {if (be == en) return be;swap(a[be], a[myRand(be, en)]);int one = be, two = en, id = be;while (one != two) {while (two > one && a[two] >= a[id]) --two; // 找第一個比id小的, 必須先找小的while (one < two && a[one] <= a[id]) ++one; // 找第一個比id大的, 因為基準數是beif (one < two) swap(a[one], a[two]);//需要從右到左是因為，如果是從左到右，例子1、2、3、4、5//找到第一個比1大的，是2，然后找不到第一個比1小，在2中相遇//然后swap(a[1], a[2]) GG }swap(a[id], a[one]);int hasKey = one - be + 1; // 有多少個元素if (hasKey >= k) return findKthMin(a, be, one, k);else return findKthMin(a, one + 1, en, k - hasKey); } int a[maxn]; void work() {int n, k;scanf("%d%d", &n, &k);for (int i = 1; i <= n; ++i) {scanf("%d", a + i);}int id = findKthMin(a, 1, n, n - k + 1);sort(a + id, a + 1 + n);for (int i = n; i >= id; --i) {printf("%d ", a[i]);} }int main() { #ifdef localfreopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endifwork();return 0; } View Code

?

轉載于:https://www.cnblogs.com/liuweimingcprogram/p/7775525.html

總結

以上是生活随笔為你收集整理的快速排序算法的实现 随机生成区间里的数 O（n）找第k小 O(nlogk)找前k大...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。