八大排序算法与 Java 代码实现

排序算法是计算机科学中最基础的算法之一，也是面试和笔试的常客。本文将详细介绍八大经典排序算法的核心思想、时间复杂度、稳定性，并给出完整的 Java 代码实现。无论你是初学者还是准备面试的开发者，相信本文都能帮你理清思路，加深理解。

排序算法分类

按照是否使用比较操作，排序算法可分为两类：

• 比较排序：通过比较元素大小决定顺序，如冒泡、选择、插入、希尔、归并、快速、堆排序。时间复杂度下界为 O(n log n)。

• 非比较排序：不通过比较，而是利用元素本身的特征排序，如计数排序、基数排序、桶排序。在特定条件下可以达到 O(n) 的时间复杂度。

按照稳定性，排序算法又可分为稳定排序和不稳定排序：稳定排序能保持相等元素的原始相对顺序。

1. 冒泡排序（Bubble Sort）

算法思想：重复遍历数组，依次比较相邻元素，若顺序错误则交换。每遍历一次，最大（或最小）的元素就会“浮”到末尾。

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：稳定

public class BubbleSort { 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 - 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; // 没有交换说明已经有序 } } }

2. 选择排序（Selection Sort）

算法思想：每次从未排序部分选出最小（或最大）元素，放到已排序部分的末尾。

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定（例如 [5, 5, 2] 第一个 5 会和 2 交换，导致两个 5 的相对顺序改变）

public class SelectionSort { 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）

算法思想：将数组看作已排序和未排序两部分，每次从未排序部分取出第一个元素，插入到已排序部分的正确位置。

时间复杂度：O(n²)（最好情况 O(n)）
空间复杂度：O(1)
稳定性：稳定

public class InsertionSort { public static void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } }

4. 希尔排序（Shell Sort）

算法思想：插入排序的改进版，通过将数组按一定间隔分组，对每组进行插入排序，然后逐步缩小间隔，最终间隔为 1 时完成排序。

时间复杂度：依赖于步长序列，平均 O(n log n) ~ O(n²)
空间复杂度：O(1)
稳定性：不稳定（分组插入可能打乱相等元素顺序）

public class ShellSort { public static void shellSort(int[] arr) { int n = arr.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i; while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } } }

5. 归并排序（Merge Sort）

算法思想：采用分治法，将数组递归分成两半分别排序，再将两个有序子数组合并。

时间复杂度：O(n log n)
空间复杂度：O(n)（需要额外数组存储合并结果）
稳定性：稳定

public class MergeSort { public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } } private static void merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } // 将临时数组复制回原数组 for (i = 0; i < temp.length; i++) { arr[left + i] = temp[i]; } } }

6. 快速排序（Quick Sort）

算法思想：选择一个基准（pivot），将小于基准的元素放左边，大于基准的放右边，然后递归地对左右子数组排序。

时间复杂度：平均 O(n log n)，最坏 O(n²)
空间复杂度：O(log n)（递归栈空间）
稳定性：不稳定

下面是简洁易懂的递归版本（使用额外数组）和原地分区版本。这里给出经典的原地分区实现。

public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pi = partition(arr, low, high); // 分区索引 quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } private static int partition(int[] arr, int low, int high) { int pivot = arr[high]; // 选择最后一个元素作为基准 int i = low - 1; // 小于基准的元素的索引 for (int j = low; j < high; j++) { if (arr[j] <= pivot) { i++; // 交换 arr[i] 和 arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // 将基准放到正确位置 int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1; } }

7. 堆排序（Heap Sort）

算法思想：利用堆这种数据结构。首先将数组构建成最大堆，然后反复将堆顶（最大元素）与末尾交换，并调整堆。

时间复杂度：O(n log n)
空间复杂度：O(1)
稳定性：不稳定

public class HeapSort { 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--) { // 交换堆顶（最大值）与末尾元素 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 调整堆 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) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest); } } }

8. 计数排序（Counting Sort）

算法思想：非比较排序，适用于数据范围不大的整数序列。统计每个元素出现的次数，然后根据次数依次输出。

时间复杂度：O(n + k)，k 为数据范围
空间复杂度：O(k)
稳定性：稳定（若从后往前填充）

public class CountingSort { public static void countingSort(int[] arr) { if (arr.length == 0) return; // 找出最大值和最小值 int max = arr[0], min = arr[0]; for (int num : arr) { if (num > max) max = num; if (num < min) min = num; } int range = max - min + 1; int[] count = new int[range]; int[] output = new int[arr.length]; // 统计每个元素出现的次数 for (int num : arr) { count[num - min]++; } // 计算累积次数（用于稳定排序） for (int i = 1; i < range; i++) { count[i] += count[i - 1]; } // 从后往前填充，保证稳定性 for (int i = arr.length - 1; i >= 0; i--) { int num = arr[i]; output[count[num - min] - 1] = num; count[num - min]--; } // 将结果复制回原数组 System.arraycopy(output, 0, arr, 0, arr.length); } }

总结对比