数据结构与算法-排序
目录
十大经典排序算法
[!blue]
不稳定的排序算法有：快希选堆
- 快速排序
- 希尔排序
- 选择排序
- 堆排序
[!blue]
稳定性：排序后相等元素的相对次序保持不变，就是稳定的。典型追问场景是多字段排序：先按字段 A 排、再用稳定排序按字段 B 排，B 相等的记录仍保持 A 的次序。面试谈到任何一种排序，要能一口气说出四件事：核心思想（一两句话）、时间复杂度（最好 / 平均 / 最坏）、空间复杂度、稳定性及原因。
冒泡排序
核心思想
每一轮从头开始两两比较相邻元素，逆序就交换，一轮结束后当前未排序区间的最大值「冒泡」到区间末尾；重复 $n - 1$ 轮，每轮比较范围缩小一位。
实现要点
- 外层循环 $n - 1$ 轮，内层比较范围是
[0, n - 1 - i)，因为末尾i个元素已经就位。- 用一个
swapped标志记录本轮是否发生过交换，一轮无交换说明数组已经有序，可以提前退出——这也是冒泡最好情况能到 $O(n)$ 的原因。
代码实现
public class BubbleSort {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length < 2) {
return nums;
}
int n = nums.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums, j, j + 1);
swapped = true;
}
}
// 一轮没有任何交换，说明已经有序，提前退出
if (!swapped) {
break;
}
}
return nums;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
func bubbleSort(nums []int) {
n := len(nums)
for i := 0; i < n-1; i++ {
swapped := false
for j := 0; j < n-1-i; j++ {
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1], nums[j]
swapped = true
}
}
// 一轮没有任何交换，说明已经有序，提前退出
if !swapped {
break
}
}
}
复杂度与稳定性
- 时间复杂度：最好 $O(n)$（已有序，靠
swapped提前退出）；平均、最坏 $O(n^2)$。- 空间复杂度：$O(1)$，原地交换。
- 稳定性：稳定。比较用严格大于，相等的相邻元素不交换，相对次序不会被打乱。
选择排序
核心思想
每一轮从未排序区间中选出最小元素的下标，把它交换到已排序区间的末尾。与冒泡的区别是每轮至多做一次交换。
实现要点
- 内层循环只更新
minIndex，不搬元素；一轮扫描结束后再做一次交换。- 比较次数与数据是否有序无关，固定是 $\frac{n(n-1)}{2}$ 次，所以最好情况也快不起来。
代码实现
public class SelectionSort {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length < 2) {
return nums;
}
int n = nums.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
// 每轮只做一次交换
if (minIndex != i) {
swap(nums, i, minIndex);
}
}
return nums;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
func selectionSort(nums []int) {
n := len(nums)
for i := 0; i < n-1; i++ {
minIndex := i
for j := i + 1; j < n; j++ {
if nums[j] < nums[minIndex] {
minIndex = j
}
}
// 每轮只做一次交换
if minIndex != i {
nums[i], nums[minIndex] = nums[minIndex], nums[i]
}
}
}
复杂度与稳定性
- 时间复杂度：最好、平均、最坏都是 $O(n^2)$，比较次数固定。
- 空间复杂度：$O(1)$。
- 稳定性：不稳定。反例
[5, 5, 2]：第一轮 2 与第一个 5 交换，两个 5 的相对次序被破坏——不稳定的根源在于跨距离交换。
插入排序
核心思想
像摸牌一样，把当前元素插入到前面已排好序的区间中的正确位置：从后往前扫描已排序区间，比它大的元素整体后移一位，腾出位置放入。
实现要点
- 先把当前元素暂存到
cur，扫描过程做的是后移而不是交换，比逐次交换的写法少一半赋值。- 内层循环条件用严格大于
nums[j - 1] > cur：相等时停下、插在后面，稳定性正是由这一处保证。
[!blue]
面试加分点：插入排序在小规模或近乎有序的数据上非常快，所以工业级排序（如 JDK 的Arrays.sort）在小区间会切换成插入排序，作为快排 / 归并的优化。
代码实现
public class InsertionSort {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length < 2) {
return nums;
}
for (int i = 1; i < nums.length; i++) {
int cur = nums[i];
int j = i;
// 比 cur 大的元素整体后移一位，腾出插入位置
while (j > 0 && nums[j - 1] > cur) {
nums[j] = nums[j - 1];
j--;
}
nums[j] = cur;
}
return nums;
}
}
func insertionSort(nums []int) {
for i := 1; i < len(nums); i++ {
cur := nums[i]
j := i
// 比 cur 大的元素整体后移一位，腾出插入位置
for j > 0 && nums[j-1] > cur {
nums[j] = nums[j-1]
j--
}
nums[j] = cur
}
}
复杂度与稳定性
- 时间复杂度：最好 $O(n)$（近乎有序时内层几乎不移动）；平均、最坏 $O(n^2)$。
- 空间复杂度：$O(1)$。
- 稳定性：稳定。相等时内层循环停止，新元素插在同值元素之后。
归并排序
核心思想
分治：把数组从中点分成两半，递归地把左右两半分别排好序，再用双指针把两个有序数组合并成一个有序数组。
实现要点
- 递归终止条件是区间长度为 1（
left >= right），单元素天然有序。- 合并时比较必须写
<=：相等元素优先取左半部分，原有相对次序才能保留，这一个字符决定了归并的稳定性。- 合并需要一个与区间等长的临时数组，拷回原数组后本层结束。
[!blue]
面试对比点：归并是常见排序里唯一稳定的 $O(n \log n)$ 算法，代价是 $O(n)$ 额外空间；快排平均更快但不稳定、最坏 $O(n^2)$。链表排序首选归并（见下面 148 题），因为链表合并不需要额外数组。
代码实现
public class MergeSort {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length < 2) {
return nums;
}
mergeSort(nums, 0, nums.length - 1);
return nums;
}
private void mergeSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
private void merge(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int p = 0, p1 = left, p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
// 相等时取左边，保证稳定性
if (nums[p1] <= nums[p2]) {
temp[p++] = nums[p1++];
} else {
temp[p++] = nums[p2++];
}
}
while (p1 <= mid) {
temp[p++] = nums[p1++];
}
while (p2 <= right) {
temp[p++] = nums[p2++];
}
System.arraycopy(temp, 0, nums, left, temp.length);
}
}
func sortArray(nums []int) []int {
if len(nums) <= 1 {
return nums
}
mid := len(nums) / 2
left := sortArray(append([]int(nil), nums[:mid]...))
right := sortArray(append([]int(nil), nums[mid:]...))
return merge(left, right)
}
func merge(left, right []int) []int {
res := make([]int, 0, len(left)+len(right))
p1, p2 := 0, 0
for p1 < len(left) && p2 < len(right) {
// 相等时取左边，保证稳定性
if left[p1] <= right[p2] {
res = append(res, left[p1])
p1++
} else {
res = append(res, right[p2])
p2++
}
}
res = append(res, left[p1:]...)
res = append(res, right[p2:]...)
return res
}
复杂度与稳定性
- 时间复杂度：最好、平均、最坏都是 $O(n \log n)$——递归深度 $\log n$，每层合并总量 $O(n)$，且与输入是否有序无关。
- 空间复杂度：$O(n)$，合并需要临时数组（递归栈另有 $O(\log n)$）。
- 稳定性：稳定。相等元素合并时优先取左半部分，相对次序不变。
快速排序
核心思想
分治：每一轮选一个基准（pivot），通过 partition 把数组划分成「小于基准 基准 大于基准」，基准就落在了最终位置上，再递归处理左右两部分。
实现要点
- 下面的 partition 用挖坑法：把基准取出来形成一个「坑」，右指针找到比基准小的填进左边的坑，左指针找到比基准大的填进右边的坑，两指针相遇处就是基准的最终位置。
- 必须随机选基准并交换到最左端，否则升序 / 降序输入会退化为 $O(n^2)$。
- 扫描条件用严格比较
>和<：相等元素会被两个指针交替搬运、大致均分到两侧，避免全相等数组把划分卡成 1 : n-1。
[!blue]
为什么最坏是 $O(n^2)$、怎么避免？（面试必问）如果固定选第一个元素做基准，遇到已经有序（或逆序）的数组时，每次划分都是「0 个 : n-1 个」的极端不平衡，递归深度退化为 $n$ 层，每层扫描 $O(n)$，总复杂度 $O(n^2)$，递归栈也可能溢出。
三种避免手段：
- 随机化基准（面试首选，下面代码采用）：随机选一个位置和最左端交换，任何输入的期望复杂度都是 $O(n \log n)$；
- 三数取中：取首、中、尾三个元素的中位数做基准，专门克制近乎有序的输入；
三路划分（荷兰国旗）：把数组分成「小于 等于 大于」三段，等于段不再参与递归，应对大量重复元素的场景。
代码实现
public class QuickSort {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length < 2) {
return nums;
}
quickSort(nums, 0, nums.length - 1);
return nums;
}
private void quickSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
// 随机选基准并换到最左侧，避免有序输入退化为 O(n^2)
int index = left + (int) (Math.random() * (right - left + 1));
swap(nums, left, index);
int pivot = nums[left];
int i = left, j = right;
while (i < j) {
while (i < j && nums[j] > pivot) j--;
if (i < j) nums[i++] = nums[j];
while (i < j && nums[i] < pivot) i++;
if (i < j) nums[j--] = nums[i];
}
nums[i] = pivot;
quickSort(nums, left, i - 1);
quickSort(nums, i + 1, right);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
func sortArray(nums []int) []int {
if len(nums) <= 1 {
return nums
}
quickSort(nums, 0, len(nums)-1)
return nums
}
func quickSort(nums []int, left, right int) {
if left >= right {
return
}
// 随机选基准并换到最左侧，避免有序输入退化为 O(n^2)
index := rand.Intn(right-left+1) + left
nums[left], nums[index] = nums[index], nums[left]
pivot := nums[left]
i, j := left, right
for i < j {
for i < j && nums[j] > pivot {
j--
}
if i < j {
nums[i] = nums[j]
i++
}
for i < j && nums[i] < pivot {
i++
}
if i < j {
nums[j] = nums[i]
j--
}
}
nums[i] = pivot
quickSort(nums, left, i-1)
quickSort(nums, i+1, right)
}
复杂度与稳定性
- 时间复杂度：最好、平均 $O(n \log n)$；最坏 $O(n^2)$（划分持续极端不平衡，随机化后任何输入的期望都是 $O(n \log n)$）。
- 空间复杂度：$O(\log n)$，递归栈的平均深度；最坏 $O(n)$。
- 稳定性：不稳定。partition 时元素跨区间搬运，相等元素的相对次序会被打乱。
堆排序
[!blue]
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
核心思想
升序排序用大顶堆，分两步：先把整个数组原地调整成大顶堆；然后每轮把堆顶（当前最大值）与堆末尾交换、堆大小减一、再把新堆顶下沉（sift down）恢复堆性质，数组从后往前依次被填上最大值。
实现要点
- 建堆从最后一个非叶子节点
n / 2 - 1开始，自右向左、自下而上依次下沉，整体是 $O(n)$，比逐个插入建堆的 $O(n \log n)$ 更优。- 下沉时先在左右孩子中选较大者，只有孩子比自己大才交换并继续向下，否则立即停止。
- 下标关系要背熟：节点
k的左右孩子是2k + 1、2k + 2，父节点是(k - 1) / 2。
[!blue]
面试常考点：「第 k 大 / TopK」问题常用堆解（见 LeetCode 215），求第 k 大用小顶堆维护 k 个最大值即可，不必全量排序。
代码实现
public class HeapSort {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length < 2) {
return nums;
}
int n = nums.length;
// 建堆：从最后一个非叶子节点开始依次下沉
for (int i = n / 2 - 1; i >= 0; i--) {
siftDown(nums, i, n);
}
for (int j = n - 1; j > 0; j--) {
swap(nums, 0, j);
siftDown(nums, 0, j);
}
return nums;
}
private void siftDown(int[] nums, int k, int size) {
while (2 * k + 1 < size) {
int j = 2 * k + 1;
if (j + 1 < size && nums[j + 1] > nums[j]) j++;
if (nums[k] >= nums[j]) break;
swap(nums, k, j);
k = j;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
func heapSort(nums []int) {
n := len(nums)
// 建堆：从最后一个非叶子节点开始依次下沉
for i := n/2 - 1; i >= 0; i-- {
siftDown(nums, i, n)
}
for j := n - 1; j > 0; j-- {
nums[0], nums[j] = nums[j], nums[0]
siftDown(nums, 0, j)
}
}
func siftDown(nums []int, k, size int) {
for 2*k+1 < size {
j := 2*k + 1
if j+1 < size && nums[j+1] > nums[j] {
j++
}
if nums[k] >= nums[j] {
break
}
nums[k], nums[j] = nums[j], nums[k]
k = j
}
}
复杂度与稳定性
- 时间复杂度：最好、平均、最坏都是 $O(n \log n)$——建堆 $O(n)$，之后 $n - 1$ 轮下沉每次 $O(\log n)$。
- 空间复杂度：$O(1)$，堆直接建在数组上，原地排序。
- 稳定性：不稳定。堆顶与末尾元素跨距离交换，会越过中间的同值元素。
构造初始堆
堆排序过程图解
排序经典题目
912. 排序数组
思路：面试手写排序的标准题，主推随机化快排（写归并或堆排也可以，能说清取舍即可）。这道题的用例专门卡两个点：必须随机选基准，否则升序 / 降序用例直接把快排退化成 $O(n^2)$ 超时；partition 的扫描必须用严格比较
>和<，让相等元素被两个指针交替搬运、均分到两侧——如果写成>=、<=，遇到全部相等的用例，j每轮都会一路走到i，划分退化成 1 : n-1，同样 $O(n^2)$ 超时（随机化对全相等数组无效，选谁做基准都一样）。
class Solution {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length < 2) {
return nums;
}
quickSort(nums, 0, nums.length - 1);
return nums;
}
private void quickSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
// 随机选基准，避免有序用例退化为 O(n^2)
int index = left + (int) (Math.random() * (right - left + 1));
swap(nums, left, index);
int pivot = nums[left];
int i = left, j = right;
while (i < j) {
// 严格比较 > 和 <，让相等元素均分到两侧，避免全相等用例退化
while (i < j && nums[j] > pivot) j--;
if (i < j) nums[i++] = nums[j];
while (i < j && nums[i] < pivot) i++;
if (i < j) nums[j--] = nums[i];
}
nums[i] = pivot;
quickSort(nums, left, i - 1);
quickSort(nums, i + 1, right);
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
func sortArray(nums []int) []int {
if len(nums) <= 1 {
return nums
}
quickSort(nums, 0, len(nums)-1)
return nums
}
func quickSort(nums []int, left, right int) {
if left >= right {
return
}
// 随机选基准，避免有序用例退化为 O(n^2)
index := rand.Intn(right-left+1) + left
nums[left], nums[index] = nums[index], nums[left]
pivot := nums[left]
i, j := left, right
for i < j {
// 严格比较 > 和 <，让相等元素均分到两侧，避免全相等用例退化
for i < j && nums[j] > pivot {
j--
}
if i < j {
nums[i] = nums[j]
i++
}
for i < j && nums[i] < pivot {
i++
}
if i < j {
nums[j] = nums[i]
j--
}
}
nums[i] = pivot
quickSort(nums, left, i-1)
quickSort(nums, i+1, right)
}
- 时间复杂度：期望 $O(n \log n)$，随机化保证任何输入都不会稳定命中最坏情况。
- 空间复杂度：$O(\log n)$，递归栈的期望深度。
88. 合并两个有序数组
思路：
nums1尾部预留了空位，所以从后往前合并：三个指针分别指向nums1有效末尾、nums2末尾、nums1总末尾，每次把两者中较大的填到最后的空位。逆向填充不会覆盖nums1还没处理的元素，做到 $O(1)$ 额外空间（正向合并则需要临时数组）。收尾时nums2若有剩余要拷完；nums1有剩余则本来就在正确位置，不用处理。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (i >= 0 && j >= 0) {
// 从后往前填较大者，不会覆盖 nums1 未处理的元素
if (nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
while (j >= 0) {
nums1[k--] = nums2[j--];
}
}
}
func merge(nums1 []int, m int, nums2 []int, n int) {
i, j, k := m-1, n-1, m+n-1
for i >= 0 && j >= 0 {
// 从后往前填较大者，不会覆盖 nums1 未处理的元素
if nums1[i] > nums2[j] {
nums1[k] = nums1[i]
i--
} else {
nums1[k] = nums2[j]
j--
}
k--
}
for j >= 0 {
nums1[k] = nums2[j]
j--
k--
}
}
- 时间复杂度：$O(m + n)$，每个元素恰好被放置一次。
- 空间复杂度：$O(1)$，原地逆向填充。
21. 合并两个有序链表
思路：迭代 + 哑结点（dummy）。dummy 免去了对头结点的特判；双指针每次把值较小的节点接到结果链表尾部，循环结束后把未走完的那条链整体挂到尾部即可（它已有序，这也是链表合并比数组合并省空间的原因）。比较用
l1.val <= l2.val，相等时优先取l1，保持合并的稳定性。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
// 相等时优先取 l1，保持稳定性
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil {
// 相等时优先取 l1，保持稳定性
if l1.Val <= l2.Val {
cur.Next = l1
l1 = l1.Next
} else {
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
if l1 != nil {
cur.Next = l1
} else {
cur.Next = l2
}
return dummy.Next
}
- 时间复杂度：$O(m + n)$，两条链各遍历一次。
- 空间复杂度：$O(1)$（递归写法则是 $O(m + n)$ 栈空间）。
148. 排序链表
思路：题目要求 $O(n \log n)$ 时间，链表排序的面试标准解是归并排序——链表随机访问差，快排 / 堆排都不合适，而链表合并只改指针、不需要额外数组，正好规避了归并的空间短板。三步走：快慢指针找中点（注意
fast从head.next出发，偶数长度时slow停在中点偏左，断开后两半都不为空，递归才能收敛）；断链（slow.next = null，切成两半分别递归排序）；合并（复用 21 题的合并两个有序链表）。
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// fast 从 head.next 出发，保证偶数长度时 slow 停在中点偏左
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null;
return merge(sortList(head), sortList(mid));
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// fast 从 head.Next 出发，保证偶数长度时 slow 停在中点偏左
slow, fast := head, head.Next
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
mid := slow.Next
slow.Next = nil
return merge(sortList(head), sortList(mid))
}
func merge(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
cur.Next = l1
l1 = l1.Next
} else {
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
if l1 != nil {
cur.Next = l1
} else {
cur.Next = l2
}
return dummy.Next
}
- 时间复杂度：$O(n \log n)$，找中点加合并每层 $O(n)$，递归 $\log n$ 层。
- 空间复杂度：自顶向下递归 $O(\log n)$ 栈空间。进阶的 $O(1)$ 空间做法是自底向上归并：按长度 1、2、4… 迭代地两两合并子链表，面试口述思路即可。