程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 從一個序列中獲取前K大的數的一種方法

從一個序列中獲取前K大的數的一種方法

編輯:C++入門知識

從一個序列中獲取前K大的數的一種方法


這個方法是利用快速排序的。在快速排序中,得到中間元素(pivot)之後,比較中間元素之前的元素個數和K的大小關系,從而確定後面該往哪個方向繼續遞歸。如果中間元素前面的元素個數等於K,那就停止遞歸過程;如果中間元素前面元素個數小於K,那就再中間元素後面進行遞歸;否則就往中間元素前面進行遞歸。這樣最終得到的是沒有排序的前K大的元素,這樣再對前K個元素進行一次真正的快速排序。這樣就能得到排好序的前K大元素。我隨機生成了一個100000個整型數據的文件進行測試,求前10000個元素。這樣做用了0.984s,然後如果直接用快速排序對整個序列進行快速排序,再取前10000個的話,用了1.05。這在某種程度上優化了這個問題。

#include
#include
#include
#include
#include
#include
#include
using namespace std;
template
class Quicksort
{
	inline int static partition(elem a[],int l,int r,elem& pivot)
	{
		do
		{
			while(a[++l]=j) return ;
  		int pivotindex=(i+j)/2;
  		swap(a[pivotindex],a[j]);
  		int k=partition(a,i-1,j,a[j]);
  		swap(a[k],a[j]);
  		int tem=k-i;
 		 if(tem==n||tem==n-1) return ;
  		else if(temn) TopN(a,i,k-1,n);
 	}
};
int a[100005];
int main()
{
 
	clock_t start=clock();
 	freopen("rand.txt","r",stdin);
 	for(int i=0;i<100000;i++) scanf("%d",&a[i]);
 	Quicksort::TopN(a,0,99999,10000);
 	Quicksort::sort(a,0,9999);
 	for(int i=0;i<9999;i++) printf("%d ",a[i]);
 	printf("\n");
 	cout<<"time used:"<<(double)(clock()-start)/CLOCKS_PER_SEC<<"s"<

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved