很多初学 Java 的人学到排序这一章都会遇到一个奇怪的现象看代码能看懂关掉书自己写就卡住笔试能用库函数面试一让手写就紧张。原因很简单排序不是背代码而是理解每一轮循环在干什么。七大排序算法里插入、希尔、选择、堆、冒泡、快排、归并各有各的脾气再加上计数、基数、桶这类不靠比较的“非比较”排序这套内容基本覆盖了数据结构初阶最核心的排序知识。这篇文章我结合自己调试这些排序时踩过的坑用 Java 把思路、代码、边界条件和优化细节都过一遍适合正在学数据结构的同学、准备算法面试的人也适合想把手写排序能力补扎实的开发者。1. 为什么要掌握七大排序算法1.1 排序在数据结构与算法中的位置很多人会觉得现在写 Java 业务代码根本不用手写排序直接Arrays.sort()或Collections.sort()就行了。这个说法没错但只看到了表面。排序是分治、双指针、二分查找、TopK 等很多算法的基础理解排序过程等于理解了数组下标操作、循环不变量、递归和分治这些底层能力。初阶数据结构里最容易被面试问到的就是手写排序尤其是快速排序和归并排序。面试官不是非要用这些代码去跑大数据量而是想通过排序看你有没有把“数组边界处理”“递归终止条件”“元素交换逻辑”想清楚。很多时候算法题写不出来不是题目难而是对排序这类基础操作不够熟导致对数组的操控不自信。另外排序算法的稳定性、时间复杂度和空间复杂度也是学习后续内容的基础。比如做数据库索引优化时归并排序用于外部排序在数据仓库里统计 TopK堆排序是最常用的方案在业务系统里处理大量整数 ID计数排序和基数排序可以比比较排序快很多。排序不是孤立的知识点它是数据结构初阶里连接数组、链表、树和分治思想的桥梁。1.2 七大排序怎么选一张表看清复杂度很多初学者一上来就记结论快排最好、归并稳定、堆排最差也是 O(n log 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^1.3~1.5)O(n²)O(n)O(1)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定快速排序O(n log n)O(n²)O(n log n)O(log n)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定计数排序O(n k)O(n k)O(n k)O(k)稳定基数排序O(d(n r))O(d(n r))O(d(n r))O(n r)稳定桶排序O(n k)O(n²)O(n)O(n k)稳定这里的 k 通常表示数据范围d 表示数字位数r 表示基数。从表里可以明显看出非比较排序的复杂度不再依赖元素之间的比较次数而是依赖数据本身的范围和分布。所以“非比较”排序不是魔法它是在特定条件下把比较成本换成了数组寻址成本。2. 交换排序冒泡排序与快速排序2.1 冒泡排序最直观的排序但优化要做对冒泡排序的思路是每一轮把相邻元素中较大的往后移动就像气泡往上浮一样。写代码之前先明确外层循环表示一共要经过多少趟内层循环表示这一趟比较哪些相邻位置。如果数组长度是 n最多经过 n - 1 趟就能完成排序。public static void bubbleSort(int[] arr) { if (arr null || arr.length 2) { return; } 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]) { swap(arr, j, j 1); swapped true; } } if (!swapped) { break; } } }这里最容易出错的是内层循环的终止条件j n - 1 - i。为什么不是j n - 1因为每一轮结束后当前范围内最大的元素已经沉到最右侧下一轮完全不需要再去碰它。如果继续用j n - 1多余比较会影响性能虽然结果不错但失去了优化的意义。第一次写冒泡排序的同学往往忽略swapped标记。这个标记的意义是如果某一轮从头到尾都没有发生过交换说明数组已经有序直接结束。不加这个标记最好情况也是 O(n²)加了之后面对一个完全有序的数组只需要一趟扫描就能结束复杂度降到 O(n)。这个优化在面试里是加分项。2.2 快速排序选好基准值避免最坏情况快速排序是典型的分治思想选一个基准值把比它小的放到左边比它大的放到右边然后递归处理左右两半。快排的平均性能很好但有一个极容易被问到的短板在最坏情况下会退化成 O(n²)典型的场景就是数组已经有序。为什么有序数组会出问题因为如果每次选基准值都选到当前区间的最小值或最大值那么划分出来的左右两边一边为空另一边几乎是全部递归深度就变成了 n退化成类似选择排序的复杂度。解决思路有两个一个是随机选择基准值另一个是“三数取中”。三数取中的意思是取当前区间左端、中间、右端三个位置的值把其中大小居中的那个作为基准值。这样可以避免有序数组和大体有序数组造成的极度不平衡划分。private static int medianOfThree(int[] arr, int left, int right) { int mid left ((right - left) 1); if (arr[left] arr[mid]) { swap(arr, left, mid); } if (arr[left] arr[right]) { swap(arr, left, right); } if (arr[mid] arr[right]) { swap(arr, mid, right); } return mid; }这个实现先把三个位置大小调整好最后返回中间位置的下标。有了三数取中即使面对有序数组基准值也能落在区间中间附近递归树会平衡很多快排的最坏概率大大降低。2.3 挖坑法实现与小区间优化快排的划分实现有很多种比如 Hoare 法和挖坑法。Hoare 法代码短但边界条件不好理解初学者很容易把和搞反。我一般建议初学阶段用挖坑法因为它更贴近“先挖坑、再填坑”的过程逻辑清晰。public static void quickSort(int[] arr, int left, int right) { if (left right) { return; } // 小区间使用插入排序减少递归深度和函数调用开销 if (right - left 15) { insertSort(arr, left, right); return; } int pivotIndex medianOfThree(arr, left, right); int pivot arr[pivotIndex]; // 把基准值暂时放到最左边形成初始坑 swap(arr, pivotIndex, left); int l left; int r right; int hole left; while (l r) { while (l r arr[r] pivot) { r--; } arr[hole] arr[r]; hole r; while (l r arr[l] pivot) { l; } arr[hole] arr[l]; hole l; } arr[hole] pivot; quickSort(arr, left, hole - 1); quickSort(arr, hole 1, right); }这里有两个细节。第一右侧扫描时条件是arr[r] pivot左侧扫描时条件是arr[l] pivot等于号不能去掉。如果去掉等于号遇到大量重复元素时左右指针容易在相等元素之间来回移动导致死循环。第二小区间降级成插入排序是工程上常用的优化阈值一般取 10 到 20。因为递归到很小区间时函数调用和分区开销已经超过直接插入排序的成本。我在自己测试时发现三数取中加小区间插入优化后快排在整体有序和大量重复数据上都能表现得比较稳。但要注意快排的空间复杂度分析的是递归栈深度平均 O(log n)最坏 O(n)所以递归实现快排时如果数据量太大且分布极端仍然可能栈溢出。3. 插入排序与希尔排序3.1 直接插入排序扑克牌思维与近乎有序的利器插入排序的思想特别贴近打扑克牌你拿到一张新牌会从右往左找到合适的位置插进去后面的牌整体右移。代码实现时外层循环从第二个元素开始内层循环把当前元素往前插入到正确位置。public static void insertSort(int[] arr) { insertSort(arr, 0, arr.length - 1); } private static void insertSort(int[] arr, int left, int right) { for (int i left 1; i right; i) { int tmp arr[i]; int j i - 1; while (j left arr[j] tmp) { arr[j 1] arr[j]; j--; } arr[j 1] tmp; } }很多人在写插入排序时容易把“移动”和“交换”混在一起。这里并没有用swap而是先把目标元素保存到tmp然后让前面的较大元素依次右移最后把tmp放回空出来的位置。移动元素比交换元素少了很多次赋值常数性能会更好。插入排序有两个非常突出的优点。第一在数据量小的时候它是常数项很低的排序比快排和归并还快。第二在序列“基本有序”的时候它的时间复杂度接近 O(n)因为大部分元素都已经在正确位置上不需要移动。这也是快排在小区间会降级成插入排序的原因。但它的缺点也很明显数据量大且乱序时移动次数非常恐怖完全没有优势。3.2 希尔排序从分组插入到逐步优化希尔排序是插入排序的改进版核心思想是“先分组再整体”。它先让间隔较远的元素进行插入排序这样大跨度的元素能快速归位然后逐步缩小间隔最后做一次全数组的插入排序。public static void shellSort(int[] arr) { int n arr.length; // gap 通常取 n/2之后不断折半 for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int tmp arr[i]; int j i - gap; // 对当前分组做插入排序 while (j 0 arr[j] tmp) { arr[j gap] arr[j]; j - gap; } arr[j gap] tmp; } } }这段代码和插入排序的核心逻辑很像区别只是步长从 1 变成了 gap。外层循环每次把 gap 除以 2这是希尔排序最常见的取法也有人用gap gap / 3 1不同序列对性能有影响但初阶阶段掌握/2这个版本足够了。为什么希尔排序比普通插入排序快因为它在间隔大时元素可以一次性跨越大距离移动把较小的元素快速往前挪。这种操作比普通插入排序里一格一格地移动要高效得多。希尔排序的时间复杂度取决于增量序列的选择平均大概在 O(n^1.3) 到 O(n^1.5) 之间最坏还是可能到 O(n²)。需要特别注意希尔排序是不稳定排序。举个例子两个相同值如果被分在不同组分组插入的过程中会改变它们原来的相对顺序。所以需要稳定排序的场景下不要用希尔排序。它的空间复杂度是 O(1)原地排序内存压力小。4. 选择排序与堆排序4.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; } } if (minIndex ! i) { swap(arr, i, minIndex); } } }从代码看选择排序无论什么数据都要进行固定轮数的扫描所以最好、最坏、平均都是 O(n²)。它虽然简单但很少用于工程中更多是作为教学案例。关于不稳定性的例子可以这样理解数组中有两个相等的元素 5a 和 5b5a 在前面。某一次选择排序中最小的元素在 5b 的后面把它换到数组前方时可能会直接把 5a 或 5b 交换出去导致 5b 出现在 5a 前面。这种相对顺序的改变在只包含 int 的排序中可能无所谓但如果数组里存的是对象并且你希望先按另一个字段排序后再按当前字段排序选择排序就会打乱上一次排序的顺序。4.2 堆排序建堆和向下调整是核心堆排序利用的是完全二叉树的性质。升序排序用大根堆每次把堆顶元素和堆尾元素交换再把堆的长度减一继续调整让剩余元素重新满足大根堆。堆排序最难的部分是“向下调整”和“建堆”。向下调整要时刻记住当前节点的左孩子下标是parent * 2 1右孩子下标是parent * 2 2。很多越界错误都出现在孩子下标超过当前堆的有效长度这里。public static void heapSort(int[] arr) { int n arr.length; // 建堆从最后一个非叶子节点开始向下调整 for (int i n / 2 - 1; i 0; i--) { siftDown(arr, i, n); } // 逐个将堆顶元素放到数组末尾 for (int i n - 1; i 0; i--) { swap(arr, 0, i); siftDown(arr, 0, i); } } private static void siftDown(int[] arr, int parent, int size) { int child parent * 2 1; while (child size) { // 如果右孩子存在且更大则选择右孩子 if (child 1 size arr[child 1] arr[child]) { child; } if (arr[child] arr[parent]) { swap(arr, parent, child); parent child; child parent * 2 1; } else { break; } } }为什么建堆要从n / 2 - 1开始因为最后一个非叶子节点就是这个位置叶子节点本身满足堆的性质不需要处理。如果从 0 开始向下调整建出来的堆不一定正确所以这个起点很关键。堆排序的优势是时间复杂度稳定在 O(n log n)空间复杂度 O(1)且不存在快排那种最坏退化问题。但它的常数比较大整体交换次数多实际速度通常不如快排。堆排序更大的应用场景是 TopK 问题维护一个大小为 K 的小根堆遍历数据时如果新元素比堆顶大就替换堆顶并调整最终堆里就是最大的 K 个元素。5. 归并排序与外部排序思路5.1 归并排序的递归实现与稳定性归并排序是分治思想最标准的体现先把数组从中间分成两半分别排序再把两个有序数组合并成一个有序数组。合并的过程需要借助临时数组这也是它空间复杂度为 O(n) 的原因。public static void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid left ((right - left) 1); 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[] tmp 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]) { tmp[k] arr[i]; } else { tmp[k] arr[j]; } } while (i mid) { tmp[k] arr[i]; } while (j right) { tmp[k] arr[j]; } for (i 0; i tmp.length; i) { arr[left i] tmp[i]; } }归并排序的稳定性来自合并时的判断条件arr[i] arr[j]时优先取左边的元素。如果写成相等元素就会取右边稳定性就被破坏了。这个细节在对象排序场景里非常关键。归并排序的缺点是需要额外的 O(n) 空间。很多初学者会把mid算成(left right) / 2这样在极端情况下可能溢出用left ((right - left) 1)更安全。这一点在 Java 里尤其重要虽然现在大多数场景数据量不会大到溢出但写成位运算形式的习惯是好的。5.2 非递归归并从“两两归并”到海量数据递归归并好理解但递归会有栈深度和函数调用开销。非递归归并采用“自底向上”的思路先让相邻的每个长度为 1 的元素两两归并得到长度为 2 的有序段再让相邻长度为 2 的有序段归并直到整个数组有序。public static void mergeSortNonRecursive(int[] arr) { int n arr.length; for (int gap 1; gap n; gap 1) { for (int left 0; left n; left 2 * gap) { int mid Math.min(left gap - 1, n - 1); int right Math.min(left 2 * gap - 1, n - 1); if (mid right) { merge(arr, left, mid, right); } } } }这里的gap表示当前每个有序段的长度第一次从 1 开始第二次从 2 开始第四次从 4 开始。边界处理很关键最后一段可能长度不足所以mid和right都要用Math.min限制到n - 1如果mid right说明右半段不存在不需要归并。非递归归并用在普通数组排序时优势不明显但它是外部排序的基础。数据量太大无法全部加载到内存时我们可以把文件切分成多个小块每块分别排序后写回磁盘然后按照归并的方式两两读取把小块合并成更大的有序块。这就是外部排序的核心思路归并排序因此成为数据库等场景里最重要的排序算法之一。6. 非比较排序计数排序、基数排序、桶排序6.1 计数排序用数组下标代替比较比较排序的下限是 O(n log n)但如果我们对数据本身有额外限制就能打破这个下限。计数排序就是一个典型例子它根本不需要比较元素大小而是把元素值作为数组下标来记录出现次数。计数排序适用于数据范围有限、且都是整数或可以映射到整数的情况。比如给一个班级的学生年龄排序年龄范围基本在 15 到 20 之间用计数排序非常快。假如数据的最大值和最小值相差很大比如从 0 到 10 亿计数数组根本没法开就不适合用计数排序。public static void countingSort(int[] arr) { if (arr.length 2) { return; } int min arr[0]; int max arr[0]; for (int v : arr) { min Math.min(min, v); max Math.max(max, v); } int range max - min 1; int[] count new int[range]; int[] output new int[arr.length]; for (int v : arr) { count[v - min]; } // 前缀和让计数排序稳定 for (int i 1; i range; i) { count[i] count[i - 1]; } // 从后往前填充保持稳定 for (int i arr.length - 1; i 0; i--) { int value arr[i]; output[--count[value - min]] value; } for (int i 0; i arr.length; i) { arr[i] output[i]; } }第一次写计数排序时我很容易漏掉“最小值偏移”这一步。如果不做偏移遇到数组里有负数时value - min可以是负的下标访问直接越界。另外前缀和的目的是记录每个值最后一次出现的位置倒序填充则是为了保证相同值的元素维持原有相对顺序也就是稳定性。单纯记录出现次数然后展开也能排好序但那样是不稳定的。如果排序对象是对象数组稳定性很重要所以工程上用“前缀和加倒序填充”这种写法更通用。计数排序时间复杂度 O(n k)空间 O(k)k 是数据范围。6.2 基数排序逐位处理的另一种视角基数排序是另一种非比较排序它的思路是按位处理。比如对一组非负整数先从个位开始按个位数字分桶收集后得到一个按个位有序的序列再按十位处理再按百位处理处理完最高位后整个数组有序。每一轮实际上可以用计数排序来实现因为每一位上的数字范围只有 0 到 9。这样可以保持稳定性而稳定性是按位排序最重要的前提。public static void radixSortForNonNegative(int[] arr) { int max 0; for (int v : arr) { max Math.max(max, v); } for (int exp 1; max / exp 0; exp * 10) { countingSortByDigit(arr, exp); } } private static void countingSortByDigit(int[] arr, int exp) { int n arr.length; int[] count new int[10]; int[] output new int[n]; for (int v : arr) { int digit (v / exp) % 10; count[digit]; } for (int i 1; i 10; i) { count[i] count[i - 1]; } for (int i n - 1; i 0; i--) { int digit (arr[i] / exp) % 10; output[--count[digit]] arr[i]; } System.arraycopy(output, 0, arr, 0, n); }这段代码只适合非负整数。如果有负数一个简单的处理办法是先给所有元素加上最小值的绝对值排完序后再减回来。但要注意偏移后的最大值可能很大会变慢。总之基数排序适合数据位数不多、数据分布相对均匀的整数场景时间复杂度 O(d(n 10))d 是最大数字位数。虽然看起来快但常数开销不小如果数据量不大、位数又多可能还不如快排。6.3 桶排序数据分布均匀时很高效桶排序的思路是把数据分成若干个桶然后每个桶内部各自排序最后按桶的顺序把元素拼接起来。它和计数排序的区别是计数排序一个值占一个下标桶排序则是一段范围内的值共用一个桶。public static void bucketSort(int[] arr, int bucketSize) { if (arr.length 2) { return; } int min arr[0]; int max arr[0]; for (int v : arr) { min Math.min(min, v); max Math.max(max, v); } int bucketCount (max - min) / bucketSize 1; ListListInteger buckets new ArrayList(bucketCount); for (int i 0; i bucketCount; i) { buckets.add(new ArrayList()); } for (int v : arr) { int index (v - min) / bucketSize; buckets.get(index).add(v); } int k 0; for (ListInteger bucket : buckets) { // 桶内元素少时直接插入排序即可 insertSortForBucket(bucket); for (int num : bucket) { arr[k] num; } } }桶排序能不能跑到近似 O(n)完全取决于数据分布。如果元素均匀分布在桶之间每个桶里的元素很少桶内排序几乎可以忽略整体就快。反过来如果所有元素落在同一个桶里桶内排序可能退化到 O(n²)。所以桶排序更适合均匀分布的数据比如在某个区间内均匀分布的小数或整数。桶内排序不需要固定的排序算法元素少时用插入排序就行。要注意桶数量不能太小也不能太大太小会导致桶内元素太多太大则浪费内存。一般可以根据数据量来估算比如bucketSize取 5 到 10 都能得到不错效果。7. 常见问题与调试经验7.1 边界条件与数组越界排序代码非常容易在边界条件上出错。我总结下来最常翻车的几个点分别是快速排序左右指针相遇后的下标恢复、堆排序中孩子节点下标计算、归并排序中右半段为空时的判断。快速排序的挖坑法里左右指针的 pivot和 pivot必须配合哨兵否则重复元素会死循环。堆排序中child 1 size这个判断不能省否则右孩子越界。归并排序非递归版本里mid和right都要用Math.min限制不然最后一个不完整段会导致越界。我建议你准备一个验证方法写完任何一个排序后都先跑一遍public static boolean isSorted(int[] arr) { for (int i 1; i arr.length; i) { if (arr[i - 1] arr[i]) { return false; } } return true; }然后专门测试这些场景空数组、只有一个元素、两个元素、全部相等、倒序数组、大量重复元素。不要只用一个随机数组验证很多排序在随机数组没问题碰到大量相等元素时才会暴露出死循环或稳定性问题。7.2 稳定性、比较器与库函数的差别理解排序稳定性比单纯背结论要有意义得多。稳定性描述的是如果两个元素值相等排序后它们的相对位置是否和原来一致。归并排序稳定快排和堆排不稳定。在实际业务中稳定性主要体现在对象排序上。比如一个列表先按姓名排序再按班级排序如果第二次排序是稳定的那么同一个班级内部仍然保留姓名顺序。所以在处理对象数组时稳定性是必须考虑的问题。Java 标准库也做了这类区分Arrays.sort(int[])底层用的是双轴快排适合基本类型Arrays.sort(Object[])使用的是一种稳定的归并式排序。排序对象是基本类型时稳定性没有意义因为两个基本类型的值相同就是不可区分但排序对象是引用类型时稳定性会影响结果。所以自己实现对象排序时需要明确用Comparable还是Comparator并在比较结果相等时不改变位置。7.3 实测对比与排序算法选择建议写排序不能只看理论复杂度还要看常数、数据规模和数据分布。我自己实测下来的经验是随机大数据场景下快速排序通常是几个 O(n log n) 算法里最快的归并排序稳定但空间开销大堆排序虽然复杂度稳定但实际交换次数多常数不小。如果要做选择可以参考这套思路数据量很小或者数组已经接近有序选插入排序。数据量较大、基本随机且不要求稳定选快速排序。数据量较大要求稳定且内存足够选归并排序。数据量大内存非常紧张且不需要稳定选堆排序。数据范围很小且是整数选计数排序。数据位数不多且都是整数选基数排序。数据分布均匀选桶排序。很多人在实际项目里会用库函数这个没问题。但你用库函数前也要知道它背后是哪一种策略这样在算法题手写排序时你才能写得更快、更稳。最后再分享一个我自己的调试习惯写完排序后不要只验证“排没排对”还要验证“稳不稳定”。我会在建一个int[]时额外记录元素原来的下标如果排序结束后两个相等元素的下标顺序变了说明算法不稳定。排序这块内容一旦吃透后面学二分、双指针、分治、海量数据排序都会顺很多。
