參考博客：傳送門

在上面的博客中介紹了求序列第K大的幾種算法，感覺收益良多，其中最精巧的還是利用快速排序的思想O(n)查詢的算法。仔細學習以后我將其中的幾個實現了一下。

解法 1：

將亂序數組從大到小進行排序然后取出前K大，總的時間復雜度為O(nlogn)

解法 2：

利用選擇排序或交互排序，取出前K大，總的時間復雜度為O(nk)

解法 3：

借鑒快速排序的思想，復雜度近似為O(n)

#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;int kth_number(int *a,int l,int r,int k)
{if(r-l == 1) return a[l];int key=a[l];int index=l;for(int i=l+1;i<r;++i){if(a[i]>=key) continue;else{++index;swap(a[i],a[index]);}}swap(a[index],a[l]);if(r-index == k) return a[index];if(r-index-1 >= k) return kth_number(a,index+1,r,k);else return kth_number(a,l,index,k-r+index);
}

測試程序

#include<cstdio>
#include"Kth_number.h"using namespace std;int main()
{int n,k;const int MAXN=1005;int a[MAXN];printf("n="); scanf("%d",&n);printf("k="); scanf("%d",&k);if(k>n) k=n;printf("please input %d number:\n",n);for(int i=0;i<n;++i)scanf("%d",&a[i]);printf("the %dth number of array is %d\n",k,kth_number(a,0,n,k));return 0;
}

運行結果

解法 4：

借助堆排序的思想，將前K個數字彈出，復雜度為建立堆的O(4n)加上k次堆排序O(logn)為O(4n+klogn)

實現程序

#include<cstdio>
#include<cstdlib>
#include<climits>
#include<algorithm>
#include<sys/types.h>
#include<sys/wait.h>
#include<fcntl.h>
#include<unistd.h>using namespace std;void Adjust(int *a, int n, int i)
{int x = a[i];for(int k = i<<1; k <= n; k = k<<1){if(k+1 <= n && a[k] < a[k+1])++k;if(a[k] > x){a[i] = a[k];i = k;}else{break;}}a[i] = x;
}void MakeHeap(int *a, int n)
{for(int i = n/2;i > 0;--i){Adjust(a, n, i);}
}void HeapSort(int *a,int n,int k,int *ans)
{int m=n-k;for(int i = n; i > m; i--){swap(a[1], a[i]);Adjust(a, i-1, 1);}*ans = a[m+1];
}int main(int argc, char* argv[])
{int n;const int MAXN = 1024;scanf("%d", &n);int a[MAXN] = {0};for(int i = 1; i <= n; ++i){scanf("%d", &a[i]);}int k;scanf("%d", &k);if(k > n) k = n;MakeHeap(a, n);int ans;HeapSort(a, n, k, &ans);printf("ans=%d\n", ans);return 0;
}

測試結果

解法 5：

維護一個大小為k的小頂堆，對于數組中的每一個元素判斷與堆頂的大小，若堆頂較大，則不管，否則彈出堆頂，將當前值插入到堆中。時間復雜度O(4k+nlogk)

實現程序

#include<cstdio>
#include<cstring>using namespace std;void Adjust(int *a,int n,int i)
{int x=a[i];for(int k=i<<1;k<=n;k<<=1){if(k+1<=n && a[k]>a[k+1])++k;if(a[k]<x){a[i]=a[k];i=k;}else break;}a[i]=x;
}
void MakeHeap(int *a,int n)
{for(int i=n/2;i>0;--i){Adjust(a,n,i);}
}
int KthNumber(int *a,int n,int k)
{
//	int *b=new int[k];int b[1024];for(int i=1;i<=k;++i){b[i]=a[i];}MakeHeap(b,k);for(int i=k+1;i<=n;++i){if(a[i]>b[1]){b[1]=a[i];Adjust(b,k,1);}}return b[1];
}int main()
{int n,k;printf("n="); scanf("%d",&n);printf("k="); scanf("%d",&k);
//	int* a = new int[n];int a[1024]={0};for(int i=1;i<=n;++i)scanf("%d",&a[i]);printf("%d\n",KthNumber(a,n,k));
//	delete a;return 0;
}

測試結果

解法 6:

利用Hash保存數組中元素出現的次數，利用計數排序的思想，線性從大到小掃描中得到結果，時間復雜度為O(n)