寻找最大的k个数 java_JAVA中寻找最大的K个数解法

这个题拿到之后首先会想到排序，排好序之后在选取选取最大的K个数。排序选择快速排序是个比较好的选择。

好了，让我们来进行第一个解法：快速排序

代码如下

复制代码 代码如下:

public static void quickSort(int[] arr, int start, int end) {

if (start < end) {

int key = arr[start];

int right = start;

int left = end;

while (right < left) {

while (right < left && arr[left] > key) {

left --;

}

if (right < left) {

arr[right] = arr[left];

}

while (right < left && arr[right] <= key) {

right ++;

}

if (right < left) {

arr[left] = arr[right];

}

}

arr[right] = key;

quickSort(arr, start, right-1);

quickSort(arr, left+1, end);

}

}

快速排序之后，数组会是有序的，上面的排序是从小到大的，所以我们输出应该是下面这样

复制代码 代码如下:

int k = 4;

for (int i=arr.length-1; i>=arr.length-k; i--) {

System.out.println(arr[i]+"  ");

}

。第一个解法已经好了，但是有没有更好的办法。

答案是有的！我们可以选择部分排序，接下来我们使用选择排序来做解决这个问题。

代码如下：

复制代码 代码如下:

public static int[] selectSortK(int[] arr, int k) {

if(arr == null || arr.length == 0) {

return null;

}

int[] newArr = new int[k];

List list = new ArrayList();//记录每次最大数的下标

for (int i=0; i

int maxValue = Integer.MIN_VALUE; //最大值

int maxIndex = i;

for (int j=0; j

if (arr[j] > maxValue && !list.contains(j) ) {

maxValue = arr[j];

maxIndex = j;

}

}

if (!list.contains(maxIndex)) {//如果不存在，就加入

list.add(maxIndex);

newArr[i] = maxValue;

}

}

return newArr;

}