這個題拿到之後首先會想到排序，排好序之後在選取選取最大的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<Integer> list = new ArrayList<Integer>();//記錄每次最大數的下標
for (int i=0; i<k; i++) {
int maxValue = Integer.MIN_VALUE; //最大值
int maxIndex = i;
for (int j=0; j<arr.length; 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;
}