本文主要是介绍快排函数Patiton来求解第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 start,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, start, 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, start, end);while (Index != k - 1){if (Index > k - 1){end = Index - 1;Index = patition(a, start, end);}else{start = Index + 1;Index = patition(a, start, 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;
}这篇关于快排函数Patiton来求解第K大的数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
