Java 中的七大经典排序算法详解
在 Java 中讨论排序算法时，通常指以下七种最经典、最常被考察的排序算法（大学数据结构课 + 面试最常出现的组合）：
- 冒泡排序 (Bubble Sort)
- 选择排序 (Selection Sort)
- 插入排序 (Insertion Sort)
- 希尔排序 (Shell Sort)
- 归并排序 (Merge Sort)
- 快速排序 (Quick Sort)
- 堆排序 (Heap Sort)
下面给出 Java 实现 + 核心思想 + 时间/空间复杂度 + 稳定性 + 适用场景 的完整对比与代码。
复杂度与特性一览表
| 排序算法 | 最好时间 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 | 原地排序 | 适用场景简述 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 | 小规模数据、教育演示 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | 是 | 小规模数据、交换次数最少要求 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | 是 | 近乎有序、小规模数据 |
| 希尔排序 | O(n log n) ~ O(n^{1.3}) | O(n^{1.3}) ~ O(n²) | O(n²) | O(1) | 不稳定 | 是 | 中等规模数据，改进插入排序 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | 否 | 大数据、稳定排序需求、外部排序 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 | 是 | 通用排序、平均性能最好（Java Arrays.sort） |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | 是 | 需要 O(1) 额外空间、大数据 |
1. 冒泡排序（Bubble Sort）
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - i - 1; 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;
}
}2. 选择排序（Selection Sort）
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;
}
}
// 交换
int temp = arr[i];
arr[i] = arr[minIdx];
arr[minIdx] = temp;
}
}3. 插入排序（Insertion Sort）
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; 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;
}
}4. 希尔排序（Shell Sort）
public static void shellSort(int[] arr) {
int n = arr.length;
// 初始间隔可以有很多取法，这里用 n/2 递减
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个分组进行插入排序
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}5. 归并排序（Merge Sort）
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int[] temp = new int[arr.length];
mergeSort(arr, 0, arr.length - 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) {
int i = left, j = mid + 1, k = left;
while (i <= mid && j <= right) {
temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
System.arraycopy(temp, left, arr, left, right - left + 1);
}6. 快速排序（Quick Sort）——最经典版本
public static void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int low, int high) {
if (low >= high) return;
// 优化：小数组用插入排序
if (high - low <= 10) {
insertionSort(arr, low, high);
return;
}
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
private static int partition(int[] arr, int low, int high) {
// 随机化 pivot 防止最坏情况
int randomIdx = low + (int)(Math.random() * (high - low + 1));
swap(arr, randomIdx, high);
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static void insertionSort(int[] arr, int low, int high) {
for (int i = low + 1; i <= high; i++) {
int key = arr[i];
int j = i - 1;
while (j >= low && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}7. 堆排序（Heap Sort）
public static void heapSort(int[] arr) {
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 n, int i) {
int largest = i;
int left = 2 * i + 1;
int 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(1)）
- 为什么 Java 的 Arrays.sort() 默认使用快速排序 + 双轴快速排序 + 插入排序混合？
- 快速排序最坏情况如何避免？（随机化 pivot、三数取中、双轴快排）
- 什么时候用归并排序比快速排序更好？（需要稳定排序、大数据外部排序、链表排序）
如果你正在准备面试，建议把快速排序、归并排序、堆排序的代码 + 手写 partition / merge / heapify 过程练熟，这是高频手撕代码题。
需要哪一个算法的更详细的动图讲解思路、边界case分析、还是完整测试代码？
或者想看 Java 中内置排序（Arrays.sort、Collections.sort）的底层实现细节？
