|
题目：有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。
测试样例：
[1,3,5,2,2],5,3
返回：
2
方法一：
利用冒泡排序，进行k趟排序，即可查找到第k大的数（每趟冒泡排序都寻找当前序列中的最大值）
方法二：
利用选择排序，进行k趟排序，即可查找到第k大的数（每趟选择排序都寻找当前序列中的最大值）
方法三：
利用快速排序的思想，只需找到第k大的数，不必把所有的数排好序。
思路分析：先任取一个数（找到基准值），把比它大的数移动到它的右边，比它小的数移动到它的左边。移动完成一轮后，看该数的下标（从0计数），如果刚好为length-k，则它就是第k大的数（因为移动后的基准值左边都是比它小的数，右边都是比他大的数，右边若没有元素，则说明当前基准值是第1大元素，若右边有1个元素，则说明当前基准值是第2大元素，若右边有2个元素，则说明当前基准值是第3大元素......即当前基准值右边有k-1个元素，或当前基准值的下标为length-k，则说明当前基准值是第k大元素），如果小于length-k，说明第k大的数在它右边，如果大于length-k，则说明第k大的数在它左边，取左边或者右边继续进行移动，直到找到。
代码实现：
package com.csu.marden;
public class Demo6 {
public static void main(String[] args) {
int [] arr={3,1,2,5,4,7,6};
int k=2;
System.out.println(quickSort(arr, 0, arr.length-1, k));
}
//使用快速排序的原理，寻找第k大的数
public static int quickSort(int [] arr,int start,int end,int k){
//递归结束条件
if(start>end){
return -1;
}
int i=start;
int j=end;
int base=arr[start];
while(i<j){
while(i<j && arr[j]>=base){
j--;
}
while(i<j && arr[i]<=base){
i++;
}
if(i<j){
int temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
//此时i=j，交换base元素的位置
arr[start]=arr[i];
arr[i]=base;
if(i==arr.length-k){
//查找到第k大的数字
return arr[i];
}
else if(i<arr.length-k){
//在基准值右边寻找
return quickSort(arr, i+1, end, k);
}else{
//在基准值左边寻找
return quickSort(arr, start, i-1, k);
}
}
}
方法四：
针对海量数据，数据量太大无法加载到内存，若采用上述方法，必须将所有数据加载到内存进行排序，尤其是快速排序，使用递归需要额外的空间开销，此时可以使用堆排序，利用较少的空间即可找到第k大的数。
思路分析：
寻找第k大的数，可以在内存中构建一个包含k个数的小顶堆（堆顶元素是最小值），然后从外存中第k+1个数据开始，依次与小顶堆的堆顶元素进行比较，若该数比堆顶元素大，则用该数替换堆顶元素，并重新构建小顶堆，重复上述操作，直到外存中的所有数据遍历完成，此时小顶堆的堆顶元素即为第k大的数。
| 
转播
