個人原創，禁止轉載——Zetrue_Li?

?

問題描述：在一個序列里找出第K小元素

以下程序基于函數 int select_kth_smallest(list q, int k) 實現 ：返回向量q中第k最小元的函數

算法一：

基于冒泡排序思想，暴力求解：

基本思路：要求找出第k個最小元素，可以通過在序列中遍歷k次，每次找出最小的，并放在序列頭。類似泡泡一樣，找出第k個大的泡泡（bubble）

偽代碼：

int select_kth_smallest(list q, int k){ intput: q is a list, k is the number of which the kth smallest in list output: return the value of the k largest number in listsize <- q.sizefor i <- 0:k-1 domin <- q[i]index <- ifor j <- i+1 : size-1 do if min > q[j] domin <- q[j]index <- jendifendforq[index] <- q[i]q[i] <- minendforreturn q[k-1] }

代碼：

int select_kth_smallest(vector<int> q, int k){int size = q.size();for(int a=0; a<k; a++){int min = q[a], index = a;for(int b=a+1; b<size; b++)if(min > q[b]){min = q[b];index = b;}q[index] = q[a]; q[a] = min;}return q[k-1]; }

算法復雜度分析：

由于都是在原地實現，所以空間復雜度為O（n）

尋找第k小元素，總共遍歷了k次序列。T = n?+ (n-1) + (n-2) +?...... + (n-k-1) = kn - (1+2+...+k-1) = O(nk)

?

算法二：

基于快速排序，高效求解

基本思路：每次以序列第一個元素作為中間數mid，將序列中小于等于mid的放在mid左邊，反之放在mid右邊。不妨設小于等于mid的個數為i，若k < i，則對左邊序列遞歸做相同操作；若k > i, 則對右邊序列遞歸尋找序列中第k-i小的元素；若k = i，則mid即為第k小的元素

偽代碼：

int select_kth_smallest(list q, int k){ intput: q is a list, k is the number of which the kth smallest in list output: return the value of the k largest number in listbot <- 0top <- size of qwhile bot < top doindex <- q[bot]left <- botright <- botwhile right < top doif q[right] < index doleft <- left + 1temp <- q[right]q[right] <- q[left]q[left] <- tempright <- right + 1endwhileq[left] <- q[bot]q[bot] <- indexif left + 1 < k dobot <- left + 1else if left + 1 > k dotop = leftelse doreturn q[left]endif return -1 }

代碼：

int select_kth_smallest(vector<int> q, int k){int bot = 0, top = q.size();while(bot < top){int left = bot, right = bot, index = q[bot];while(right < top){if(q[right] < index){left++;int temp = q[left];q[left] = q[right];q[right] = temp;}right++;}/*for(int a=0; a<q.size(); a++)cout<< q[a]<< ' ';cout<< endl;cout<< bot<< ' '<< top<< endl;*/q[bot] = q[left];q[left] = index;if(left+1 < k)bot = left + 1;else if(left+1 > k)top = left;elsereturn q[left];}return -1; }

算法復雜度分析：

空間復雜度：原地操作，O（n）

時間復雜度：由于將序列第一個元素作為mid來分開序列，具有一定的隨機性。所以我們只能考慮極限情況，最壞情況時，即每次選的都是最大值或者最小值，則需要進行k次循環，T = O(n^2)。

?

算法三：BFPRT(線性查找算法)

BFPRT算法描述：

從某n個元素的序列中選出第k大（第k小）的元素，通過巧妙的分?析，BFPRT可以保證在最壞情況下仍為線性時間復雜度。該算法的思想與快速排序思想相似，當然，為使得算法在最壞情況下，依然能達到o(n)的時間復雜?度，五位算法作者做了精妙的處理。

算法步驟：

1.?將n個元素每5個一組，分成n/5(上界)組。

2.?取出每一組的中位數，任意排序方法，比如插入排序。

3.?遞歸的調用selection算法查找上一步中所有中位數的中位數，設為x，偶數個中位數的情況下設定為選取中間小的一個。

4.?用x來分割數組，設小于等于x的個數為k，大于x的個數即為n-k。

5.?若i==k，返回x；若i<k，在小于x的元素中遞歸查找第i小的元素；若i>k，在大于x的元素中遞歸查找第i-k小的元素。

終止條件：n=1時，返回的即是i小元素。

?

偽代碼：

int select_kth_smallest(list q, int k){ intput: q is a list, k is the number of which the kth smallest in list output: return the value of the k largest number in listbot <- 0top <- the size of qwhile bot < top doleft <- botright <- botindex <- choose_mid(bot, top)while right < top doif q[right] < index doleft <- left + 1temp <- q[right]q[right] <- q[left]q[left] <- tempendifright <- right + 1endwhileif left + 1 < k dobot <- left + 1else if left + 1 > k dotop = leftelse doreturn q[left]endif endwhilereturn -1 }int choose_mid(q, left, right){ input: q is a number list, left and right are the indexes of q indicating the range of choosing midian output: the median in range of (left, right)v <- [] // create a empty vectorwhile left + 5 < right domid <- selection(q[left : left+5])push mid in vleft <- left + 5endwhilemid <- selection(q[left : right])push mid in vreturn selection(v) }int selection(v){ input: v is a number vector output: return the midian in vsize <- the size of vfor a <- 1:size-1b <- atemp <- v[b]while b > 0 and temp < v[b-1] dov[b] <- v[b-1]b <- b - 1v[b] <- tempindex <- (size-1) // 2return v[index] }

代碼：

int select_kth_smallest(vector<int> q, size_t k); int choose_mid(vector<int>& q, int left, int right); int selection(vector<int> v);int select_kth_smallest(vector<int> q, size_t k){int bot = 0, top = q.size();while(bot < top){int left = bot, right = bot, i;int index = choose_mid(q, bot, top);while(right < top){if(q[right] < index){int temp = q[left];q[left] = q[right];q[right] = temp;left++;}if(q[right] == index)i = right;right++;}q[i] = q[left];q[left] = index;/*for(int a=0; a<q.size(); a++)cout<< q[a]<< ' ';cout<< endl;cout<< index<< endl;cout<< bot<< ' '<< top<< endl;cout<< left<< ' '<< right<< endl; */if(left+1 < k)bot = left + 1;else if(left+1 > k)top = left;elsereturn index;}return -1; }int choose_mid(vector<int>& q, int left, int right){vector<int> v;while(left+5 < right){int mid = selection(vector<int>(&q[left], &q[left+5]));v.push_back(mid);left += 5;}int mid = selection(vector<int>(&q[left], &q[right]));v.push_back(mid);return selection(v); }int selection(vector<int> v){int size = v.size();for(int a=1; a<size; a++){int b = a;int temp = v[b];while(b>0 && temp<v[b-1]){v[b] = v[b-1];b--;}v[b] = temp;}int mid = (size-1)/2;return v[mid]; }

算法分析：

在第三步選出x時，大于x的元素至少有3n/10 - 6個，在最差的情況下，第五步遞歸作用的元素個數是7n/10 + 6.可得遞歸表達式如下：
T(n) <= T(n/5) + T(7n/10 + 6) + O(n)

比起算法二，消除了中間數mid選取的隨機性干擾，使得在最差的情況下也是線性復雜度O（n）。

總結

以上是生活随笔為你收集整理的解决寻找第K小元素问题——三种不同的算法实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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