此題目，需要用到快速排序里的劃分數組操作：
快排參考：https://blog.csdn.net/qq_21201267/article/details/81516569#t2

先選取一個合適的哨兵（三數取中法）

將數組分成三部分【小于哨兵的】【哨兵】【大于等于哨兵的】

然后看哨兵的下標+1 == K嗎？等于就返回哨兵，不等則在一側遞歸調用該劃分方法

復雜度：平均情況下，遍歷一次數組找到哨兵是n，下一次就是n/2，最后到1，中間最多需要k次（k=lg₂n）
等比數列求和：n+n/2+n/4+n/8+…+1

所以復雜度為O(n)

代碼實現

/*** @description: 尋找第K大的元素* @author: michael ming* @date: 2019/4/13 13:02* @modified by: */ #include <iostream> #include <time.h> #include <random> #include "shellsort.cpp" using namespace std; void printArr(int* arr, size_t N) //打印數組 {for(int i = 0; i < N; ++i){cout << arr[i] << " ";}cout << endl; } void generateArr(int* arr, size_t N) //生成隨機數組 {srand((unsigned)time(NULL));for(int i = 0; i < N; ++i)arr[i] = rand()%100000; } void selectMiddle(int *arr, size_t left, size_t right) //三數取中，并挪至首位 {size_t mid = left + (right-left)/2;if(arr[mid] > arr[right])swap(arr[mid], arr[right]);if(arr[left] > arr[right])swap(arr[left], arr[right]);if(arr[mid], arr[left])swap(arr[mid], arr[left]); } int findkthelem(int *arr, size_t N, size_t K, size_t left, size_t right) {selectMiddle(arr, left, right);int Pval = arr[left];size_t Pindex = left, i = left, j = right;while(i < j) //將哨兵挪至中間{while(i < j && arr[j] > Pval) //以下兩個while的順序不可更換！！！哨兵在左邊，先從右邊開始比j--;swap(arr[i],arr[j]);while(i < j && arr[i] <= Pval)i++;swap(arr[i],arr[j]);}Pindex = i; //哨兵下標if(i+1 == K)return arr[i];else if(i+1 < K && right-Pindex > 0)return findkthelem(arr, right-Pindex, K, Pindex+1,right);else if(i+1 > K && Pindex-left > 0)return findkthelem(arr, Pindex-left, K, left, Pindex-1); } int main() {size_t N, K;cout << "請輸入正整數N：程序將生成隨機數組。" ;cin >> N;int arr[N];generateArr(arr, N);printArr(arr, N);cout << "請輸入K：程序將查找第K大的元素。";while(true){cin >> K;if(K > 0 && K <= N)break;cout << "K超過N了，或者為0" << endl;continue;}shellsort(arr, N);cout << "排序后數組是：" << endl;printArr(arr, N);cout << "第" << K << "大的元素是：" << findkthelem(arr,N,K,0,N-1) << endl;return 0; }

總結

以上是生活随笔為你收集整理的算法--排序--寻找数组内第K大的元素的全部內容，希望文章能夠幫你解決所遇到的問題。

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