本文简明介绍了10种经典排序算法，涵盖冒泡、选择、插入、快速、希尔、归并、堆、计数、桶和基数排序。每种算法从定义、时间复杂度（最佳/平均/最差）、空间复杂度、稳定性及适用场景进行说明，并附Java实现代码。关键对比显示：快速排序适合通用场景（平均O(nlogn)），堆排序保证最坏情况性能，归并排序兼顾稳定性和效率，而计数/桶/基数排序适用于特定数据特征。最后给出选择建议：内存敏感用堆排序，需稳定性选归并，特定数据用非比较类算法。
目录
1. 冒泡排序 (Bubble Sort)
定义：重复遍历数组，比较相邻元素，若顺序错误则交换。每轮遍历将最大元素“冒泡”到末尾。
时间复杂度：
最好：O(n)（已有序）
平均：O(n²)
最坏：O(n²)（完全逆序）
空间复杂度：O(1)（原地排序）
稳定性：稳定
Java代码：
public void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n - 1; i++) { 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; } } } }
2. 选择排序 (Selection Sort)
定义：遍历数组，每次选择最小元素放到已排序序列末尾。
时间复杂度：O(n²)（所有情况）
空间复杂度：O(1)（原地排序）
稳定性：不稳定（交换可能破坏顺序）
Java代码：
public 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)（原地排序）
稳定性：稳定
Java代码：
public void insertionSort(int[] arr) { int n = arr.length; for (int i = 1; i < n; 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. 快速排序 (Quick Sort)
定义：分治法思想。选取基准元素，将数组分为小于基准和大于基准的两部分，递归排序。
时间复杂度：
最好/平均：O(n log n)
最坏：O(n²)（基准选择不当）
空间复杂度：O(log n)（递归栈）
稳定性：不稳定
Java代码：
public 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 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; }
5. 希尔排序 (Shell Sort)
定义：改进的插入排序，按增量分组排序，逐渐减小增量至1。
时间复杂度：O(n log n) ~ O(n²)（取决于增量序列）
空间复杂度：O(1)（原地排序）
稳定性：不稳定
Java代码：
public 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; } } }
6. 归并排序 (Merge Sort)
定义：分治法思想。递归拆分数组为两半，排序后合并。
时间复杂度：O(n log n)（所有情况）
空间复杂度：O(n)（合并需额外空间）
稳定性：稳定
Java代码：
public void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } } private 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++]; System.arraycopy(temp, 0, arr, left, temp.length); }
7. 堆排序 (Heap Sort)
定义：构建最大堆，将堆顶元素（最大值）与末尾交换，调整堆。
时间复杂度：O(n log n)（所有情况）
空间复杂度：O(1)（原地排序）
稳定性：不稳定
Java代码：
public 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 void heapify(int[] arr, int n, int i) { int largest = i, left = 2 * i + 1, 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(n + k)（需额外空间）
稳定性：稳定（需反向填充）
适用场景：整数且范围小
Java代码：
public void countingSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); int min = Arrays.stream(arr).min().getAsInt(); 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--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } System.arraycopy(output, 0, arr, 0, arr.length); }
9. 桶排序 (Bucket Sort)
定义：将数据分到有限数量的桶中，每个桶单独排序（通常用插入排序）。
时间复杂度：
最好：O(n)（均匀分布）
平均：O(n + k)（k为桶数）
最坏：O(n²)（所有元素入一个桶）
空间复杂度：O(n + k)
稳定性：稳定（取决于桶内排序）
适用场景：数据均匀分布
Java代码：
public void bucketSort(float[] arr) { int n = arr.length; ArrayList<Float>[] buckets = new ArrayList[n]; for (int i = 0; i < n; i++) buckets[i] = new ArrayList<>(); for (float num : arr) { int idx = (int) (num * n); buckets[idx].add(num); } for (ArrayList<Float> bucket : buckets) Collections.sort(bucket); int idx = 0; for (ArrayList<Float> bucket : buckets) for (float num : bucket) arr[idx++] = num; }
10. 基数排序 (Radix Sort)
定义：按位数从低位到高位依次排序（通常用计数排序作为子排序）。
时间复杂度：O(d(n + k))（d为最大位数，k为基数）
空间复杂度：O(n + k)（需额外空间）
稳定性：稳定
适用场景：整数或字符串
Java代码：
public void radixSort(int[] arr) { int max = Arrays.stream(arr).max().getAsInt(); for (int exp = 1; max / exp > 0; exp *= 10) countingSortByDigit(arr, exp); } private void countingSortByDigit(int[] arr, int exp) { int n = arr.length; int[] output = new int[n]; int[] count = new int[10]; for (int num : arr) count[(num / exp) % 10]++; for (int i = 1; i < 10; i++) count[i] += count[i - 1]; for (int i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } System.arraycopy(output, 0, arr, 0, n); }
十大排序算法对比总结
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|---|
| 冒泡排序 | 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 log n) | O(n²) | O(log n) | 不稳定 | 通用排序（平均性能最优） |
| 希尔排序 | O(n log n) | O(n log 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 log n) | O(1) | 不稳定 | 原地排序、避免最坏情况 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 稳定 | 整数且范围小 |
| 桶排序 | O(n + k) | O(n) | O(n²) | O(n + k) | 稳定 | 数据均匀分布 |
| 基数排序 | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | 稳定 | 整数或字符串（位数固定） |
关键总结：
时间复杂度优先：
大规模数据：快速排序（平均O(n log n)）。
避免最坏情况：堆排序（始终O(n log n)）。
稳定且高效：归并排序（O(n log n) + 稳定）。
空间复杂度优先：
原地排序：堆排序、希尔排序（O(1)）。
特殊场景：
小范围整数：计数排序（O(n + k)）。
均匀分布浮点数：桶排序（O(n)）。
多位数整数：基数排序（O(dn)）。
稳定性要求：归并排序、计数排序、桶排序、基数排序。
小规模数据：插入排序（简单且稳定）。
实际建议：
通用场景：优先选择 快速排序（库函数常用）。
内存敏感：选择 堆排序。
稳定性必需：选择 归并排序。
特定数据：根据范围/分布选择非比较排序（计数、桶、基数）。
