線性時間選擇

（一）題目

問題描述

給定線性序集中$n$個元素和一個正數$k$，$1\le k\le n$，要求找出這$n$個元素中第$k$小的元素

注意：$n$中的元素不重復

（二）解答

1.RandomizedSelect算法

算法思路

在數組$a[p:r]$中隨機找一個數$i$將數組劃分成兩個子數組$a[p:i]$和$a[i+1:r]$，如果數組$a[p:r]$的長度小于等于$k$，說明第$k$小的數在這個數組，將其遞歸，否則遞歸數組$a[i+1:r]$，直到 $p=r$，數組被分割成只剩下一個元素，該元素就是第$k$小的元素。

舉例

源代碼

#include<iostream> #include<cstdio> #include<random>using namespace std;int n, k, len;//將數組數組首元素a[p]作為基準數將數組分割 int Partition(int a[], int p, int r); //交換兩個元素 void Swap(int &a, int &b); //在數組中隨機選擇一個數將數組分割 int RandomizedPartition(int a[], int p, int r); //產生隨機數 int Random(int x, int y); //線性劃分 int RandomizedSelect(int a[], int p, int r, int k);int main() {//輸入數組長度ncin>>n;//輸入數組int *a = new int[n];for (int i = 0; i < n; ++i){cin>>a[i];}//輸入第k小cin>>k;//找第k小并返回int res = RandomizedSelect(a, 0, n - 1, k);cout<<res<<endl;delete []a;return 0; }int Partition(int a[], int p, int r) {//i指向首元素，j指向尾元素的下一個元素int i = p, j = r + 1;//將首元素作為基準數int x = a[p];while (1){//i從基準數右邊的元素開始找，直到找到第一個大于等于基準數的元素while (a[++i] < x && i < r);//j從尾元素開始找，直到找到第一個小于等于基準數的元素while (a[--j] > x);//若i>=j，說明基準數的位置已找到，為jif (i >= j){break;}//交換兩個元素，使得基準數左邊的數均不大于它，右邊的數均不小于它Swap(a[i], a[j]);}//將基準數歸位a[p] = a[j];a[j] = x;//返回基準數的位置return j; }void Swap(int &a, int &b) {int temp;temp = a;a = b;b = temp; }int RandomizedPartition(int a[], int p, int r) {//在p和r之間找一個隨機數int i = Random(p, r);Swap(a[i], a[p]);return Partition(a, p, r); }int Random(int x, int y) {return x + rand() % (y - x); }int RandomizedSelect(int a[], int p, int r, int k) {//數組被分割成只剩下一個元素，該元素就是第k小的元素if (p == r){return a[p];}//在數組中隨機找一個數將數組分割，分成小于等于該基準的數組和大于該基準的數組int i = RandomizedPartition(a, p, r);//求較小數數組的長度len = i - p + 1;//若較小數數組的長度小于等于k，說明第k小的元素在這個數組內，將其遞歸if (k <= len){return RandomizedSelect(a, p, i, k);}//否則，說明第k小的元素在較大數數組，將其遞歸else{return RandomizedSelect(a, i + 1, r, k - len);} }

2.Select算法

算法思路

將原數組分成$?\frac{n}{5}?$組，每組有5個元素（最后一個數組的元素個數可能不等于5，）將這5個元素排序后找到其中位數并將中位數置于每組的開頭，遞歸調用Select算法找到各組中位數的中位數作為劃分基準x（$?\frac{n}{5}?$為奇數時找其中位數，為偶數時找其中位數中較大的那個），劃分后的處理與RandomizedSelect算法相同。

舉例

源代碼

#include<iostream> #include<cstdio> #include<random>using namespace std;int n, k, len;//選擇排序 void SelectSort(int a[], int p, int r); //將x作為基準數將數組分割，返回x的位置 int Partition(int a[], int p, int r, int x); //交換兩個元素 void Swap(int &a, int &b); //找每組的中位數,返回中位數的位置i int SearchMid(int a[], int p, int r); //線性劃分 int Select(int a[], int p, int r, int k);int main() {//輸入數組長度ncin>>n;//輸入數組int *a = new int[n];for (int i = 0; i < n; ++i){cin>>a[i];}//輸入第k小cin>>k;//找第k小并返回int res = Select(a, 0, n - 1, k);cout<<res<<endl;delete []a;return 0; }void SelectSort(int a[], int p, int r) {for (int i = p; i < r; ++i){int index = i;for (int j = i + 1; j <= r; ++j){if (a[j] < a[index]){index = j;}}Swap(a[i], a[index]);} }int Partition(int a[], int p, int r, int x) {//i指向首元素的前一個位置，j指向尾元素的后一個位置int i = p - 1, j = r + 1;while (1){//i從基準數右邊的元素開始找，直到找到第一個大于等于基準數的元素while (a[++i] < x && i < r);//j從尾元素開始找，直到找到第一個小于等于基準數的元素while (a[--j] > x && j > p);//若i>=j，說明基準數的位置已找到，為jif (i >= j){break;}//交換兩個元素，使得基準數左邊的數均不大于它，右邊的數均不小于它Swap(a[i], a[j]);}//返回基準數的位置return j; }void Swap(int &a, int &b) {int temp;temp = a;a = b;b = temp; }int SearchMid(int a[], int p, int r) {//建立與數組a同等大小的數組bint *b = new int[r - p + 1];//用數組b存放數組a（注意此時b的首地址為0，而a的首地址為p）for (int i = p; i <= r; ++i){b[i - p] = a[i];}//將數組b排序，b[(r-p+1)/2]為中位數SelectSort(b, 0, r - p);for (int i = p; i <= r; ++i){if (a[i] == b[(r - p + 1) / 2]){return i;}}delete []b;return 0; }int Select(int a[], int p, int r, int k) {if (r - p < 5){SelectSort(a, p, r);return a[p + k - 1];}//分成n/5組，每組5個，找到每組的中位數并將它放到數組首元素的位置for (int i = 0; i <= (r - p - 4) / 5; ++i){int mid = SearchMid(a, p + 5 * i, p + 5 * i + 4);Swap(a[mid], a[p + i]);}//找到各組中位數的中位數int x = Select(a, p, p + (r - p - 4) / 5, (r - p - 4) / 10 + 1);//按照中位數劃分int i = Partition(a, p, r, x);//求較小數數組的長度len = i - p + 1;//若較小數數組的長度小于等于k，說明第k小的元素在這個數組內，將其遞歸if (k <= len){return Select(a, p, i, k);}//否則，說明第k小的元素在較大數數組，將其遞歸else{return Select(a, i + 1, r, k - len);} }

（三）總結

復雜度分析

1.RandomizedSelect算法

對于RandomizedSelect算法，該算法劃分的基準是隨機的，最好情況下的時間復雜度為$\mathrm{O}(n)$，而最壞情況下的時間復雜度為$\mathrm{O}(n^2)$，但這種情況在隨機劃分的過程中發生的的概率極小，因此RandomizedSelect算法的平均時間復雜度為$\mathrm{O}(n)$。

2.Select算法

對于Select算法，該算法劃分的基準是固定的，若能在線性時間內找到一個劃分基準，使得按這個基準劃分的兩個子數組長度均至少為原數組長度的 倍（0<$\epsilon$<1）,那么在最壞情況下，Select算法的時間復雜度也為$\mathrm{O}(n)$。

例如：當$\epsilon =\frac{9}{10}$時，算法遞歸調用產生的2個子數組的長度至少縮短$\frac{1}{10}$。因此，在最壞情況下，算法所需的計算時間$T(n)$滿足$T(n)\le T(\frac{9n}{10})+\mathrm{O}(n)$，解得$T(n)=\mathrm{O}(n)$

在線性時間內找到一個劃分基準，使得按這個基準劃分的兩個子數組長度均至少為原數組長度的$\epsilon$倍（0<$\epsilon$<1）,那么在最壞情況下，Select算法的時間復雜度也為$\mathrm{O}(n)$。

例如：當$\epsilon =\frac{9}{10}$時，算法遞歸調用產生的2個子數組的長度至少縮短$\frac{1}{10}$。因此，在最壞情況下，算法所需的計算時間$T(n)$滿足$T(n)\le T(\frac{9n}{10})+\mathrm{O}(n)$，解得$T(n)=\mathrm{O}(n)$

總結

以上是生活随笔為你收集整理的算法分析与设计-线性时间选择详解（通俗易懂，含图解，附源码）（c++)的全部內容，希望文章能夠幫你解決所遇到的問題。

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