Java 常见排序算法

约定

• 稳定性：排序后，相等元素的相对顺序是否与输入一致。
• 原地：除递归栈外是否仅需 (O(1)) 额外空间。

---

冒泡排序

反复比较相邻元素，逆序则交换；每一轮将当前未排序区间的最大元素「冒泡」到右端。若某一轮未发生交换，说明已有序，可提前结束。

• 时间：最坏/平均 (O(n^2))，最好（已有序且带提前结束）(O(n))。
• 空间：(O(1))。
• 稳定性：稳定（在「严格大于」时才交换的前提下）。

public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

---

选择排序

每一轮在未排序区间找最小下标，与区间首元素交换。交换次数少于冒泡，但比较次数仍为 (O(n^2))，且与输入是否部分有序关系不大。

• 时间：(O(n^2))。
• 空间：(O(1))。
• 稳定性：不稳定（交换可能跨过相等元素）。

public static void selectionSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

---

插入排序

将第 (i) 个元素插入左侧已有序区间：从 i-1 向左，大于 current 的元素后移，空位填入 current。逆序对数量与交换/移动次数相关，部分有序时很快。

• 时间：最坏 (O(n^2))，最好 (O(n))。
• 空间：(O(1))。
• 稳定性：稳定（向左扫描时用「严格小于」判断移动）。

public static void insertSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int current = arr[i];
        int j = i - 1;
        while (j >= 0 && current < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
    }
}

---

快速排序（荷兰国旗分区 + 随机 pivot）

分治：选基准 pivot，将区间划为 < pivot、== pivot、> pivot 三段（荷兰国旗），再递归左右两段。实现中将 pivot 先换到区间最右，分区后返回「小于区最右下标」与「大于区最左下标」，递归区间为 [left, less] 与 [large, right]。

随机 pivot：在 [left, right] 内随机选一元素与 right 交换再分区，降低有序输入下退化到 (O(n^2)) 的概率。

• 时间：平均 (O(n \log n))，最坏 (O(n^2))。
• 空间：递归栈平均 (O(\log n))，最坏 (O(n))。
• 稳定性：不稳定。

与 CS-Notes 中的三向切分快排同族，都是为大量重复键优化分区结构。

public static void swap(int[] arr, int left, int right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

public static int[] netherLandsFlagPartition(int[] nums, int left, int right) {
    if (left > right) {
        return new int[]{-1, -1};
    }
    if (left == right) {
        return new int[]{left, right};
    }
    int less = left - 1;
    int large = right + 1;
    int nowIndex = left;
    int target = nums[right];
    while (nowIndex < large) {
        if (nums[nowIndex] < target) {
            swap(nums, ++less, nowIndex);
            nowIndex++;
        } else if (nums[nowIndex] > target) {
            swap(nums, --large, nowIndex);
        } else {
            nowIndex++;
        }
    }
    return new int[]{less, large};
}

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int index = (int) (Math.random() * (right - left + 1)) + left;
    swap(arr, index, right);
    int[] sideArr = netherLandsFlagPartition(arr, left, right);
    quickSort(arr, left, sideArr[0]);
    quickSort(arr, sideArr[1], right);
}

另：neTherlandsPartition(nums, target) 是对整段数组按固定值 target 做三区划分，适合理解国旗过程；排序入口应对子区间调用上面的 quickSort（源码中递归方法名为 process03）。

---

归并排序

先二分递归到长度为 1，再合并两个有序段。合并时把 [left, right] 复制到辅助数组 temp，双指针比较写回原数组。merge 中取 <= 先拷贝左段，可保持稳定性。

• 时间：(O(n \log n))（最好/最坏/平均一致）。
• 空间：(O(n)) 辅助数组 + (O(\log n)) 栈。
• 稳定性：稳定。

入口方法在源码中命名为 mergetSort（拼写笔误），内部为自顶向下 mergeSort。

public static void mergeSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    int n = arr.length;
    int[] temp = new int[n];
    mergeSort(arr, 0, n - 1, temp);
}

private static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left >= right) {
        return;
    }
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid, temp);
    mergeSort(arr, mid + 1, right, temp);
    merge(arr, left, mid, right, temp);
}

private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    for (int i = left; i <= right; i++) {
        temp[i] = arr[i];
    }
    int p1 = left;
    int p2 = mid + 1;
    int k = left;
    while (p1 <= mid && p2 <= right) {
        if (temp[p1] <= temp[p2]) {
            arr[k++] = temp[p1++];
        } else {
            arr[k++] = temp[p2++];
        }
    }
    while (p1 <= mid) {
        arr[k++] = temp[p1++];
    }
    while (p2 <= right) {
        arr[k++] = temp[p2++];
    }
}

说明：原始实现里用参数名 left 兼作左指针并在循环中自增，逻辑等价；上文改写为 p1/p2 更易读。

---

堆排序

用数组表示完全二叉树，下标 i 的左右孩子为 2i+1、2i+2。先自底向上 heapify 建大顶堆，再将堆顶与末尾交换、缩小堆规模并再次对根 heapify，得到升序。

• 时间：(O(n \log n))。
• 空间：(O(1)) 原地。
• 稳定性：不稳定。

实现注意：swap 后若子树仍可能违反堆性质，应对交换下去的那一侧子树根继续递归 heapify(arr, heapSize, largest)，而不是仍从原父下标 i 下沉（后者在部分数据上会破坏正确性）。

public static void heapSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int heapSize, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < heapSize && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < heapSize && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, heapSize, largest);
    }
}

源码中排序入口名为 dumpSort，与常见命名 heapSort 对应同一流程。

---

希尔排序

在插入排序基础上，按递减间隔 h 对子序列排序，最后 h=1 退化为插入排序。间隔序列不同，最坏复杂度上界不同，但实践中常优于 (O(n^2))。详见 CS-Notes 希尔排序。

算法总结

算法	稳定性	时间（平均 / 最坏）	额外空间	备注
冒泡	是	(O(n^2)) / (O(n^2))	(O(1))	可提前结束
选择	否	(O(n^2)) / (O(n^2))	(O(1))	交换少
插入	是	(O(n^2)) / (O(n^2))	(O(1))	部分有序快
快速	否	(O(n\log n)) / (O(n^2))	(O(\log n))~栈	随机 pivot + 国旗
归并	是	(O(n\log n)) / (O(n\log n))	(O(n))	稳定、需辅助数组
堆排序	否	(O(n\log n)) / (O(n\log n))	(O(1))	原地，缓存友好性一般

扩展：Arrays.sort 与站内笔记

JDK 对基本类型与引用类型排序策略不同（如双轴快排、TimSort 等）。更细的叙述可参考站内文章 Java集合相关（Java集合相关.md）中对 Arrays.sort / Collections.sort 的说明。

参考

• CyC2018 CS-Notes：算法 - 排序