用快速排序的思想输出数组第k大的元素：
1 #include<iostream> 2 #include<algorithm> 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<j) 12 { 13 while(i<j && arr[j]<=key) j--; 14 arr[i]=arr[j]; 15 while(i<j && arr[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 <class T> 30 int partition(T a[],int low,int high) 31 { 32 T key=a[low]; 33 int i=low,j=high; 34 while(i<j) 35 { 36 while(i<j && a[j]>=key) j--; 37 a[i]=a[j]; 38 while(i<j && a[i]<=key) i++; 39 a[j]=a[i]; 40 } 41 a[i]=key; 42 return i; 43 } 44 45 //利用快速排序的思想查找第K大的数值 46 //第一个参数代表要查找的数组 47 //第二个参数代表数组的长度 48 //第三个参数代表要查找第几大的元素 49 //非递归 50 template <class T> 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) 59 { 60 low=pos+1; 61 high=n-1; 62 } 63 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<<a[i]<<" "; 78 cout<<endl; 79 sort(a,a+11); 80 for(int i=0;i<11;i++) cout<<a[i]<<" "; 81 cout<<endl; 82 83 for(int i=11;i>=1;i--) 84 cout<<findkth(b,0,10,i)<<" "; 85 cout<<endl; 86 87 for(int i=11;i>=1;i--) 88 cout<<findkth2(c,11,i)<<" "; 89 cout<<endl; 90 91 92 cout<<endl<<endl; 93 for(int i=0;i<11;i++) cout<<b[i]<<" "; 94 cout<<endl; 95 for(int i=0;i<11;i++) cout<<c[i]<<" "; 96 cout<<endl; 97 return 0; 98 }
参考：http://blog.csdn.net/guangwen_lv/article/details/39674241
利用快速排序的特点：第一遍排序会确定一个数的位置，这个数左边都比它大，右边都比他小（降序），当左边区间大于K时，说明我们求的第K大数在左边区间，这时我们可以舍弃右边区间，将范围缩小到左边区间从而重复上述过程，直到确定一个数的位置时，左边区间的小是K-1那么这个数字就是我们所求。右边同理。
能够使用这种方法的前提条件是：n个数不能重复。如果n个数中有重复，那么区间的大小不能保证就是第K大。可以用HASH判重来将重复的数据去掉。然后再使用上述方法。
也可阅读如下另一位网友的java代码：
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/9f887dfc374a 51 來源：简书 52 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。*/
