常见排序算法Java实现讲句实在话排序算法这个东西几乎是所有Java开发者逃不过去的一道坎。校招面试要问社招跳槽要问就连工作三五年回去带新人讲数据结构的时候还是得从排序说起。我当年准备面试的时候把冒泡、选择、插入、快排、归并这些算法反反复复手写了不知道多少遍后来去面别人发现大部分候选人也都在背这几种排序但真正能把原理讲清楚、能把代码写得滴水不漏的其实不多。这篇文章就把常见的排序算法用Java挨个实现一遍包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序以及一些特定场景下才会用到的计数排序。每个算法我都会讲清楚它的核心思想、代码实现、时间复杂度分析还会结合实际业务场景说说什么时候该用哪个。不管你是在准备面试还是想系统地补一下算法基础这篇文章都值得你认真看一遍。1. 内容整体设计与思路拆解1.1 为什么要反复啃排序算法很多人觉得排序算法在业务开发中根本用不到项目里直接用Collections.sort()或者Stream.sorted()就完事了。这话对了一半但另一半才是关键框架帮我们封装好了排序的实现可排序算法本身承载的不仅仅是“排个序”这个动作它背后牵扯到时间复杂度分析、空间复杂度权衡、稳定性判断、分治思想、递归思维等一系列编程基本功。举个例子你去看JDK的Arrays.sort()源码会发现它对不同数据规模、不同数据类型采用了不同的排序策略小数组用插入排序大数组用快速排序对象数组用归并排序TimSort。为什么这么设计原因就是不同排序算法在不同场景下的表现差异非常大。你要是没真正理解这些算法的原理看源码看得一头雾水改起性能问题来也无从下手。再往实际了说我见过不少同事在处理“TOPK”问题的时候上来就把全量数据排序然后取前十个。数据量小还好说数据量一上来内存和时间双重爆炸。如果懂堆排序用一个大小为K的小顶堆就能优雅地解决这个问题。这就是懂算法和不懂算法的差别。1.2 算法分类与选型总览排序算法可以从多个维度去分类。按时间复杂度分有O(n²)级别的冒泡、选择、插入有O(nlogn)级别的希尔、归并、快排、堆排还有O(nk)级别的线性排序计数、桶、基数。按空间复杂度分有原地排序不需要额外内存和非原地排序需要额外内存之分。按稳定性分有稳定排序相等元素的相对位置不变和不稳定排序。我在实际项目里做技术选型的时候基本上遵循这样一套思路数据量小几百以内直接用插入排序代码简单性能也够数据量中等几千到几万用快速排序数据量特别大、又要求稳定用归并排序如果是求TopK用堆排序如果数据有特殊的范围限制比如0到100的分数计数排序和桶排序能给你惊喜。下表是我整理的常用排序算法核心参数对比建议保存到你的笔记里排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n²)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(n²)O(logn)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定计数排序O(nk)O(nk)O(k)稳定注意一个容易踩坑的点稳定性不是指算法性能稳不稳定而是指排序后相等元素的相对顺序是否保持不变。如果需求是“先按时间倒序再按优先级正序”那就必须先按优先级排序再按时间排序这时候第二轮的排序就必须用稳定排序否则第一轮的优先级顺序会被打乱。2. 基础排序冒泡、选择、插入的对比与实现2.1 冒泡排序冒泡排序的思路最简单直观从头开始依次比较相邻的两个元素如果前一个比后一个大就交换位置。这样每一轮下来最大的元素就像气泡一样“浮”到了数组末尾。重复n-1轮整个数组就排好了。public class BubbleSort { 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) { // 每一轮确定一个最大值放到末尾所以内层循环只需遍历到 n-1-i for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); } } } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }这个最基本的实现其实还有优化空间我给你写一个带“提前退出”机制的版本public class BubbleSortOptimized { 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; } } }这个优化在应对“已经接近有序”的数据时效果非常明显。比如数据是[1, 2, 3, 5, 4, 6, 7]第一轮交换完5和4之后第二轮再扫描会发现没有任何交换发生直接跳出循环时间复杂度从 O(n²) 降到了 O(n)。但是说实话我在实际开发中几乎不用冒泡排序。它的唯一优势就是代码好写、逻辑直观教学意义大于实战意义。真要排小数据量插入排序的表现几乎总是好于冒泡。2.2 选择排序选择排序的思路也很简单每一轮从未排序的区间中找到最小值把它放到已排序区间的末尾。可以理解为“打擂台”每轮决出当前最小的那个元素。public class SelectionSort { public static void selectionSort(int[] arr) { if (arr null || arr.length 2) return; 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²) 的时间复杂度没有优化空间。这意味着即使数据已经是排好序的选择排序依然会傻乎乎地跑完所有比较。还有一个经常被面试官追问的细节选择排序不稳定。举个例子数组[5, 8, 5, 2, 9]第一轮找到最小元素2位置在索引3然后和索引0位置的5交换这时候两个5的相对顺序就变了本来在前面的5被换到了后面所以在“相同元素保持稳定”的需求下选择排序是不能用的。2.3 插入排序插入排序的思路类似玩扑克牌时的理牌动作从第二个元素开始依次把每个元素插入到前面已经排好序的子数组中的合适位置。public class InsertionSort { public static void insertionSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; for (int i 1; i n; i) { int current arr[i]; int j i - 1; // 从后往前找插入位置同时向后移动元素 while (j 0 arr[j] current) { arr[j 1] arr[j]; j--; } arr[j 1] current; } } }这里有一个值得注意的编码细节我先把arr[i]存到current变量里然后在 while 循环里统一往后移动元素最后再把current放到正确的位置。如果你不存临时变量而是直接在 while 里用swap代码看起来简单了但每次交换涉及三次赋值整体耗时反而更高。特别是数据量大的时候这个差距会很明显。插入排序在“接近有序”的数据集上表现极好时间复杂度可以逼近 O(n)。这也是为什么JDK的Arrays.sort()在对小规模数组排序时会采用插入排序变体因为小规模数据用O(n²)级别的插入排序常数因子小实际执行效率往往比复杂的O(nlogn)排序更高。3. 进阶排序归并、快排、堆排的核心原理与实现3.1 归并排序归并排序是典型的“分而治之”思想。先把数组从中间分成两半分别对左右两半排序然后把两个有序的子数组合并成一个有序的完整数组。递归地进行下去直到子数组只有一个元素天然有序为止。public class MergeSort { public static void mergeSort(int[] arr) { if (arr null || arr.length 2) return; 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); } }归并排序有几个点值得展开讲。首先是原地归并的技巧。上面这个实现里我每次merge都会创建一个临时数组。如果频繁创建数组内存开销比较大。一个常见的优化是在递归之前先创建一个和原数组等长的临时数组然后在merge的时候通过arraycopy在不同位置之间拷贝复用同一个临时数组。这样可以将空间复杂度从 O(nlogn) 优化到 O(n)。其次是稳定性。注意 merge 过程中当arr[i]和arr[j]相等时我取的是左边的元素。用这个符号就是为了保证相等元素的相对顺序不改变。如果你写成相等元素会被先从右边取出来稳定性就丢失了。面试的时候这个细节经常被追问。最后是应用场景。归并排序的额外空间是 O(n)所以对于特别大的数据量比如内存放不下需要外部排序的场景归并排序反而是首选。像大数据领域里的外部排序基本就是归并排序的变体。3.2 快速排序快速排序也是分治思想但它和归并排序的思路相反归并排序是先递归处理子问题再合并快速排序则是先做分区partition把数组分成“小于基准值”和“大于等于基准值”两部分然后再递归处理这两部分。public class QuickSort { public static void quickSort(int[] arr) { if (arr null || arr.length 2) return; 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) { swap(arr, i, j); i; } } swap(arr, i, right); return i; } }经典的快排实现基准值取最后一个元素。如果面试官要求“优化版”通常会在以下几个方向做文章基准值的选择三数取中。如果数组本身已经有序每次取最后一个元素作为基准值会导致每次分区极度不平衡递归深度退化成 O(n)时间复杂度退化成 O(n²)。规避办法是“三数取中”取左端点、中点、右端点三个元素中的中位数作为基准值。这样一来面对有序数组时也能得到一个相对平衡的分区。private static int medianOfThree(int[] arr, int left, int right) { int mid left (right - left) / 2; 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; }双路快排处理大量重复元素。上面这个分区实现遇到数组里有大量重复元素时会出现一个问题等于基准值的元素被分到哪一边取决于具体实现可能导致两边严重不平衡。双路快排的思路是从左边找大于等于基准值的元素从右边找小于等于基准值的元素一旦都找到就交换让等于基准值的元素均匀分布在两侧。三路快排彻底解决重复元素问题。三路快排把数组分成三个区域小于基准值的、等于基准值的、大于基准值的。等于基准值的区域直接不参与后续递归。对于重复元素极多的场景比如成绩单排序一半人的分数都一样三路快排能大幅提升效率时间复杂度接近 O(n)。我之前在面试别人的时候喜欢让候选人写快排然后追问“如果数据是[1, 2, 3, 4, 5, 6, 7, 8, 9]你的性能会怎样”。很多候选人会愣住因为根本没想过快排也有最坏情况。能答出来“退化到O(n²)”并且说出“三数取中”这个策略的基本就过关了。3.3 堆排序堆排序利用了二叉堆这种数据结构的特性。给你一个无序数组先把它调整成一个大顶堆父节点的值大于等于子节点然后依次把堆顶元素最大值和堆的最后一个元素交换交换后堆的大小减一再对剩余元素重新调整堆。重复这个过程就完成了排序。public class HeapSort { public static void heapSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; // 建堆从最后一个非叶子节点开始逐个下沉调整 for (int i n / 2 - 1; i 0; i--) { heapify(arr, i, n); } // 依次取出堆顶元素放到数组末尾 for (int i n - 1; i 0; i--) { swap(arr, 0, i); heapify(arr, 0, i); } } private static void heapify(int[] arr, int i, int n) { 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) { swap(arr, i, largest); heapify(arr, largest, n); } } }堆排序有两个非常典型的应用场景这两个场景在实际开发中出镜率极高。第一个是TopK问题。如果要从海量数据比如几亿条日志中找出最大的100条全量排序肯定不现实。正确做法是维护一个大小为100的小顶堆遍历数据时如果当前元素比堆顶元素大就弹出堆顶将当前元素入堆。遍历完成后堆里就是最大的100个元素。这个过程的时间复杂度是 O(nlogk)当 k 远小于 n 时效率非常惊人。第二个是优先队列。Java中的PriorityQueue底层就是堆实现。我做一个任务调度模块的时候就需要按优先级动态地取任务插入和取出的时间复杂度都是 O(logn)用堆实现再合适不过。堆排序本身作为独立排序算法日常业务中用得不如快排和归并多但堆这种数据结构的思想很重要掌握了堆排序再看优先队列、延迟队列、定时任务等组件思路会清晰得多。4. 线性排序计数排序的实现与适用场景4.1 计数排序前面讲的所有排序都是基于“比较”的排序时间复杂度下界是 O(nlogn)。但有一种情况可以突破这个限制当待排序的数据范围有限且已知时可以用计数排序在 O(nk) 时间内完成排序k 是数据范围。思路很简单先扫描一遍数组统计每个值出现的次数然后根据统计信息重建排序后的数组。public class CountingSort { public static void countingSort(int[] arr) { if (arr null || arr.length 2) return; int n arr.length; // 找到最小值和最大值确定计数数组的范围 int min arr[0], max arr[0]; for (int value : arr) { if (value min) min value; if (value max) max value; } int range max - min 1; int[] count new int[range]; // 统计每个元素出现的次数 for (int value : arr) { count[value - min]; } // 把统计结果逐项写回原数组 int index 0; for (int i 0; i range; i) { while (count[i] 0) { arr[index] i min; count[i]--; } } } }我这里做了一点优化先找到数组的最小值再用value - min作为下标。这样即使数据范围是[1000, 1100]计数数组也能只开101个位置而不是1100个位置。如果不做这个偏移处理计数排序对数据范围大但实际数据集中的情况会浪费大量内存。举个业务场景一个班50个学生考试成绩都在0到100分之间要对成绩排序。这时候用计数排序一次扫描就能完成排序比快排还快。再比如对IP地址的前缀做统计、对年龄做分布统计只要你确认了数据范围可控计数排序就是最优解。4.2 桶排序桶排序是计数排序的一种扩展思路。计数排序把每个值单独占一个“桶”桶排序则是把一定范围的值分到同一个桶里每个桶内部再用其他排序算法通常是插入排序或快速排序排序最后把所有桶里的数据按顺序拼接起来。举例来说对[0, 1]之间均匀分布的浮点数排序可以把数据分成10个桶[0, 0.1)、[0.1, 0.2)等等每个桶分别排序最后拼接。桶排序的关键在于数据要均匀分布否则大量数据堆到某一个桶里性能就退化了。桶排序在Java中的一个典型应用是Collections.sort()对LinkedList的排序JDK里就是先把链表拆成若干子链表分别排序后再合并本质上就是桶排序思路。4.3 基数排序基数排序是另一种线性排序思路它把整数按位拆开依次按个位、十位、百位进行排序。每一轮排序都要求是稳定的通常配合计数排序来实现。举个例子排序[170, 45, 75, 90, 802, 24, 2, 66]先按个位排序再按十位排序再按百位排序。由于每轮都是稳定排序三轮下来整个数组自然就有序了。我在实际工作中用基数排序的场景不多因为它要求数据能用固定位数表示而且排序数字效率不如直接调用Arrays.sort()。但了解一下没有坏处特别是你面试的时候能说出“对手机号、身份证号这种位数固定的数据排序”面试官会觉得你知识面够宽。5. 各排序算法对比与选型策略5.1 从性能指标看选型我整理了一个“什么时候用哪个排序”的决策思路这比背参数表更管用数组几乎有序数据量不大几百以内插入排序。最好情况O(n)的时间复杂度几乎没有额外空间开销代码还简单。JDK内部就是这么干的。数据量中等几万到几十万没有稳定性要求快速排序。平均性能最好常数因子小。Java的Arrays.sort()对基本类型数组就是用的双轴快排。数据量大而且要求稳定比如订单按时间金额排序后还需要保持先前的排序规则归并排序。TimSort就是归并排序的优化版Java对对象数组的排序就是它。求最大/最小的K个数堆排序的小顶堆/大顶堆方案时间复杂度O(nlogk)内存只占用O(k)在海量数据场景下几乎是唯一选择。数据范围小且已知如成绩0-100年龄0-120计数排序一趟搞定时间复杂度逼近O(n)。5.2 稳定性到底有多重要我单独再说一下稳定性因为这个概念在实际业务里太容易被忽略但踩过一次坑就再也不会忘了。假设你是做电商的需要把订单先按“地区”分组展示组内再按“下单时间”排序。这时候的常规做法是先按下单时间排序再按地区排序。如果第二次排序用的是不稳定排序那么同一地区内的订单时间顺序可能就被打乱了。这时候必须用稳定排序。Java里的Collections.sort()用的是TimSort是稳定排序所以你可以放心地连续多次按不同字段排序。但如果你自己实现排序就需要特别注意这个点。5.3 实际项目里的性能实测我去年处理过一个性能优化需求一个接口需要对几万条用户数据进行多条件排序原来用的是Collections.sort() 自定义Comparator耗时在80ms左右。后来我分析了一下数据特征发现排序字段其实就两个而且第二个字段的取值范围特别小只有几种状态值。于是我把排序策略改成了“先按状态值做计数排序分组组内再用快排按下单时间排序”。一趟优化下来接口耗时降到了20ms以内。这个例子说明理解排序算法的本质不是让你天天手写排序而是让你在关键时刻能想到用合适的算法去解决问题。6. 常见问题与排查技巧实录6.1 快排最怕的输入是什么最怕已经有序或逆序的数组。传统实现下递归深度退化成O(n)可能触发栈溢出时间上也会退化到O(n²)。处理办法就是前面说的三数取中或者随机选取基准值。如果你在生产环境用了快排而数据又可能是有序的建议直接上随机化快排或三路快排。6.2 归并排序为什么没有被快排完全替代主要就是两个原因一是稳定性归并排序是稳定排序二是对链表等非随机访问数据结构归并排序依然高效而快排依赖数组的下标随机访问用链表实现时性能会大打折扣。另外归并排序在数据规模极大、需要外部排序的时候几乎是唯一靠谱的选择。6.3 手写排序时最常见的Bug我在日常code review和面试中见到最多的BUG集中在三类边界条件处理错误。比如快排的递归边界写成if (left right)而不是if (left right)当数组长度为2时可能因为传入的left right而导致无限递归。这类错误写代码时就要注意加上防护判断省得出现问题后排查半天。swap操作的错误。有些同学喜欢用位运算写交换像a ^ b; b ^ a; a ^ b;这个写法在i j时会把同一个地址的值变成0导致数据丢失。所以除非能保证交换的两个下标不同否则老老实实写临时变量。计数排序的偏移量遗漏。计数排序如果忘了处理最小值不为0的情况会导致数组越界。我给出的代码里用value - min作为下标就是为了规避这个问题。6.4 面试考排序到底在考什么我面试Java候选人的时候只要时间允许一定会让写一道排序。但我考察的重点从来不是“能不能默写出来”而是以下几点能不能说清每个算法的核心思想而不是背代码。比如快排的核心是partition归并的核心是merge堆排的核心是heapify。能不能分析时间复杂度和空间复杂度并且说明这个复杂度是怎么推导出来的。知不知道稳定性的概念能不能举出需要稳定性的实际场景。能不能针对特定输入做优化比如重复元素多的数组、几乎有序的数组、超大规模的数据。如果你能围绕这四点把排序讲透面试官很难不给高分。6.5 一个百试百灵的编码小习惯最后分享一个我在实际编码中养成的习惯写排序算法时先把数组的边界情况和空值检查写清楚再写核心逻辑。if (arr null || arr.length 2) return;这一行几乎每个排序算法都是通用的。这样写的好处有两个一是调用方传了空数组或者单元素数组时不会出错二是递归调用时不用在每一层递归里反复判断边界核心逻辑更清晰。还有一个习惯就是尽量把“交换元素”的逻辑抽取成一个独立的swap方法。排序算法里到处是交换抽成方法后代码可读性大幅提高也不容易出错。这篇文章几乎把我这些年用到的排序算法的经验和踩过的坑都写了一遍。说到底排序算法不是背出来的是写出来的。建议你把文中的代码挨个自己抄一遍、跑一遍、改一改比如试着把快排改成随机基准、把归并改成迭代实现、把插入排序改成二分插入排序。动手改过一遍比在纸上画十遍都管用。至少我在当初学习的时候是通过反复手写、改错、跑测试才真正把这些算法变成自己的东西的。