快排函数Patiton来求解第K大的数
发布时间:2020-12-14 02:27:12 所属栏目:大数据 来源:网络整理
导读:利用快速排序的特点:第一遍排序会确定一个数的位置,这个数左边都比它大,右边都比他小(降序),当左边区间大于K时,说明我们求的第K大数在左边区间,这时我们可以舍弃右边区间,将范围缩小到左边区间从而重复上述过程,直到确定一个数的位置时,左边区间
利用快速排序的特点:第一遍排序会确定一个数的位置,这个数左边都比它大,右边都比他小(降序),当左边区间大于K时,说明我们求的第K大数在左边区间,这时我们可以舍弃右边区间,将范围缩小到左边区间从而重复上述过程,直到确定一个数的位置时,左边区间的小是K-1那么这个数字就是我们所求。 用于快速排序升序时,是使得左边的数都比pivot小,右边的数都比pivot数大。区别只在于左右查找时的条件。 下面贴出主要代码:
int patition(int *a,int start,int end) { int i = start; int j = end - 1; int x = a[i]; while (i < j) { while (i < j&&a[j] <= x)j--; if (i < j) a[i++] = a[j]; while (i < j&&a[i] >= x)i++; if (i < j) a[j--] = a[i]; } a[i] = x; return i; } int FindKthNumByPatition(int *a,int end,int k) { if (end < start) return a[start]; unsigned position = patition(a,start,end); if (position == k-1) return a[position]; else if (position < k-1 ) return FindKthNumByPatition(a,position+1,end,k ); else if (position >k-1 ) return FindKthNumByPatition(a,position,k); } 剑指offer版的在这里: int KthNumInArray(int *a,int length,int k) { if (a == NULL || length<0 || k>length) return -1; int start = 0,end = length - 1; int Index = patition(a,end); while (Index != k - 1) { if (Index > k - 1) { end = Index - 1; Index = patition(a,end); } else { start = Index + 1; Index = patition(a,end); } } int result = a[Index]; return result; } 再贴一个非递归的版本: #include <iostream> using namespace std; template <class T> int quick2_sort(T a[],int low,int high) { T temp=a[low]; int pos=low; int i=low,j=high; while(i<j) { while(i<j && a[j]>temp) j--; if(i<j) { a[pos]=a[j]; pos=j; } while(i<j && a[i]<temp) i++; if(i<j) { a[pos]=a[i]; pos=i; } } a[pos]=temp; return pos; } //利用快速排序的思想查找第K大的数值 //第一个参数代表要查找的数组 //第二个参数代表数组的长度 //第三个参数代表要查找第几大的元素 template <class T> T findkth(T a[],int n,int k) { int low=0,high=n-1; while(1) { int pos=quick2_sort(a,low,high); if(pos==n-k) return a[pos]; else if(pos<n-k) { low=pos+1; high=n-1; } else if(pos>n-k) { high=pos-1; low=0; } } } int main() { int a[11]={78934,234,65,32,543,354,567,3412,23,547,423}; cout<<findkth(a,11,4)<<endl; return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |