查找算法(2)、经典算法(8):从N个乱序数据中找出第K小的数

2017-01-03 19:15:14来源:CSDN作者:qcyfred人点击

第七城市

如何从N个乱序数据中,快速地找出第K小的数?

如果K接近0或者接近N,用选择排序,排几个应该就可以找到了。

如果K比较大呢?或者说,就是要找N个乱序数据中的中位数呢?

思路和快速排序很像。非常像。

Review:快速排序算法


现假设数组A,有N个元素。要快速地找出第K小的元素。

基本思想还是用递归去查找。当然,在查找的过程中,也是需要排序的。但只是粗略地排序。

关键问题还是找中轴变量pivor。把中轴变量排到它应该在的位置上。

这里涉及到一个排序。比pivor小的,都放在pivor的左边,大于或等于pivor的,都放在pivor的右边。

然后比较pId+1和K的大小。 // C++数组从0开始。

1. pId==K-1的话,返回A[pId]就好。当然不愿意承认这一点…

2. pId<K-1的话,说明第K小的数,还在由pivor一分为二的右半段,于是对右半段的数据继续查找。

3. pId>K-1的话,则要对左半段的数据继续查找。


下面贴上C++代码。

// 2017年1月3日12:31:22// 2017年1月3日12:46:49// 熟能生巧,背背背!#include <iostream>#include <algorithm>using namespace std;int findPivorIdx(int A[], int k, int low, int high) {	int pivor = A[low];	while (low<high)	{		while (A[high]>=pivor && low<high)		{			high--;		}		A[low] = A[high];		while (A[low]<pivor && low<high)		{			low++;		}		A[high] = A[low];	}	A[low] = pivor;	return low;}int findKMin(int A[],int k, int low, int high) {	if (low<high) // 继续查找	{		int pId = findPivorIdx(A,k,low,high);		if ((pId+1)==k) // 找到了		{			return A[pId];		}else if((pId+1)<k) { // 还在右边			return findKMin(A,k,pId+1,high); // 对右边递归		}else if((pId+1)>k){			return findKMin(A,k,low,pId-1); // 对左边递归		}	}	else { // 返回low		return A[low];	}}int main () {		const int N = 16;	int A[N] = {32,122,34,5,6,74,22,11,55,66,11,33,6,1,4,8};	int B[N];	cout<<"原始数据"<<endl;	for (int i = 0;i<N;i++)	{		cout<<A[i]<<" ";		B[i] = A[i];	}	cout<<"/n";	// 在sort后的数据中找	cout<<"排序好的数据"<<endl;	sort(B,B+N); // first, the one past last	for (int i = 0;i<N;i++)	{		cout<<B[i]<<" ";	}	cout<<"/n/n";	for (int i = 1;i<=N;i++)	{		cout<<"第"<<i<<"小的数是"<<B[i-1]<<"(正确的) "<<findKMin(A,i,0,N-1)<<" (我写的)"<<endl;	}	system("pause");	return 0;}
原始数据
32 122 34 5 6 74 22 11 55 66 11 33 6 1 4 8
排序好的数据
1 4 5 6 6 8 11 11 22 32 33 34 55 66 74 122

第1小的数是1(正确的) 1 (我写的)
第2小的数是4(正确的) 4 (我写的)
第3小的数是5(正确的) 5 (我写的)
第4小的数是6(正确的) 6 (我写的)
第5小的数是6(正确的) 6 (我写的)
第6小的数是8(正确的) 8 (我写的)
第7小的数是11(正确的) 11 (我写的)
第8小的数是11(正确的) 11 (我写的)
第9小的数是22(正确的) 22 (我写的)
第10小的数是32(正确的) 32 (我写的)
第11小的数是33(正确的) 33 (我写的)
第12小的数是34(正确的) 34 (我写的)
第13小的数是55(正确的) 55 (我写的)
第14小的数是66(正确的) 66 (我写的)
第15小的数是74(正确的) 74 (我写的)
第16小的数是122(正确的) 122 (我写的)

为了检验我的代码正确与否,我先对原始数据进行了排序。

结果表明,至少在这几个数中,我的代码还是正确的。


需要注意的是,pId是pivor在原始数据A中的第pId+1小的。

因为每次排序后,pivor会出现在排序后的正确位置上。(尽管两边的数内部顺序可能不一样,但这个pivor的位置一定对了。从小到大排)

递归调用的时候,尽管只是从A的一部分中去找,但是还是找的全局第K小的数。所以参数k一直没变。

最后,当low<high的时候,才去找。否则,也要有终止条件:return A[low]。这是必须有的终止条件。

写递归,一定要有递推式和终止条件!二者缺一不可。



第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台