寻找最大的K个数（二）：快排优化和二分搜索

（总要更好的，等你去发现）
如果对技术不感兴趣的，可以直接跳转到最后的题外话。写了一点点，支离破碎。也是从这个程序想到的一点点。
今天继续和大家聊寻找最大的k个数。
先来熟悉一下问题：
有很多个无序的数（我们这里假设为正整数），而且各不相等，怎么选出最大的k个数。
例如：2，5，7，1，3，9，3，6，7，8，5
最大的5个数为：7，9，6，7，8
昨天我们给出了两个解法：
快速排序和选择排序，文章详情：寻找最大的k个数：快排和选择（一）
今天我们继续。
回想一下快速排序，每次做完一次快速排序，数组s都会被分成两部分sa和sb。sb的每一个数都大于sa的每一个数。这时候会出现两种情况：
第一：sb.length >= k，这时候我们只需要关心sb数组即可，因为前k个最大的数都在sb中。
第二：sb.length < k，这时候前k个最大的数为sb加上sa数组中前k-sb.length个数。
下面这段代码，是在前面快速排序的基础上修改的。主要是一次快速排序后比较k和
sb数组的长度。
具体代码如下：
package com.xylx.utils.selectk;
/
* 优化快速排序，查找最大的ｋ个输
*/
public class optquicksortselectk {
public static void main(string[] args) {
int[] arr = constans.getlengtharr(100);
system.out.println("排序前：");
constans.printarr(arr);
optquicksort(arr, 0, arr.length-1, constans.k);
system.out.println("排序后:");
constans.printarr(arr);
system.out.println("排序是否正确: " constans.isok(arr));
constans.selectk(arr);
}
public static void optquicksort(int[] arr, int start, int end, int k) {
int left = start;
int right = end;
int key = arr[left];
while (left < right) {
while (left<right && arr[right] > key) {
right –;
}
if (left < right) {
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left ;
}
while (left<right && arr[left] < key) {
left ;
}
if (left < right) {
int tmp = arr[right];
arr[right] = arr[left];
arr[left] = tmp;
right–;
}
}
if (start < left-1) {
int rightlength = end – right 1;
system.out.println("rightlength=" rightlength " k=" k);
if (rightlength < k) { //右边数组小于需要的ｋ数
optquicksort(arr, start, left-1, k-rightlength); //需要左边数组k-rightlength个最大的数
}
}
if (right 1 < end) {
int rightlength = end – right 1;
if (rightlength > k) {
optquicksort(arr, right 1, end, k);
}
}
}
}
上面这段代码能大大降低排序的次数。
寻找前k个最大数，也就是选择第k大的数。
如果数组s的中最大值为max，最小值为min。那么第k大的值vk一定满足下面的关系：
min<=vk<=max。
我们从中间值开始找起，mid=(min max)/2。查找数组s中所有>=mid的数的个数total。这时候也会出现两种情况：
第一：total>=k, 证明查找出来的数比k多，我们需要增加mid的值，也就是min=mid。
第二：total<k，证明查找出来的数比k少，我们需要减少max的值，也就是max=mid。
这样不断循环，直到max-min <= 1。
代码如下：
package com.xylx.utils.selectk;
import java.util.arraylist;
import java.util.list;
/
*/
public class binsearchselectk {
public static void main(string[] args) {
int[] arr = constans.getlengtharr(100);
constans.printarr(arr);
selectk(arr);
}
public static void selectk(int[] arr) {
list<integer> result = getmaxmin(arr);
int max = result.get(0);
int min = result.get(1);
while (max – min > 1) {
int mid = (max min)/2;
int total = getgttotal(arr, mid);
if (total >= constans.k) {
min = mid;
} else {
max = mid;
}
}
system.out.println("min=" min " max=" max);
printk(arr, min);
}
private static void printk(int[] arr, int min) {
int index = 0;
system.out.println("最大的k个数:");
for (int i=0; i<arr.length; i ) {
if (arr[i] > min) {
system.out.print(arr[i] " ");
index ;
}
}
for (int i=0; i<(constans.k-index); i ) {
system.out.print(min " ");
}
}
/
* 查找数组中大于等于mid值大的数的个数
* @param arr
* @param mid
* @return
*/
public static int getgttotal(int[] arr, int mid) {
int total = 0;
for (int i=0; i<arr.length; i ) {
if (arr[i] >= mid) {
total ;
}
}
return total;
}
/
* 寻找数组中最大值和最小值
* @param arr
* @return 0:最大　1:最小
*/
public static list<integer> getmaxmin(int[] arr) {
list<integer> result = new arraylist<integer>();
if (arr == null || arr.length < 1) {
return result;
}
int max = integer.min_value;
int min = integer.max_value;
for (int i=0; i<arr.length; i ) {
if (a

中国生活O2O十五年沉浮录
备案申请退回咨询-备案平台
新人对于域名注册商该怎么去选择？
阿里云服务器必须进行备案吗
3大主流视频平台的VIP会员成长体系！
腾讯云服务器镜像还原
怒江云服务器租用购买
阿里云怎么购买高防服务器