? ? ? 主要是利用快排的RANDOMIZED_PARTTITION()函數返回一個第q小的數，且第q小的數的坐標是絕對坐標而不是相對坐標，比如輸入坐標范圍為[p,r]的數組，第q小的數會返回p+q-1的坐標。

#include "stdafx.h" #include<iostream> #include <stdlib.h> #include <time.h> using namespace std;#define SB -1int RANDOM(int p, int r) {srand((unsigned)time(NULL));return (rand() % (r - p + 1)) + p; }int partition(int a[], int p, int r) {int x, i, t;x = a[r];i = p - 1;t = 0;for (int j = p; j <= r - 1; j++){if (a[j]< x){i = i + 1;int ti;ti = a[i];a[i] = a[j];a[j] = ti;}if (a[j] == x){t = t + 1;int ti;ti = a[i + t];a[i + t] = a[j];a[j] = ti;}}int tii;tii = a[i + t + 1];a[i + 1 + t] = a[r];a[r] = tii;return i + 1; }int random_partion(int a[], int p, int r) {int i = RANDOM(p, r);int tii;tii = a[i];a[i] = a[r];a[r] = tii;return partition(a, p, r); }/*int random_select(int a[], int p, int r, int i) //隨機選擇算法遞歸實現 {if (p == r)return a[p];int q;q = random_partion(a, p, r);int k = q - p + 1;if (i == k)return a[q];else if (i < k)return random_select(a, p, q - 1, i);elsereturn random_select(a, q+1, r, i-k); }*/int random_select2(int a[], int p, int r, int i) //隨機選擇算法循環實現 {if (p == r)return a[p];int q;int head = p, end = r;q = random_partion(a, head, end);while (i != q) {if (i < q) {end = q - 1;if (end > r)end = r;q = random_partion(a, head, end);}else {head = q + 1;if (head > r)head = r;q = random_partion(a, head, end);}}return a[q]; }int main() {int a[] = { SB ,3 ,2 ,4 ,5 ,6 ,7,8,9,10,11,12,13}; //SB為哨兵，不包括在選擇項cout << random_select2(a, 1, 12, 7);while (1);return 0; }

　　

轉載于:https://www.cnblogs.com/linear/p/6569177.html

總結

以上是生活随笔為你收集整理的线性选择算法的递归实现和循环实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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