問題背景

班里有 $m$ 位學生，共計劃組織 $n$ 場考試。給你一個下標從 $0$ 開始、大小為 $m\times n$ 的整數矩陣 $score$，其中每一行對應一位學生，而 $score[i][j]$ 表示第 $i$ 位學生在第 $j$ 場考試取得的分數。矩陣 $score$ 包含的整數 互不相同 。
另給你一個整數 $k$。請你按第 $k$ 場考試分數從高到低完成對這些學生（矩陣中的行）的排序。
返回排序后的矩陣。

數據約束

• $m=score.length$
• $n=score[i].length$
• $1\le m,n\le 250$
• $1\le score[i][j]\le 105$
• $score$ 由 不同 的整數組成
• $0\le k<n$

解題過程

根據某個標準帶著整個數組排序，可以當作模板記下來。
題目保證待排序的元素不重復，那就可以完全不考慮穩定性的問題。
寫一下在其它算法中常用 $O(NlogN)$ 量級的簡單做法，再把三種常用排序都實現一下當作練習好了。

具體實現

調用 API

class Solution {public int[][] sortTheStudents(int[][] score, int k) {Arrays.sort(score, (o1, o2) -> o2[k] - o1[k]);return score;}
}

歸并排序 - 遞歸版

class Solution {// 二維數組最大長度為 250，開長為 300 的輔助數組就夠了private static final int MAX_N = 300;private static final int[][] temp = new int[MAX_N][];private int k;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;mergeSort(score, 0, score.length - 1);return score;}// 歸并操作，入參改成二維數組private void merge(int[][] arr, int left, int mid, int right) {int index1 = left, index2 = mid + 1, index = left;while(index1 <= mid && index2 <= right) {// 除了收集元素的標準不一樣，其它都可以不變temp[index++] = arr[index1][k] > arr[index2][k] ? arr[index1++] : arr[index2++];}while(index1 <= mid) {temp[index++] = arr[index1++];}while(index2 <= right) {temp[index++] = arr[index2++];}System.arraycopy(temp, left, arr, left, right - left + 1);}// 歸并排序，入參改成二維數組private void mergeSort(int[][] arr, int left, int right) {if(left == right) {return;}int mid = left + ((right - left) >>> 1);mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}

歸并排序 - 非遞歸版

class Solution {// 二維數組最大長度為 250，開長為 300 的輔助數組就夠了private static final int MAX_N = 300;private static final int[][] temp = new int[MAX_N][];private int k;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;mergeSort(score);return score;}// 歸并操作，入參改成二維數組private void merge(int[][] arr, int left, int mid, int right) {int index1 = left, index2 = mid + 1, index = left;while(index1 <= mid && index2 <= right) {// 除了收集元素的標準不一樣，其它都可以不變temp[index++] = arr[index1][k] > arr[index2][k] ? arr[index1++] : arr[index2++];}while(index1 <= mid) {temp[index++] = arr[index1++];}while(index2 <= right) {temp[index++] = arr[index2++];}System.arraycopy(temp, left, arr, left, right - left + 1);}// 歸并排序，入參改成二維數組private void mergeSort(int[][] arr) {int n = arr.length;for(int left, mid, right, step = 1; step < n; step <<= 1) {left = 0;while(left < n) {mid = left + step - 1;if(mid >= n - 1) {break;}right = Math.min(left + (step << 1) - 1, n - 1);merge(arr, left, mid, right);left = right + 1;}}}
}

隨機快速排序

class Solution {private int k;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;quickSort(score, 0, score.length - 1);return score;}// 交換操作，入參改成二維數組private void swap(int[][] arr, int i, int j) {int[] temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static int first, last;// 隨機快排，入參改成二維數組private void quickSort(int[][] arr, int left, int right) {if (left >= right) {return;}int pivot = arr[left + (int) (Math.random() * (right - left + 1))][k];partition(arr, left, right, pivot);quickSort(arr, left, first - 1);quickSort(arr, last + 1, right);}// 劃分操作，入參改成二維數組public void partition(int[][] arr, int left, int right, int pivot) {first = left;last = right;int cur = left;while (cur <= last) {if (arr[cur][k] == pivot) {cur++;// 修改區域標準，較大的數往數組左側交換} else if (arr[cur][k] > pivot) {swap(arr, first++, cur++);} else {swap(arr, cur, last--);}}}
}

堆排序

class Solution {private int k;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;heapSort(score);return score;}// 交換操作，入參改成二維數組private void swap(int[][] arr, int i, int j) {int[] temp = arr[i];arr[i] = arr[j];arr[j] = temp;}private void downAdjust(int[][] arr, int cur, int size) {int child = 2 * cur + 1;while (child < size) {// 修改確定修改目標的條件，用小根堆來完成排序，就能得到從大到小的結果int target = child + 1 < size && arr[child + 1][k] < arr[child][k] ? child + 1 : child;target = arr[target][k] < arr[cur][k] ? target : cur;if (target == cur) {break;}swap(arr, target, cur);cur = target;child = 2 * cur + 1;}}// 建堆操作，入參改成二維數組private void buildHeap(int[][] arr) {int n = arr.length;for (int i = n - 1; i >= 0; i--) {downAdjust(arr, i, n);}}// 堆排序，入參改成二維數組private void heapSort(int[][] arr) {buildHeap(arr);int size = arr.length;while (size > 0) {swap(arr, 0, --size);downAdjust(arr, 0, size);}}
}

總結梳理

Java 中的排序 API 的實現是 Tim Sort，大體上可以理解為在數據量較小的情況下使用 插入排序，通常使用歸并排序。這里表現出來的效率不如直接實現的歸并排序，猜想是因為整體數據量不是很大，在某些樣例上被忽悠使用了效率不是那么高的算法。
歸并排序 能夠保證時間復雜度在 $O(NlogN)$ 這個量級的同時，算法本身是穩定的，是有必要自己實現排序算法時的首選，只需要考慮開輔助數組會不會影響效率。
快速排序 不僅需要額外的系統棧空間，還不穩定。它有時會成為面試時手撕算法的考題，需要好好掌握。
堆排序 是一種原地算法，但是不穩定，所以通常不是一個好的排序算法的選擇。但是堆本身能夠維護一系列元素中的最大值或者最小值，是一種非常好用的數據結構。