常见排序算法#
排序算法是计算机科学中最基础也是最重要的算法之一。本文介绍几种常见的排序算法，并给出 Java 实现。
1. 冒泡排序（Bubble Sort）#
思想：重复遍历待排序序列，每次比较相邻两个元素，若顺序错误则交换，直到没有需要交换的元素为止。
- 时间复杂度：O(n²)
- 空间复杂度：O(1)
- 稳定排序
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)
- 不稳定排序
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 将最小元素交换到已排序部分的末尾
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}3. 插入排序（Insertion Sort）#
思想：将未排序部分的元素逐个插入到已排序部分的正确位置，类似于整理扑克牌。
- 时间复杂度：O(n²)，最好情况 O(n)
- 空间复杂度：O(1)
- 稳定排序
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）#
思想：插入排序的改进版，先将序列按照一定间隔分组，对各组进行插入排序，然后逐渐缩小间隔，最终变为普通插入排序。
- 时间复杂度：O(n log² n) ~ O(n²)，取决于间隔序列
- 空间复杂度：O(1)
- 不稳定排序
public static void shellSort(int[] arr) {
int n = arr.length;
// 使用 Knuth 序列作为间隔：1, 4, 13, 40, ...
int gap = 1;
while (gap < n / 3) {
gap = gap * 3 + 1;
}
while (gap >= 1) {
for (int i = gap; i < n; i++) {
int key = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > key) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = key;
}
gap /= 3;
}
}5. 归并排序（Merge Sort）#
思想：采用分治策略，将序列递归地分成两半，分别排序后再合并。
- 时间复杂度：O(n log n)
- 空间复杂度：O(n)
- 稳定排序
public static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
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 n1 = mid - left + 1;
int n2 = right - mid;
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
System.arraycopy(arr, left, leftArr, 0, n1);
System.arraycopy(arr, mid + 1, rightArr, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k++] = leftArr[i++];
} else {
arr[k++] = rightArr[j++];
}
}
while (i < n1) arr[k++] = leftArr[i++];
while (j < n2) arr[k++] = rightArr[j++];
}调用方式：mergeSort(arr, 0, arr.length - 1);
6. 快速排序（Quick Sort）#
思想：选取一个基准元素，将序列分为小于基准和大于基准的两部分，然后递归排序两部分。
- 时间复杂度：平均 O(n log n)，最坏 O(n²)
- 空间复杂度：O(log n)（递归栈）
- 不稳定排序
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
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) {
// 以末尾元素为基准
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
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;
}调用方式：quickSort(arr, 0, arr.length - 1);
7. 堆排序（Heap Sort）#
思想：利用堆这种数据结构，先建立最大堆，然后依次将堆顶元素（最大值）取出并放到末尾，再调整堆。
- 时间复杂度：O(n log n)
- 空间复杂度：O(1)
- 不稳定排序
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 temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}算法复杂度对比#
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n log² n) | O(n²) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
如何选择排序算法#
- 数据量小：插入排序或选择排序即可，实现简单。
- 数据基本有序：插入排序效率最高，接近 O(n)。
- 需要稳定排序：归并排序是最优选择，时间复杂度稳定在 O(n log n)。
- 追求平均性能：快速排序在大多数情况下表现最好。
- 内存受限：堆排序空间复杂度为 O(1)，且时间复杂度稳定为 O(n log n)。
