排序算法

排序算法总览

大家学习完排序算法后，可以去 912. 排序数组 验证自己的写法。

插入排序

插入排序的具体步骤如下：

1. 初始状态：将数组第一个元素视为已排序。

2. 选择待插入元素：从第二个元素开始，取出当前元素作为待插入值（base）。

3. 查找插入位置：从已排序部分的末尾向前比较，找到第一个小于或等于 base 的位置。

4. 移动元素与插入：比较的同时将大于 base 的元素依次后移一位，然后将 base 插入正确的位置。

5. 重复：对数组中的每个元素重复上述过程，直到所有元素均排序完成。

public void insertSort(int[] arr) {
    // 初始时数组第一个元素是有序的，i 从 1 开始
    for (int i = 1; i < arr.length; i++) {
        int base = arr[i];
        int j = i - 1;
        // 向左移动 j 指针，找到 base 在已排序区间 [0, i - 1] 中的正确位置
        // 同时将 > base 的元素都向后移动一位，为 base 空出位置
        while (j >= 0 && arr[j] > base) {
            arr[j + 1] = arr[j];    // 将 arr[j] 向右移动一位
            j--;
        }
        arr[j + 1] = base;  // 将 base 赋值到正确位置
    }
}

一、快速排序

快速排序是一种基于分治策略的排序算法。

快速排序的核心操作是“哨兵划分”，其目标是：选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。

然后递归的排序接下来的两个子数组。

public void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

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

// 哨兵划分
public int partition(int[] arr, int left, int right) {
    int pivot = arr[right]; // 选择最后一个元素作为基准
    // 双指针遍历，将小于 pivot 的数移动到 i 指针的位置
    int i = left;
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            swap(arr, i, j);
            i++;
        }
    }
    // 循环结束 [left, i - 1] 全部满足小于 pivot 的条件
    swap(arr, i, right);    // 将 pivot 移动到 i 位置
    return i;
}

二、归并排序

归并排序是一种基于分治策略的排序算法，具体分为「划分」和「合并」两个阶段。

1. 划分阶段：通过递归不断将数组从中间分成两端，将长数组的排序问题改成短数组的排序问题；

2. 合并阶段：当子数组的长度为 1 时结束划分，开始向上合并，借助辅助数组合并左右两个有序数组为一个有序数组。

public void mergeSort(int[] arr) {
    int n = arr.length;
    int[] tmp = new int[n];
    mergeSort(arr, 0, n - 1, tmp);
}

// 左闭右闭区间 [0, n - 1]
public void mergeSort(int[] arr, int left, int right, int[] tmp) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid, tmp);
        mergeSort(arr, mid + 1, right, tmp);
        merge(arr, left, mid, right, tmp);
    }
}

public void merge(int[] arr, int left, int mid, int right, int[] tmp) {
    int i = left;       // 左半部分起始索引
    int j = mid + 1;    // 右半部分起始索引
    int k = left;       // 辅助数组起始索引
    // 将两个有序子数组合并到辅助数组
    while (i <= mid && j <= right) {
        // 使用 <= 保证了稳定性
        if (arr[i] <= arr[j]) {
            tmp[k++] = arr[i++];
        } else {
            tmp[k++] = arr[j++];
        }
    }
    // 处理剩余元素
    while (i <= mid) {
        tmp[k++] = arr[i++];
    }
    while (j <= right) {
        tmp[k++] = arr[j++];
    }
    // 从 tmp 复制回 arr
    System.arraycopy(tmp, left, arr, left, right - left + 1);
}

三、堆排序

堆排序是一种基于堆数据结构实现的高效排序算法，堆排序的算法流程如下：

1. 根据输入数组建立最大堆

2. 将堆顶元素于堆底元素交换，堆的长度减 1，已排序的元素数量加 1；

3. 从堆顶开始，自顶向下堆化（sift down）。完成堆化后，堆的性质得到修复；

4. 重复上述步骤，循环 n-1 次后，即可完成数组排序。

public void heapSort(int[] arr) {
    int n = arr.length;
    // 原地堆化，时间复杂度 O(n)
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, i, n);
    }
    // 从堆中提取最大元素，循环 n - 1 轮
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        siftDown(arr, 0, i);
    }
}

// 堆长度为 n，从节点 i 开始，自顶向下堆化
public void siftDown(int[] arr, int i, int n) {
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int maxIdx = i;
    if (l < n && arr[l] > arr[maxIdx]) {
        maxIdx = l;
    }
    if (r < n && arr[r] > arr[maxIdx]) {
        maxIdx = r;
    }
    if (maxIdx == i) {
        return;
    }
    swap(arr, i, maxIdx);
    siftDown(arr, maxIdx, n);
}

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

堆的具体操作流程参见：手写数据结构：堆