• | | time complexity | space complexity | 思想 | stability | | :--- | :--- | :--- | :--- | :--- | | merge sort | O(nlogn), 最好最坏都 O(nlogn) | O(n), 额外数组 | 先局部有序 后全局有序 (分成两部分分别排序再合并) | stable | | quick sort | O(nlogn), 平均复杂度O(nlogn), 最坏-完全逆序 O(n^2) | O(1), in-place | 先全局有序 后局部有序 (用partition分为左右) | unstable | | heap sort | O(nlogn) | O(n) | extract max / min | unstable |