前言

这篇文章是基于个人学习体会整理而来，主要介绍七种常见的基于比较的排序算法基本原理及实现、排序算法的性能分析、 java 中的常用排序方法。如果内容有不足之处，非常欢迎大家一起指正和交流！

1. 排序的基本概念

1.1 排序是什么？

排序算法，可以说是《数据结构与算法》这门课里最基础、也最重要的一环。常见的排序算法有很多，比如插入排序、希尔排序、选择排序、冒泡排序、归并排序、堆排序等等。

在开始之前，我们先明确几个基本概念：

内部排序 vs 外部排序：

• 内部排序：可以想象成所有需要排序的数据都能一股脑儿地放进电脑内存里进行处理。
• 外部排序：当数据量非常大，内存一次性装不下时，就需要借助硬盘等外部存储，在内存和外存之间来回倒腾数据来完成排序。

排序 (Sort)：

• 简单来说，排序就是让一串数据记录，根据其中我们关心的某个关键信息（比如数字的大小、字母的顺序），按照从小到大（递增）或从大到小（递减）的规则重新排列。

稳定性 (Stability)：

• 这是一个衡量排序算法性质的重要指标。设想一下，如果我们要排序的数据里有好几个值是相同的。经过排序后，如果这些相同值的记录，它们之间的相对位置和排序前保持一致，那这种排序算法就是稳定的。反之，如果它们的相对顺序被打乱了，那就是不稳定的。
• 举个例子，假设原序列中有两个记录 r[i] 和 r[j]，它们的值相等，并且 r[i] 在 r[j] 的前面。如果排序后，r[i] 仍然在 r[j] 的前面，那么这个排序算法就是稳定的。

1.2 常见的排序算法概览

为了对各种排序算法有个整体的印象，我们可以通过下面这张图来梳理一下它们的分类关系。

2. 常见排序算法的实现

2.1 插入排序 (Insertion Sort)

2.1.1 基本思想

插入排序（Insertion Sort）是一种非常直观的排序算法。它的工作原理可以联想一下我们平时打扑克牌整理手牌的过程：每次摸一张新牌，都会把它插入到已经排好序的手牌中的合适位置，直到所有牌都摸完，手牌也就变得有序了。

2.1.2 直接插入排序

直接插入排序是插入排序中最基础的一种。它的核心思路是：通过构建一个有序序列，对于还没排序的数据，在已排序的序列中从后往前扫描，找到它应该在的位置并插入进去。

我们可以这样想象整个过程：当处理到第 i 个元素时（i 从 1 开始），我们假定它前面的 array[0] 到 array[i-1] 这些元素已经是有序的了。现在，我们需要为 array[i] 这个新来的元素找到它的位置。我们拿着 array[i] 从后往前，依次和 array[i-1], array[i-2]… 这些比较，直到找到一个比它小或等于它的元素，那么那个位置的后面就是 array[i] 的新位置。为了给它腾出位置，所有比它大的元素都需要顺序地向后挪一个位置。

参考代码：

    /*** 直接插入排序* 时间复杂度：O(N^2)* 空间复杂度：O(1)* 稳定性：稳定的* 一个本身是稳定的排序可以被实现为不稳定的，但反过来则不行。* 最好情况：当数组本身就是有序的，时间复杂度为 O(N)。数据越趋于有序，直接插入排序的效率就越高。* @param array 待排序数组*/public static void insertSort(int[] array) {// 从第二个元素开始，逐个进行插入操作for (int i = 1; i < array.length; i++) {int tmp = array[i]; // 记录下当前要插入的元素int j = i - 1;// 从已排序序列的末尾开始向前查找插入位置for (; j >= 0; j--) {// 如果当前元素大于要插入的元素，则将其后移if (array[j] > tmp) {array[j + 1] = array[j];} else {// 找到了比 tmp 小或等于的元素，说明 tmp 应该插在这里的后面break;}}// 将 tmp 放置到正确的插入位置array[j + 1] = tmp;}}

直接插入排序的特性总结：

1. 数据敏感性：元素集合越接近有序，直接插入排序算法的时间效率就越高。
2. 时间复杂度：平均和最坏情况下都是 O(N^2)。
3. 空间复杂度：O(1)，因为它是一个原地排序算法。
4. 稳定性：稳定。

优缺点分析

• 优点：
  • 实现起来很简单，代码逻辑清晰易懂。
  • 对于小规模数据或者基本有序的数据，排序效率相当不错。
  • 是原地排序，几乎不需要额外的存储空间。
  • 是一种稳定的排序算法，能保证相同元素的相对顺序不变。
• 缺点：
  • 时间复杂度是 O(N^2)，当数据量很大时，性能会急剧下降，不太适合处理大规模数据集。

2.1.3 希尔排序 (Shell Sort)

希尔排序，可以看作是直接插入排序的“威力加强版”，它的另一个名字叫“缩小增量排序”。这个名字很形象地道出了它的精髓。

我们知道直接插入排序有两个特点：

• 当数据几乎有序时，它的效率非常高，接近线性时间 O(N)。
• 但在大多数情况下，它效率又很低，因为元素每次只能移动一个位置，像“龟速”一样。

希尔排序正是抓住了这两点，进行了一次非常巧妙的优化。它的核心思想是：先让数组变得“大致有序”，再进行最终的插入排序。

具体怎么做呢？它引入了一个“增量”gap的概念。

1. 分组预排序：先选择一个较大的增量 gap（比如数组长度的一半），将整个数组按照这个增量分成若干个小组。例如，array[0], array[gap], array[2*gap]… 属于一个组；array[1], array[1+gap], array[1+2*gap]… 属于另一个组。然后对每个小组内部进行直接插入排序。这一步的目的就是让数据进行“大跨步”的移动，快速将较小的元素移动到前面，较大的元素移动到后面，让整个数组迅速变得“基本有序”。
2. 缩小增量，重复过程：完成一轮后，缩小增量 gap（比如再除以2），然后重复上面的分组和组内排序过程。随着 gap 的不断缩小，整个数组的有序程度会越来越高。
3. 最终排序：当增量 gap 缩小到 1 时，整个数组已经非常接近有序了。此时再对全体记录进行一次直接插入排序，由于数据已经“基本有序”，这次排序的效率会非常高。

这个动图可能有点快，有点难理解。我们自己画一个来展示🖌

参考代码：

    /*** 希尔排序* 时间复杂度：约为 O(N^1.3) 到 O(N^1.5)，取决于增量序列的选择* 空间复杂度：O(1)* 稳定性：不稳定的* @param array 待排序数组*/public static void shellSort(int[] array) {// 初始增量为数组长度int gap = array.length;// 循环缩小增量，直到增量为1while (gap > 1) {// 每次将增量减半gap /= 2;// 对当前增量下的各个分组进行插入排序shell(array, gap);// 这里的写法是单纯为了接口(主函数只传递一个array参数)统一多套了一层方法}}/*** 对指定增量(gap)的子序列进行直接插入排序* @param array 待排序数组* @param gap   增量*/private static void shell(int[] array, int gap) {// 从第 gap 个元素开始，逐个对其所在组进行插入排序for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i - gap;// 在组内进行插入排序for (; j >= 0; j -= gap) {if (array[j] > tmp) {// 将大于 tmp 的元素后移array[j + gap] = array[j];} else {// 找到插入位置break;}}// 将 tmp 插入到正确的位置array[j + gap] = tmp;}}

希尔排序的特性总结：

1. 优化思路：希尔排序可以看作是对直接插入排序的一种分组优化策略。
2. 预排序：当 gap > 1 时，所做的都是预排序，目的是让整个数组宏观上变得越来越有序。当 gap == 1 时，数组已经非常接近有序状态，此时的直接插入排序效率极高，从而达到了整体优化的效果。
3. 时间复杂度：希尔排序的时间复杂度是一个比较复杂的数学问题，因为它严重依赖于 gap 增量序列的选择。目前还没有一个公认的最优增量序列。通常认为其时间复杂度在 O(N^1.3) 到 O(N^1.5) 之间，比 O(N^2) 要好得多。
4. 稳定性：由于相同元素的记录可能被分到不同的子序列中，它们的相对顺序可能会在排序过程中发生改变，因此希尔排序是不稳定的。

关于 gap 的选择

增量序列的选择是希尔排序性能的关键。不同的教材和文献中给出了不同的建议。

在《数据结构(C语言版)》 by 严蔚敏 中，建议的增量序列是 n/2, n/4, ..., 1。

而在《数据结构-用面向对象方法与C++描述》 by 殷人昆 中，提到了其他可能的序列。

著名计算机科学家 Knuth 经过大量实验，提出了一个经典的增量序列 1, 4, 13, 40, ...，其性能相对较好。在实际应用中，我们通常采用 n/2 的方式，因为它简单且效果尚可。根据估算，其时间复杂度大约在：
$$O(n^{1.25})\text{ 到 }O(1.6\times n^{1.25})$$

2.2 选择排序 (Selection Sort)

选择排序（Selection Sort）的思路非常耿直：每一次遍历，都只为了做一件事——找到当前范围里最小（或最大）的那个元素，然后把它放到队伍的末尾（或开头）。

这种算法有一个很“公平”的特点：不管输入的数据长什么样，它都勤勤恳恳地执行 O(N²) 次操作，从不偷懒。所以，它比较适合那些数据规模不大的场景。要说优点，可能就是它不需要额外的内存空间。

2.2.1 直接选择排序

直接选择排序是选择排序最直接的实现。它的工作流程可以分解为以下几步：

1. 首先，在整个数组 array[0] 到 array[n-1] 中，地毯式搜索，找到最小的那个元素。
2. 然后，把它和 array[0] 位置的元素交换。这样，整个数组中最小的元素就“归位”了。
3. 接下来，在剩下的 array[1] 到 array[n-1] 中，重复上面的过程：找到这个范围内的最小值，和 array[1] 交换。
4. 如此循环，每次都从“待排序”的部分里选出最小的，放到“已排序”部分的末尾，直到所有元素都“归位”。

参考代码：

    /*** 直接选择排序* 时间复杂度：O(N^2)，与数据初始顺序无关* 空间复杂度：O(1)* 稳定性：不稳定的* @param array 待排序数组*/public static void selectSort(int[] array) {// 外层循环控制排序的轮数，也代表了已排序区间的末尾for (int i = 0; i < array.length; i++) {int minIndex = i; // 假设当前位置的元素是未排序区间的最小值// 内层循环在未排序区间 [i+1, array.length) 中寻找真正的最小值for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {minIndex = j; // 如果找到更小的值，更新最小值的索引}}// 将找到的最小值与当前轮次的起始位置交换swap(array, i, minIndex);}}/*** 双向选择排序 (优化版)* 在一轮中同时找到最大值和最小值*/public static void selectSort2(int[] array) {int left = 0;int right = array.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;// 在 [left, right] 区间内寻找最大值和最小值的索引for (int i = left + 1; i <= right; i++) {if (array[i] < array[minIndex]) {minIndex = i;}if (array[i] > array[maxIndex]) {maxIndex = i;}}// 将最小值交换到左边界swap(array, left, minIndex);// 这里有个小陷阱：如果本轮的最大值恰好在 left 位置，// 经过上一步交换，它已经被换到了 minIndex 的位置，所以需要更新 maxIndex。if (maxIndex == left) {maxIndex = minIndex;}// 将最大值交换到右边界swap(array, right, maxIndex);left++;right--;}}

关于 selectSort2 的一点思考：
这种“双向选择排序”的优化，并没有从根本上改变选择排序 O(N²) 的时间复杂度。它的改进主要体现在“常数”级别上，通过在一轮遍历中同时搞定最大和最小两个元素，使得外层循环的次数减少了一半。
在实际测试中，对于中等规模的数据，这种优化可能会带来一些可见的性能提升。但对于大数据集，它依然无法和 O(N log N) 的高效排序算法（如快排、归并、堆排）相比较速度。同时，代码逻辑也变得更复杂了，尤其要注意 maxIndex 的更新，算是一种用代码简洁性换取微小性能提升的尝试。

直接选择排序的特性总结：

1. 易于理解：思路简单清晰，但效率不高，在实际工程中很少被采用。
2. 时间复杂度：O(N²)，雷打不动。
3. 空间复杂度：O(1)，原地排序。
4. 稳定性：不稳定。比如序列 [5, 8, 5, 2, 9]，第一轮会把第一个 5 和 2 交换，导致两个 5 的相对顺序改变。

2.2.2 堆排序 (Heap Sort)

堆排序（Heap Sort）可以看作是选择排序的一种高阶进化版。它巧妙地利用了“堆”这个数据结构来高效地完成“选择”这个动作。

在开始之前，有个关键点需要记住：排升序要建大顶堆，排降序要建小顶堆。为什么呢？

• 大顶堆：每个节点的值都比它的子节点大或相等。这意味着堆顶元素永远是整个堆里最大的。
• 小顶堆：每个节点的值都比它的子节点小或相等。这意味着堆顶元素永远是整个堆里最小的。

堆排序的过程分为两大步：

1. 建堆：将无序的数组原地构建成一个大顶堆（以升序为例）。
2. 排序：
   a. 将堆顶元素（当前最大值）与堆末尾的元素交换。此时，最大的元素就“归位”到了数组的末尾。
   b. 将剩余的 n-1 个元素重新调整成一个新的大顶堆。
   c. 重复上述过程，每次都将当前堆的最大值交换到末尾，直到所有元素都有序。

参考代码：

    /*** 堆排序 (升序)* 时间复杂度：O(N*logN)* 空间复杂度：O(1)* 稳定性：不稳定的* @param array 待排序数组*/public static void heapSort(int[] array) {// 1. 将无序数组构建成一个大顶堆createHeap(array);int end = array.length - 1;// 2. 循环将堆顶元素与末尾元素交换，并重新调整堆while (end > 0) {swap(array, 0, end); // 将堆顶(最大值)交换到数组末尾siftDown(array, 0, end); // 对 [0, end) 区间重新进行向下调整end--;}}/*** 构建大顶堆* 从最后一个非叶子节点开始，自下而上，自右向左进行向下调整*/private static void createHeap(int[] array) {for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {siftDown(array, parent, array.length);}}/*** 向下调整算法 (大顶堆)* @param array 数组* @param parent 要调整的子树的根节点索引* @param len    堆的有效长度*/private static void siftDown(int[] array, int parent, int len) {int child = 2 * parent + 1; // 左孩子while (child < len) {// 如果右孩子存在且大于左孩子，则选择右孩子进行比较if (child + 1 < len && array[child] < array[child + 1]) {child++;}// 如果父节点小于子节点中的较大者，则交换if (array[child] > array[parent]) {swap(array, parent, child);// 继续向下调整parent = child;child = 2 * parent + 1;} else {// 如果父节点已经大于等于两个子节点，则调整完成break;}}}

堆排序的特性总结：

1. 效率提升：通过使用堆这种数据结构，堆排序将选择过程的效率从 O(N) 提升到了 O(logN)，使得整体排序效率大大提高。
2. 时间复杂度：O(N*logN)。
3. 空间复杂度：O(1)，原地排序。
4. 稳定性：不稳定。

2.3 交换排序

交换排序的核心思想很简单：通过比较序列中两个元素的值，来决定是否交换它们的位置。这类排序的共同特点是：努力将值大的元素往序列尾部移动，值小的元素往序列前部移动。

2.3.1 冒泡排序 (Bubble Sort)

冒泡排序（Bubble Sort）可能是我们接触的第一个排序算法，非常经典。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来也很有趣，因为越小的元素会经由交换慢慢“浮”到数列的顶端，就像碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样。

参考代码：

    /*** 冒泡排序 (优化版)* 时间复杂度：最坏 O(N^2)，最好 O(N)* 空间复杂度：O(1)* 稳定性：稳定的* @param array 待排序数组*/public static void bubbleSort(int[] array) {// 外层循环控制排序的轮数for (int i = 0; i < array.length - 1; i++) {boolean flag = false; // 优化标志位// 内层循环进行相邻元素的比较和交换for (int j = 0; j < array.length - 1 - i; j++) {if (array[j] > array[j + 1]) {swap(array, j, j + 1);flag = true; // 发生了交换}}// 如果在一整轮比较中都没有发生任何交换，说明数组已经有序if (!flag) {break; // 提前结束排序}}}

冒泡排序的特性总结：

1. 易于理解：冒泡排序是交换排序中最容易理解的一种。
2. 时间复杂度：O(N²)。虽然有优化，但在最坏情况下依然是这个量级。
3. 空间复杂度：O(1)。
4. 稳定性：稳定。

2.3.2 快速排序 (Quick Sort)

快速排序（Quick Sort）是由图灵奖得主 Hoare 在 1962 年提出的。它的思想完美体现了分治法（Divide and Conquer）。

核心思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

可以说，快速排序是冒泡排序的一种递归分治改进版本。它的名字起得名副其实，就是快！在处理大规模数据时，它是目前公认的最快的排序算法之一。

    // 快速排序主框架 (递归)void quickSort(int[] array, int left, int right) {// 递归终止条件：区间只有一个或没有元素if (left >= right) {return;}// 核心步骤：对 [left, right] 区间进行分区，找到基准值的最终位置int pivotIndex = partition(array, left, right);// 分治：递归地对左右两个子区间进行排序quickSort(array, left, pivotIndex - 1);quickSort(array, pivotIndex + 1, right);}

这个递归框架和二叉树的前序遍历非常相似，理解了这一点，就能很快地写出主干代码。接下来的关键，就在于如何实现 partition（分区）这个核心操作。

partition 的目标是：在数组的一个区间内，选定一个基准值（pivot），然后将所有小于基准值的元素移动到它的左边，所有大于基准值的元素移动到它的右边，最后返回基准值所在的最终索引。

常见的 partition 实现方式有三种：

2.3.2.1 Hoare 法

这是 Hoare 本人提出的原始版本。

• 思路：选定最左边的元素为基准值。设置左右两个指针，右指针从右向左找第一个小于基准值的数，左指针从左向右找第一个大于基准值的数，然后交换它们。重复这个过程，直到左右指针相遇，最后将基准值与相遇位置的元素交换。

    // Hoare 分区法private static int partitionHoare(int[] array, int left, int right) {int pivotIndex = left; // 基准值的初始索引int pivot = array[left]; // 基准值while (left < right) {// 右指针从右向左找小while (left < right && array[right] >= pivot) {right--;}// 左指针从左向右找大while (left < right && array[left] <= pivot) {left++;}swap(array, left, right);}// 将基准值换到相遇点swap(array, pivotIndex, left);return left; // 返回基准值最终的位置}

2.3.2.2 挖坑法

挖坑法是对 Hoare 法的一种形象化理解，更容易掌握。

• 思路：将最左边的元素（基准值）挖出来，形成第一个“坑”。然后右指针从右向左找一个小的数，填到左边的坑里，自己形成一个新的坑。接着左指针从左向右找一个大的数，填到右边的坑里，自己又形成一个新坑。如此交替，直到左右指针相遇，最后将最初挖出的基准值填入最后一个坑中。
  

    // 挖坑法private static int partitionWiggle(int[] array, int left, int right) {int pivot = array[left]; // 将基准值挖出，形成第一个坑while (left < right) {// 右指针找小，填左坑while (left < right && array[right] >= pivot) {right--;}array[left] = array[right]; // 填坑// 左指针找大，填右坑while (left < right && array[left] <= pivot) {left++;}array[right] = array[left]; // 填坑}array[left] = pivot; // 将基准值填入最后的坑return left;}

2.3.2.3 前后指针法

这种方法也非常经典，思路清晰。

• 思路：选定最左边的元素为基准值。使用两个指针 prev 和 cur，prev 指向“小于基准值区域”的末尾，cur 负责向右遍历数组。如果 cur 遇到的元素小于基准值，就将 prev 向后移动一位，并交换 prev 和 cur 指向的元素。遍历结束后，将基准值与 prev 指向的元素交换即可。

    // 前后指针法private static int partitionPointer(int[] array, int left, int right) {int pivot = array[left];int prev = left; // “小于区域”的边界for (int cur = left + 1; cur <= right; cur++) {if (array[cur] < pivot) {prev++;swap(array, cur, prev);}}swap(array, left, prev);return prev;}

三种分区方法的比较

• Hoare 法：是快排的“原版”实现，但实现起来略微复杂，尤其是最后基准值的交换位置需要想清楚。
• 挖坑法：逻辑最形象，最容易理解和手写，是初学者掌握快排的首选。
• 前后指针法：代码简洁，也是一种非常高效的实现方式，在很多标准库中可以看到它的身影。

在面试或做题时，挖坑法通常是最稳妥、最不容易出错的选择。

2.3.3 快速排序的优化

理论上，快速排序的时间复杂度是 O(N*logN)，性能非常出色。但通过实际测试我们会发现，在某些特定情况下，比如一个已经完全有序或逆序的数组，我们基础版本的快速排序可能会“退化”，甚至抛出 StackOverflowError 栈溢出异常。

这是因为，如果每次选取的基准值（pivot）都恰好是当前区间的最大或最小值，那么分区操作就会变得极不均衡，一边是 0 个元素，另一边是 n-1 个元素。这会导致递归树变成一条长长的链，递归深度接近 N，当 N 非常大时，就会耗尽调用栈空间。

为了解决这些问题，我们可以从以下几个方面对快速排序进行优化：

2.3.3.1 优化一：三数取中法选择基准值

一个好的基准值，应该能尽可能地将数组分成规模相当的两个部分。最理想的基准值是数组的中位数，但找中位数本身代价太高。

一个简单又高效的替代方案是“三数取中法”：从区间的 left, mid, right 三个位置中，选择大小居中的那个数作为基准值。这样可以极大地避免选到极端值，让分区更均衡。

    // 三数取中法private static int getMedian(int[] array, int left, int right) {int mid = left + (right - left) / 2; // 避免整数溢出// 通过一系列比较，最终让 array[mid] 成为三数中的中值if (array[left] > array[right]) {swap(array, left, right);}if (array[mid] > array[right]) {swap(array, mid, right);}if (array[mid] > array[left]) {swap(array, mid, left);}// 此时，array[left] 就是三数中的中值return left;}

在 partition 方法的一开始，调用 getMedian 并将返回的索引与 left 交换，就可以确保我们总是用一个相对“靠谱”的基准值来进行分区。

2.3.3.2 优化二：小区间改用插入排序

递归是有开销的。当快速排序的递归深入到很小的子区间时，再继续递归就有点“杀鸡用牛刀”了。由于插入排序在处理小规模、近乎有序的数据时效率很高，我们可以在递归到一定深度（例如，当区间长度小于某个阈值，如 16）时，停止递归，转而使用插入排序来处理这些小区间。

    // 对小区间使用插入排序private static void insertSortRange(int[] array, int left, int right) {for (int i = left + 1; i <= right; i++) {int tmp = array[i];int j = i - 1;for (; j >= left && array[j] > tmp; j--) {array[j + 1] = array[j];}array[j + 1] = tmp;}}// 在快速排序主框架中加入判断void quickSort(int[] array, int left, int right) {if (left >= right) return;// 当区间长度小于阈值时，使用插入排序if (right - left + 1 <= 16) {insertSortRange(array, left, right);return;}// ... 后续分区和递归逻辑}

2.3.3.3 优化三：非递归实现

为了从根本上避免栈溢出的风险，我们可以将快速排序从递归形式改写为非递归形式。这通常需要借助一个栈（或队列）来手动模拟递归调用的过程。

    // 快速排序的非递归实现public static void quickSortNonRecursive(int[] array) {if (array == null || array.length <= 1) {return;}Deque<Integer> stack = new ArrayDeque<>();stack.push(array.length - 1);stack.push(0);while (!stack.isEmpty()) {int left = stack.pop();int right = stack.pop();if (left >= right) {continue;}int pivotIndex = partition(array, left, right);// 先压入右半部分，再压入左半部分stack.push(right);stack.push(pivotIndex + 1);stack.push(pivotIndex - 1);stack.push(left);}}

2.4 归并排序 (Merge Sort)

归并排序（Merge Sort）是另一个基于分治法的、非常高效的排序算法。它稳定、可靠，无论输入数据是什么样，都能保证 O(N*logN) 的时间复杂度。

2.4.1 基本思想

它的核心思想可以概括为“先拆分，后合并”：

1. 分解 (Divide)：不断地将一个大数组一分为二，直到每个子数组都只包含一个元素。显然，只含一个元素的数组本身就是有序的。
2. 合并 (Conquer)：然后，再将这些有序的子数组两两合并，形成一个更大的有序数组。这个合并的过程是关键，它能保证两个有序的子数组在合并后，新的大数组依然是有序的。
3. 重复这个合并过程，直到所有子数组最终合并成一个完整的、有序的大数组。

参考代码：

    /*** 归并排序 (递归实现)* 时间复杂度：O(N*logN)* 空间复杂度：O(N)* 稳定性：稳定的* @param array 待排序数组*/public static void mergeSort(int[] array) {mergeSortRecursive(array, 0, array.length - 1);}private static void mergeSortRecursive(int[] array, int left, int right) {if (left >= right) {return;}int mid = left + (right - left) / 2;// 递归排序左半部分mergeSortRecursive(array, left, mid);// 递归排序右半部分mergeSortRecursive(array, mid + 1, right);// 将两个有序的子数组合并merge(array, left, mid, right);}// 合并两个有序子数组的核心方法private static void merge(int[] array, 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 (array[i] <= array[j]) { // 使用 <= 保证稳定性temp[k++] = array[i++];} else {temp[k++] = array[j++];}}// 将剩余的元素（如果有一边先走完）复制到临时数组while (i <= mid) {temp[k++] = array[i++];}while (j <= right) {temp[k++] = array[j++];}// 将排好序的临时数组内容复制回原数组的相应位置for (int l = 0; l < temp.length; l++) {array[left + l] = temp[l];}}

非递归实现：

归并排序也可以用非递归（迭代）的方式实现，思路是从底向上进行合并。

• 首先，将数组看作是 N 个长度为 1 的有序子数组。
• 然后，两两合并，得到 N/2 个长度为 2 的有序子数组。
• 接着，再两两合并，得到 N/4 个长度为 4 的有序子数组。
• …如此循环，gap（每次合并的子数组长度）从 1, 2, 4, … 翻倍增长，直到 gap 大于等于数组长度。

    /*** 归并排序 (非递归实现)*/public static void mergeSortNonRecursive(int[] array) {int n = array.length;for (int gap = 1; gap < n; gap *= 2) {for (int i = 0; i < n; i += 2 * gap) {int left = i;int mid = Math.min(i + gap - 1, n - 1);int right = Math.min(i + 2 * gap - 1, n - 1);merge(array, left, mid, right);}}}

2.4.2 归并排序总结

1. 缺点：归并排序最大的缺点是需要 O(N) 的额外空间复杂度，这在内存受限的场景下是个问题。
2. 优点：它的思考方式，尤其适合解决在磁盘上进行的“外部排序”问题。
3. 时间复杂度：O(N*logN)，非常稳定。
4. 空间复杂度：O(N)。
5. 稳定性：稳定。

2.4.3 海量数据的排序问题（外部排序）

当我们需要处理的数据量远超内存容量时，比如有 100G 的数据文件，但内存只有 1G，这时就必须借助外部存储（如磁盘）来进行排序，这就是外部排序。

归并排序的思想是解决这类问题的天然利器。

1. 分割：首先，将 100G 的大文件分割成 200 个 512M 的小文件。
2. 内部排序：然后，依次将每个 512M 的小文件读入内存，使用任意一种内部排序算法（比如快速排序）对其进行排序，并将排好序的结果写回磁盘，生成 200 个有序的临时文件。
3. 多路归并：最后，对这 200 个有序的临时文件进行一次“多路归并”。每次从每个文件中读取一小部分数据到内存中的输入缓冲区，然后在这 200 个元素中找到最小的，写入到最终的输出文件中。重复这个过程，直到所有文件都被合并完毕。

通过这种方式，我们就能在有限的内存下，完成对海量数据的排序。

3. 排序算法性能大比拼

下面这个表格清晰地展示了各种排序算法在不同情况下的性能表现和特点。

排序方法	最好情况	平均情况	最坏情况	空间复杂度	稳定性
插入排序	O(N)	O(N²)	O(N²)	O(1)	稳定
希尔排序	O(N)	O(N^1.3)	O(N²)	O(1)	不稳定
选择排序	O(N²)	O(N²)	O(N²)	O(1)	不稳定
堆排序	O(N*logN)	O(N*logN)	O(N*logN)	O(1)	不稳定
冒泡排序	O(N)	O(N²)	O(N²)	O(1)	稳定
快速排序	O(N*logN)	O(N*logN)	O(N²)	O(logN)	不稳定
归并排序	O(N*logN)	O(N*logN)	O(N*logN)	O(N)	稳定

几个记忆小技巧：

• 稳定性：在常见的排序算法中，只有插入排序、冒泡排序、归并排序是稳定的。可以记作“插冒归（插帽龟）”是稳定的。
• 最快：在平均情况下，快速排序通常被认为是“最快”的，这也是它名字的由来。
• 空间：归并排序是典型的“空间换时间”代表，需要 O(N) 的额外空间。而快速排序的递归实现需要 O(logN) 的栈空间。

4. 非比较排序：另一种思路

我们前面讨论的所有排序算法，都基于一个共同的前提：通过比较元素的大小来决定它们的顺序。但还有一类排序算法，它们另辟蹊径，不通过比较，也能完成排序，我们称之为“非比较排序”。这类算法通常非常快，能达到线性时间复杂度，但它们的使用场景也有限制。

4.1 计数排序 (Counting Sort)

计数排序就是非比较排序中的一个典型代表。它非常适用于对一个确定范围内的整数进行排序。

核心思想：它的核心思路不是比较，而是“计数”。

1. 找出待排序数组中的最大值 max 和最小值 min，以确定需要计数的范围。
2. 创建一个计数数组 count，长度为 max - min + 1。
3. 遍历原数组，将每个元素出现的次数，统计到 count 数组的相应位置上。比如，元素 x 出现了几次，就在 count[x - min] 的位置记上几。
4. 最后，遍历计数数组 count，根据每个元素的计数值，将元素按顺序重新写回原数组。

    /*** 计数排序* 适用场景：数据量大，但数据范围相对集中（例如，对百万考生的百分制成绩进行排序）* 时间复杂度：O(N + range)，其中 range 是数据的范围 (max - min)* 空间复杂度：O(range)* 稳定性：可以实现为稳定的，但当前代码版本是不稳定的* @param array 待排序数组*/public static void countSort(int[] array) {if (array == null || array.length <= 1) {return;}// 1. 找到数据的范围int maxVal = array[0];int minVal = array[0];for (int i = 1; i < array.length; i++) {if (array[i] < minVal) {minVal = array[i];}if (array[i] > maxVal) {maxVal = array[i];}}// 2. 创建计数数组并统计频率int range = maxVal - minVal + 1;int[] count = new int[range];for (int x : array) {count[x - minVal]++;}// 3. 根据计数结果，重写原数组int arrayIndex = 0;for (int i = 0; i < range; i++) {while (count[i] > 0) {array[arrayIndex++] = i + minVal;count[i]--;}}}

4.2 桶排序与基数排序

除了计数排序，桶排序（Bucket Sort）和基数排序（Radix Sort）也是常见的非比较排序算法，它们同样能达到线性的时间复杂度。

• 桶排序：可以看作是计数排序的升级版，它将数据分布到有限数量的“桶”里，然后对每个桶里的数据再单独进行排序。
• 基数排序：一种非常巧妙的排序方式，它将整数按位数切割成不同的数字，然后按每个位数分别比较。

由于篇幅关系，这里就不展开详细介绍了，感兴趣的同学可以查阅相关资料深入了解。

5. 总结

排序是计算机科学中最基础也最核心的问题之一。通过这次学习，我们一起探索了从简单直观的 O(N²) 算法（如冒泡、插入、选择），到更高效的 O(N*logN) 算法（如快排、归并、堆排）的演进过程。

每种排序算法都有其独特的思想和适用场景：

• 插入排序和冒泡排序简单易懂，在数据量小或基本有序时表现不错。
• 希尔排序作为插入排序的改进版，显著提升了性能。
• 选择排序思路直接，但效率较低；而它的高级版堆排序则一跃成为高效排序的代表。
• 快速排序名副其实，是大多数场景下的首选，但需要注意最坏情况下的优化。
• 归并排序稳定可靠，是外部排序和需要稳定性的场景下的不二之选。
• 最后，计数排序等非比较排序算法为我们打开了新世界的大门，展示了在特定条件下超越比较排序极限的可能性。

没有“最好”的算法，只有“最合适”的算法。深刻理解它们的原理、优劣和适用场景，才能在解决实际问题时游刃有余。