常见排序算法

排序算法全景

稳定性：相等的元素排序后，原有的相对顺序是否保持。

插入排序

思路：维护一个已排序的前缀，每次将新元素插入到前缀中的正确位置。类比整理扑克牌。

void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];     // 待插入的元素
        int j = i - 1;
        // 向左移动，为 key 腾出位置
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;     // 插入到正确位置
    }
}

优势：对近乎有序的数组，插入排序近乎 O(n)，实际性能很好。很多语言在小数组（长度 < 16）时会用插入排序代替快速排序。

快速排序

核心思想：选取一个基准元素（pivot），将数组分为"比 pivot 小"和"比 pivot 大"两组，然后递归排序两组。

void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivotIdx = partition(arr, left, right);
    quickSort(arr, left, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, right);
}

// 双指针分区（Lomuto 方案，以末尾元素为 pivot）
int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;              // i 是小于 pivot 部分的右边界
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);       // 把小的放左边
        }
    }
    swap(arr, i + 1, right);       // pivot 放到中间
    return i + 1;
}

void swap(int[] arr, int i, int j) {
    int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
}

arr = [3, 6, 8, 10, 1, 2, 1], pivot = arr[6] = 1
i = -1
j=0: arr[0]=3 > 1，不交换
j=1: arr[1]=6 > 1，不交换
j=2: arr[2]=8 > 1，不交换
j=3: arr[3]=10 > 1，不交换
j=4: arr[4]=1 ≤ 1，i=0，swap(0,4) → [1, 6, 8, 10, 3, 2, 1]
j=5: arr[5]=2 > 1，不交换
swap(1, 6) → [1, 1, 8, 10, 3, 2, 6]
返回 1（pivot 在下标 1）

随机化：为避免有序数组导致 O(n²) 退化，实际中随机选取 pivot：

// 在 partition 开头加：
int randIdx = left + (int)(Math.random() * (right - left + 1));
swap(arr, randIdx, right);

快速选择（第 K 大/小）

快排的 partition 可以用于在 O(n) 平均时间内找第 K 小的元素（无需完整排序）：

int findKthSmallest(int[] nums, int k) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int pivot = partition(nums, left, right);
        if (pivot == k - 1) return nums[pivot];
        else if (pivot < k - 1) left = pivot + 1;
        else right = pivot - 1;
    }
    return -1;
}

归并排序

核心思想：分治——将数组分为两半，分别排序，然后合并两个有序数组。

int[] mergeSort(int[] arr) {
    if (arr.length <= 1) return arr;
    int mid = arr.length / 2;
    int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
    int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
    return merge(left, right);
}

int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) result[k++] = left[i++];  // ≤ 保证稳定
        else result[k++] = right[j++];
    }
    while (i < left.length) result[k++] = left[i++];
    while (j < right.length) result[k++] = right[j++];
    return result;
}

归并排序的优势：

• 稳定：相等元素保持原顺序（快排不稳定）
• 最坏 O(n log n)：不受输入数据影响（快排最坏 O(n²)）
• 适合链表：链表的归并只需修改指针，无需额外数组

应用：逆序对计数

归并排序的 merge 过程恰好可以统计逆序对（i < j 但 arr[i] > arr[j] 的对数）：

int countInversions(int[] arr) {
    // 在 merge 步骤，当选 right[j] 时，left 中剩余的所有元素都与 right[j] 构成逆序对
    // 此时加 (leftLen - i) 即可
}

堆排序

核心思想：利用堆（大顶堆）排序：先建堆，再反复提取堆顶（最大值）放到末尾。

void heapSort(int[] arr) {
    int n = arr.length;
    // 1. 建大顶堆（从最后一个非叶节点开始向上 heapify）
    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
    // 2. 反复提取堆顶，放到末尾
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);        // 堆顶（最大值）放到末尾
        heapify(arr, i, 0);     // 重新维护堆（堆大小缩小 1）
    }
}

// 以 i 为根，对大小为 n 的子树做 heapify（下沉）
void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1, right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, n, largest);  // 递归向下调整
    }
}

非比较排序

当元素范围有限时，可以突破 O(n log n) 的比较排序下界，实现 O(n) 线性排序。

计数排序

void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int[] count = new int[max + 1];
    for (int x : arr) count[x]++;          // 统计频次
    int idx = 0;
    for (int val = 0; val <= max; val++) {
        while (count[val]-- > 0) arr[idx++] = val; // 按频次填回
    }
}

适用：元素范围 [0, k] 较小时（k = O(n)），时间空间均 O(n + k)。

Java 内置排序

Arrays.sort(arr);           // 基本类型：双轴快排（原地，不稳定）
Arrays.sort(objArr);        // 引用类型：TimSort（稳定，归并+插入）

// 自定义排序（只能用对象数组）
Integer[] nums = {3, 1, 2};
Arrays.sort(nums, (a, b) -> b - a);   // 降序

// 对象排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  // 按第一列升序

注意：Arrays.sort 对 int[] 使用双轴快排（不稳定），对对象数组使用 TimSort（稳定）。要对基本类型稳定排序，需转换为包装类数组。

如何选择排序算法？

数据量小（< 20）    → 插入排序（简单，常数因子小）
数据近乎有序        → 插入排序
需要稳定排序        → 归并排序（或 Java 的 Arrays.sort 对象版）
一般情况           → 快速排序（随机化，实际最快）
不能用额外空间      → 堆排序（O(1) 空间，O(n log n) 保证）
元素范围有限        → 计数排序 / 基数排序

小结

三大 O(n log n) 算法的本质区别：

系统底层中快排和归并是应用最广泛的，要能手写 partition 和 merge。