1. 为什么需要掌握排序算法排序是程序开发中最常见的基础操作之一。无论是给商品列表按价格排序、给用户按注册时间排序还是给搜索结果按相关度排序背后都离不开排序算法。对于 Java 开发者来说掌握排序算法不仅能帮助你理解Arrays.sort等内置方法的工作原理还能在遇到特殊业务场景时写出更高效的代码。本文将从最基础的交换类排序讲起逐步深入到分治排序、堆排序以及线性时间排序并对比各算法的时间复杂度、空间复杂度与稳定性最后介绍 Java 内置排序工具的正确用法。2. 排序算法的分类与核心指标在开始写代码之前我们先了解几个评价排序算法的核心指标时间复杂度描述算法执行时间随数据规模增长的趋势通常用大 O 表示法。空间复杂度描述算法运行过程中额外占用的内存大小。稳定性如果两个值相等的元素在排序前后的相对顺序保持不变则称该排序是稳定的。原地排序排序过程中是否只使用常数级别的额外空间。排序算法可以按实现思路分为交换类冒泡、快速、插入类直接插入、希尔、选择类简单选择、堆、归并类归并排序、分配类计数、桶、基数。下面逐一介绍。3. 冒泡排序冒泡排序是最直观的排序算法。它反复遍历数组每次比较相邻两个元素如果顺序错误就交换。每一轮遍历都会把当前未排序区间中的最大值“冒泡”到最后位置。3.1 算法步骤从头开始比较相邻元素如果前者大于后者则交换。每一轮结束后最后一个元素就是当前轮的最大值。下一轮遍历范围缩小一位直到没有元素需要交换。3.2 代码实现public class BubbleSort { public static void sort(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; } } } }3.3 复杂度分析冒泡排序平均和最坏时间复杂度均为 O(n²)最优已有序为 O(n)空间复杂度 O(1)属于稳定排序。它实现简单但性能较差通常只用于教学或小规模数据。4. 选择排序选择排序的思路是每一轮从未排序区间中选出最小或最大的元素把它放到已排序区间的末尾。4.1 代码实现public class SelectionSort { public static void sort(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[i]; arr[i] arr[minIndex]; arr[minIndex] temp; } } }4.2 复杂度分析选择排序无论数据是否有序都要进行约 n²/2 次比较时间复杂度稳定为 O(n²)空间复杂度 O(1)。由于交换可能跨越多个元素它是不稳定排序。5. 插入排序插入排序模拟人们整理扑克牌的过程把未排序区间的元素逐个插入到已排序区间的合适位置。5.1 代码实现public class InsertionSort { public static void sort(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; } } }5.2 复杂度分析插入排序平均和最坏时间复杂度为 O(n²)但数据基本有序时接近 O(n)空间复杂度 O(1)且是稳定排序。它在小规模数据或部分有序数据上表现良好因此常被用于高级排序的优化环节。6. 希尔排序希尔排序是插入排序的改进版。它先将数组按一定间隔分组对每组做插入排序然后逐步缩小间隔直到间隔为 1。这种设计能让元素快速移动到大致正确的位置减少后续交换次数。6.1 代码实现public class ShellSort { public static void sort(int[] arr) { int n arr.length; for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key arr[i]; int j i; while (j gap arr[j - gap] key) { arr[j] arr[j - gap]; j - gap; } arr[j] key; } } } }6.2 复杂度分析希尔排序的时间复杂度与间隔序列的选择有关通常介于 O(n) 和 O(n²) 之间实践中常取得不错的性能。它是不稳定排序空间复杂度 O(1)。7. 归并排序归并排序采用分治思想先把数组递归地拆分成两半分别排序再把两个有序子数组合并成一个有序数组。它是稳定排序的代表算法之一。7.1 算法步骤如果数组长度小于等于 1直接返回。将数组从中间分成左右两部分。递归地对左右两部分排序。合并两个有序子数组。7.2 代码实现public class MergeSort { public static void sort(int[] arr) { mergeSort(arr, 0, arr.length - 1); } private 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[] temp new int[right - left 1]; int i left; int j mid 1; int 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.3 复杂度分析归并排序的时间复杂度始终为 O(n log n)空间复杂度 O(n)是稳定排序。由于需要额外数组空间它不属于原地排序但其稳定且性能可预测的特点让它广泛应用于外部排序和对象排序场景。8. 快速排序快速排序同样采用分治思想但实现方式不同选择一个基准元素把小于基准的元素放到左边大于基准的放到右边再递归处理左右两个区间。它是实际应用中最常用的排序算法之一。8.1 代码实现public class QuickSort { public static void sort(int[] arr) { quickSort(arr, 0, arr.length - 1); } private static void quickSort(int[] arr, int left, int right) { if (left right) { return; } int pivotIndex partition(arr, left, right); quickSort(arr, left, pivotIndex - 1); quickSort(arr, pivotIndex 1, right); } private static int partition(int[] arr, int left, int right) { int pivot arr[right]; int i left; for (int j left; j right; j) { if (arr[j] pivot) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; i; } } int temp arr[i]; arr[i] arr[right]; arr[right] temp; return i; } }8.2 复杂度分析快速排序平均时间复杂度为 O(n log n)最坏情况例如每次选的基准都是最大或最小值会退化为 O(n²)空间复杂度 O(log n)是不稳定排序。实际使用中通常配合随机选基准或三数取中法来避免最坏情况。9. 堆排序堆排序利用二叉堆这种数据结构先构建大顶堆然后反复把堆顶最大值与末尾元素交换再调整堆最终得到升序数组。9.1 代码实现public class HeapSort { public static void sort(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); } } }9.2 复杂度分析堆排序的时间复杂度始终为 O(n log n)空间复杂度 O(1)是不稳定排序。它的优势在于不需要额外数组空间且最坏情况仍然保持 O(n log n)。10. 计数排序计数排序适用于取值范围较小且已知的整数排序。它统计每个值出现的次数再根据计数结果把元素放回原数组。10.1 代码实现public class CountingSort { public static void sort(int[] arr) { int max arr[0]; int 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]; for (int num : arr) { count[num - min]; } for (int i 1; i range; i) { count[i] count[i - 1]; } int[] output new int[arr.length]; for (int i arr.length - 1; i 0; i--) { int num arr[i]; output[--count[num - min]] num; } System.arraycopy(output, 0, arr, 0, arr.length); } }10.2 复杂度分析计数排序的时间复杂度为 O(n k)其中 k 是取值范围大小空间复杂度 O(k)是稳定排序。当 k 远大于 n 时会浪费大量空间因此只适合整数且范围有限的场景。11. 桶排序桶排序把数据分散到多个有序的桶中对每个桶内部单独排序最后按桶的顺序把元素依次收集起来。它适合数据分布比较均匀的情况。11.1 代码实现import java.util.ArrayList; import java.util.Collections; import java.util.List; public class BucketSort { public static void sort(int[] arr) { int n arr.length; int max arr[0]; int min arr[0]; for (int num : arr) { if (num max) max num; if (num min) min num; } int bucketCount Math.max(n, 10); ListListInteger buckets new ArrayList(bucketCount); for (int i 0; i bucketCount; i) { buckets.add(new ArrayList()); } for (int num : arr) { int index (int) ((long) (num - min) * (bucketCount - 1) / (max - min)); buckets.get(index).add(num); } int idx 0; for (ListInteger bucket : buckets) { Collections.sort(bucket); for (int num : bucket) { arr[idx] num; } } } }11.2 复杂度分析桶排序平均时间复杂度接近 O(n k)其中 k 是桶的数量最坏情况会退化为 O(n²)。它需要额外空间存储桶稳定性取决于桶内部使用的排序算法。12. 基数排序基数排序按照数值的每一位进行排序从最低位开始依次到最高位。每一位使用稳定的排序通常配合计数排序最终得到完整有序结果。12.1 代码实现import java.util.Arrays; public class RadixSort { public static void sort(int[] arr) { int max Arrays.stream(arr).max().orElse(0); for (int exp 1; max / exp 0; exp * 10) { countingSortByDigit(arr, exp); } } private static void countingSortByDigit(int[] arr, int exp) { int[] output new int[arr.length]; 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 arr.length - 1; i 0; i--) { int digit (arr[i] / exp) % 10; output[--count[digit]] arr[i]; } System.arraycopy(output, 0, arr, 0, arr.length); } }12.2 复杂度分析设数字的最大位数为 d基数排序的时间复杂度为 O(d × n)空间复杂度 O(n k)是稳定排序。它适合位数有限的整数或定长字符串排序。13. 算法对比总结排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序取决于间隔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 k)O(n k)O(k)稳定桶排序O(n k)O(n²)O(n k)取决于桶内算法基数排序O(d × n)O(d × n)O(n k)稳定14. Java 内置排序Arrays.sort 与 Collections.sort实际开发中绝大多数场景不需要手写排序直接使用 Java 标准库即可。14.1 对基本类型数组排序import java.util.Arrays; public class BuiltInSortDemo { public static void main(String[] args) { int[] arr {5, 1, 9, 3, 7}; Arrays.sort(arr); System.out.println(Arrays.toString(arr)); } }对于int、long等基本类型数组Arrays.sort底层使用双轴快速排序平均性能很好。14.2 对对象数组排序import java.util.Arrays; public class ObjectSortDemo { static class Person implements ComparablePerson { String name; int age; Person(String name, int age) { this.name name; this.age age; } Override public int compareTo(Person other) { return Integer.compare(this.age, other.age); } Override public String toString() { return name : age; } } public static void main(String[] args) { Person[] people { new Person(Alice, 30), new Person(Bob, 22), new Person(Charlie, 25) }; Arrays.sort(people); System.out.println(Arrays.toString(people)); } }对象数组排序底层使用 TimSort这是一种结合归并排序和插入排序的稳定算法最坏时间复杂度为 O(n log n)。14.3 使用 Comparator 定制排序规则import java.util.ArrayList; import java.util.Comparator; import java.util.List; public class ComparatorDemo { public static void main(String[] args) { ListString names new ArrayList(List.of(banana, apple, cherry)); names.sort(Comparator.comparingInt(String::length).thenComparing(Comparator.naturalOrder())); System.out.println(names); } }通过Comparator可以灵活指定排序字段、排序方向以及多级排序规则。15. 如何选择排序算法数据量小插入排序或冒泡排序即可实现简单。数据基本有序优先考虑插入排序它在此场景下接近 O(n)。需要稳定排序且数据量大使用归并排序或 TimSort。内存受限、要求 O(1) 额外空间优先考虑快速排序或堆排序。整数且取值范围有限计数排序通常最快。日常开发直接使用Arrays.sort或Collections.sort不要重复造轮子。16. 总结本文系统讲解了冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序和基数排序的原理、Java 实现与复杂度分析并给出了各算法的对比表格。同时介绍了 Java 内置排序工具的使用方法。学习排序算法时建议不要死记代码而是理解每种算法的核心思想冒泡是相邻交换、选择是挑最小、插入是维护有序区间、归并是分而治之再合并、快排是围绕基准划分、堆排是利用堆的性质、计数是统计频次。理解了“为什么这样做”遇到变体问题才能灵活应对。
