第k大元素代码,C代码库,德仔网

代码语言

代码分类

【C】第k大元素

作者:独步天下 / 发布于2013/10/11/ 687

这个求第k大元素的程序是根据快速排序改编的。。。始终检索第n-k个位置所在的段。。不过复杂度不是O(n)。。回头再分享复杂度为O（n）的算法实现


	#include "stdafx.h"
	#include "iostream"
	#include "windows.h"
	using namespace std;
	#define N 10
	void main()
	{
	int num[N];
	int low,hight,plow,phight,kelement=0,k,temp;
	cout<<"Input the "<<N<<" numbers:";
	for (int i=0;i<N;i++)
	{cin>>num[i];}
	cout<<"Input the K:";
	cin>>k;
	plow=0;
	phight=N-1;
	while (kelement!=N-k)
	{
	 low=plow;
	 hight=phight;
	 while (low!=hight)
	 {
	 if (num[low]>num[hight])
	 {
	 temp=num[low];
	 num[low]=num[hight];
	 num[hight]=temp;
	 low++;
	 }
	 else
	 {hight--;}
	 }
	 kelement=low;
	 if (low<N-k)
	 {plow=low+1;}
	 else
	 {phight=low-1;}

	}
	cout<<"The k max element is: "<<num[N-k]<<endl;
	Sleep(10000);
	}

试试其它关键字

　第k大元素　

同语言下

可能有用的

独步天下贡献的其它代码(2)