1 #include 2 #include 3 using namespace std; 4 5 //递归实现:返回数组第k大的值.数组下标区间是[begin,end].其中数组假定n个元素，则k的值在区间[1,n]. 6 //能够使用这种方法的前提条件是：n个数不能重复。如果n个数中有重复，那么区间的大小不能保证就是第K大。 7 int findkth(int* arr, int begin, int end, int k) 8 { 9 int key=arr[begin]; 10 int i=begin,j=end;11 while(i =key) i++;16 arr[j]=arr[i];17 }18 arr[i]=key;19 20 //递归的结束条件为某一记录刚好划分到第k个位置21 //由于数组从0开始，所以需要加1了22 if (i == k-1)return arr[i];23 else if (i < k-1) return findkth(arr, i+1, end, k);24 else return findkth(arr, begin, i-1, k);25 }26 27 28 //只做了一轮划分，没有递归完成快速排序.返回的是划分的下标。数组a[]下标区间[low,high]29 template 30 int partition(T a[],int low,int high) 31 {32 T key=a[low];33 int i=low,j=high; 34 while(i =key) j--;37 a[i]=a[j];38 while(i 51 T findkth2(T a[],int n,int k)52 {53 int low=0,high=n-1;54 while(1)55 {56 int pos=partition(a,low,high);57 if(pos==n-k) return a[pos];58 else if(pos n-k)64 {65 high=pos-1;66 low=0;67 }68 }69 }70 71 int main() 72 {73 int a[11]={ 78934,234,65,32,543,354,567,3412,23,547,423};74 int b[11]={ 78934,234,65,32,543,354,567,3412,23,547,423};75 int c[11]={ 78934,234,65,32,543,354,567,3412,23,547,423};76 77 for(int i=0;i<11;i++) cout< <<" ";78 cout< =1;i--)84 cout< <<" ";85 cout< =1;i--)88 cout< <<" ";89 cout<
利用快速排序的特点：第一遍排序会确定一个数的位置，这个数左边都比它大，右边都比他小（降序），当左边区间大于K时，说明我们求的第K大数在左边区间，这时我们可以舍弃右边区间，将范围缩小到左边区间从而重复上述过程，直到确定一个数的位置时，左边区间的小是K-1那么这个数字就是我们所求。右边同理。
1 /** * Created with IntelliJ IDEA. 2 * User: hqtc 3 * Date: 16-3-22 4 * Time: 下午9:52 5 * To change this template use File | Settings | File Templates. 6 */ 7 public class QuickSort{ 8 9 private int getSeparatorIndex(int[] nums, int low, int high) {10 int k = nums[low];11 while (low < high) {12 while (k < nums[high] && low < high) {13 high--;14 }15 if (low < high)16 nums[low++] = nums[high];17 while (k > nums[low] && low < high) {18 low++;19 }20 if (low < high)21 nums[high--] = nums[low];22 }23 nums[low] = k;24 return low;25 }26 27 public void sort(int num[], int low, int high) {28 if (low < high) {29 int sepIndex = getSeparatorIndex(num, low, high);30 sort(num, low, sepIndex - 1);31 sort(num, sepIndex + 1, high);32 }33 }34 35 public int findKthMax(int arr[], int k, int left, int right) {36 int sepIndex = getSeparatorIndex(arr, left, right);37 if (k == arr.length - sepIndex) {38 return arr[sepIndex];39 } else {40 if (k > arr.length - sepIndex) {41 return findKthMax(arr, k, left, sepIndex - 1);42 } else {43 return findKthMax(arr, k, sepIndex + 1, right);44 }45 }46 }47 }48 49 /*作者：环球探测50 链接：http://www.jianshu.com/p/9f887dfc374a51 來源：简书52 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/