← 返回学习路线

SYSTEM

排序

八股1.4 排序system
src/content/notes/system/排序.md

1.4 排序

快排(partition + 代码)

选基准、把小于基准的放左、大于放右,再对左右子区间递归。

class Solution {
    public void quickSort(int[] nums, int l, int r) {
        if (l >= r) return;
        int p = partition(nums, l, r);
        quickSort(nums, l, p - 1);
        quickSort(nums, p + 1, r);
    }

    private int partition(int[] nums, int l, int r) {
        int pivot = nums[l];
        while (l < r) {
            while (l < r && nums[r] >= pivot) r--;
            nums[l] = nums[r];
            while (l < r && nums[l] <= pivot) l++;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }
}

归并排序(分治 + 代码)

分到单元素再两两合并,合并时借助临时数组。

class Solution {
    public void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        merge(nums, l, mid, r);
    }

    private void merge(int[] nums, int l, int mid, int r) {
        int[] tmp = new int[r - l + 1];
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            tmp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        }
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];
        System.arraycopy(tmp, 0, nums, l, tmp.length);
    }
}

堆排(大顶堆 + 代码)

先建大顶堆,再把堆顶与末尾交换、缩小堆、下沉调整。

class Solution {
    public void heapSort(int[] nums) {
        int n = nums.length;
        for (int i = n / 2 - 1; i >= 0; i--) heapify(nums, n, i); // 建堆
        for (int i = n - 1; i > 0; i--) {
            int t = nums[0]; nums[0] = nums[i]; nums[i] = t;     // 堆顶放末尾
            heapify(nums, i, 0);                                 // 缩小堆并调整
        }
    }

    private void heapify(int[] nums, int n, int i) {
        int largest = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && nums[l] > nums[largest]) largest = l;
        if (r < n && nums[r] > nums[largest]) largest = r;
        if (largest != i) {
            int t = nums[i]; nums[i] = nums[largest]; nums[largest] = t;
            heapify(nums, n, largest);
        }
    }
}

复杂度与稳定性对比

排序 平均时间 最坏时间 空间 稳定性
快排 O(NlogN) O(N²) O(logN) 不稳定
归并 O(NlogN) O(NlogN) O(N) 稳定
堆排 O(NlogN) O(NlogN) O(1) 不稳定

面试题:“快排为什么比归并快?”

虽然都是 O(NlogN),但快排在工程上更快:一是常数小,partition 是原地交换、不需要额外数组;二是缓存友好,顺序访问比归并的跳跃合并更利于 CPU 缓存命中;三是空间省,归并需 O(N) 辅助数组。代价是快排最坏会退化到 O(N²),可通过随机化基准或三数取中规避。