十大排序从入门到入赘 agile Posted on Jul 14 2023 排序算法 yukiyama --- title: 十大排序从入门到入赘 tags: - 排序算法 - 算法与数据结构 categories: 算法与数据结构 description: 两万五千字全面介绍如下十种排序算法：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、基数排序、桶排序。 cover: >- https://raw.githubusercontent.com/iyukiyama/pics/master/hexo-iyukiyama/site_img/posts/algorithms/sorting-bg.png katex: true abbrlink: sorting keywords: top_img: comments: --- # 从今天起，与「排序」一刀两断 **感谢官方置顶推荐** 🎉😄。 > - 可在作者的 [github仓库](https://github.com/iyukiyama/leetcode-posts) 中获取本文和其他文章的 markdown 源文件及相关代码。 > > - 欢迎评论或仓库 PR 指出文章错漏或与我讨论相关问题，我将长期维护所有文章。 > - 所有文章均用 Typora 完成写作，可使用 Typora 打开文章 md 文件，以获得最佳阅读体验。 ⚠️ ⚠️ ⚠️ **本文巨长，全文两万五千余字，尝试彻底解析十大排序算法并给出相应实现。** ❗️ **【NEW】** ❗️ - 9-15: [红黑树从入门到看开](https://leetcode.cn/circle/discuss/SwgIJV/) *** > $keywords$ : > > 三种元素交换方法 / 排序稳定性分析 / 排序复杂度分析 / 冒泡排序 / 选择排序 / 插入排序 / 希尔排序 / shell增量 / Hibbard增量 / Knuth增量 / 逆序数 / 归并排序 / 自顶向下 / 自底向上 / 原地与非原地 / 手摇算法 (三重反转) / 快速排序 / 非递归与递归快速排序 / 首位轴 / 三数取中轴 / 随机轴 / 双轴快排 / 堆排序 / 堆化方法 / 下滤方法 / 计数排序 / 稳定版计数排序 / 非稳定版计数排序 / 基数排序 / 基于计数排序的基数排序 / 不基于计数排序的基数排序 / 桶排序 / 决策树 前几天在讨论区上发布的二分查找和并查集文章反馈良好，这让我进一步相信基础知识的总结和分享确实很有一部分受众，于是趁热打铁，~~连夜~~推出本文。我(几乎)可以肯定，你在别处(基本上)看不到比本文更深入更广泛地网罗「十大排序」方方面面的文章，如果有，我就把这句话划掉。 「排序」十分基础，但内容庞杂，网上做全面介绍的资料不可谓不多，但我所看过的材料，总是在这一处或那一处上有所遗憾。比如复杂度缺少证明，比如优化版本未给出，比如缺少便于理解的图示，或者干脆就是到处复制粘贴错误百出的公众号引流文等等等等。**因此上作者试图（企图）在「面试」这一层面上，彻底对排序做一个了断**，使得面试官(几乎)不可能问得比本文内容更深更广（如果你是面试官，我劝你别看，我看你别劝👊😅）。 本文设想的读者应当是初学排序的同学，以及想对「排序」做一点查漏补缺工作的朋友，比如你突然想不起「双轴快排」该如何实现（对你竟然想要徒手实现双轴快排，我起立致敬🫡），或者「计数排序」稳不稳定，又或者「自底向上归并」该怎么写，你都可以在文中找到相应的答案。不过即便你就是纳闷，“不就是「排序」吗，自己随便看看不就好了，有什么好说的，还搞得这么煞有介事”，也十分欢迎你给出一些指导意见。 本文标题意在表达作者的一种希望，即看完本文，读者觉得确实有些帮助，甚或令七尺男儿拍案，以至于 **「想嫁」** 的心都有了，那就算对得起作者案头那把 **键帽斑驳的双飞燕键盘** 了。 发文的本心首要是**向大家学习**，其次是分享(一点微不足道)的心得。仍旧希望大家**不吝赐教**，你所指出的每一个错误，我都会 **立即更正** 。 本文主要内容（特色）如下： - **内容 (应该还算) 全面。** 具体如下。 - 给出 $swap$ 的三种实现。 - 给出十大排序中后面贴出的思维图所列的所有实现。 - 所有代码均经过验证，注释关键语句，力求所见即所得，贴到IDE上就能跑。 - 给出十大排序的所有稳定性和时空复杂度结论和分析证明。 - 在「希尔排序」中讨论了逆序数。 - 在「归并排序」中分析了 自顶向下/自底向上/原地/非原地 各情形排序过程，并给出各自的实现代码。 - 在「归并排序」中讨论了「手摇算法」。 - 在「快速排序」中讨论了三种基于不同轴选择的单轴快排（首位轴/随机轴/三数取中轴）并给出相应实现代码。分析给出了利用栈实现的迭代方式的快排。给出并逐行分析了「双轴快排」的代码。 - 讨论了「计数排序」的稳定性。 - 分别给出了基于计数排序和不基于计数排序的「基数排序」实现。 - 从「决策树」角度分析并证明了基于「比较」的排序时间复杂度下界为$O(nlogn)$。 - 贴出「Stiring公式」的详细证明文章链接。 - **叙述 (应该还算) 准确。** 本文力求言必有据，所有性质，包括各类排序的稳定性，时空复杂度等关键信息，或给出例子，或给出图示，或严格证明，总之尽力拒绝模糊。 - **制作 (应该还算) 精良。** 公式一概以 $\LaTeX$ 编辑。有多处方便记忆的汇总表格。有大量图示，动图静图，有助于理解之处尽附详图。 *** yuki的其他文章如下，欢迎阅读指正！ > 如下所有文章同时也在我的 github [仓库](https://github.com/iyukiyama/leetcode-posts) 中维护。 | 文章 | [发布时间] 字数/览/藏/赞 (~2022-10-20) | | ------------------------------------------------------------ | ---------------------------------------- | | [十大排序从入门到入赘](https://leetcode.cn/circle/discuss/eBo9UB/) 🔥🔥🔥 | [20220516] 2.5万字/64.8k览/3.7k藏/937赞 | | [二分查找从入门到入睡](https://leetcode.cn/circle/discuss/ooxfo8/) 🔥🔥🔥 | [20220509] 2.3万字/38.4k览/2.1k藏/503赞 | | [并查集从入门到出门](https://leetcode.cn/circle/discuss/qmjuMW/) 🔥🔥 | [20220514] 1.2万字/17.9k览/1.0k藏/321赞 | | [图论算法从入门到放下](https://leetcode.cn/circle/discuss/FyPTTM/) 🔥🔥 | [20220617] 5.6万字/19.9k览/1.3k藏/365赞 | | 树ADT系列 (预计13篇) | 系列文章，连载中 | | 3. [二叉查找树](https://leetcode.cn/circle/discuss/wPzlSb/) | [20220801] 5千字 | | 4. [AVL树](https://leetcode.cn/circle/discuss/zbwD3p/) | [20220817] 5千字 | | 5. [splay树](https://leetcode.cn/circle/discuss/BCK17f/) | [20220817] 5千字 | | 6. [红黑树从入门到看开](https://leetcode.cn/circle/discuss/SwgIJV/) 🔥🤯🤯🤯 | [20220915] 3万字/5.3k览/269藏/72赞 | | 10. [树状数组从入门到下车](https://leetcode.cn/circle/discuss/qGREiN/) 🔥🤯 | [20220722] 1.4万字/5.8k览/196藏/72赞 | | 11. [线段树从入门到急停](https://leetcode.cn/circle/discuss/H4aMOn/) 🔥🤯 | [20220726] 2.5万字/8.7k览/481藏/138赞 | | [图论相关证明系列](https://leetcode.cn/circle/discuss/GV0JrV/) | 系列文章 | | 1. [Dijkstra正确性证明](https://leetcode.cn/circle/discuss/jJQn7V/) 🤯 | [20220531] | | 2. [Prim正确性证明](https://leetcode.cn/circle/discuss/VVEc8f/) 🤯 | [20220919] | | 3. [Bellman-Ford及SPFA正确性证明](https://leetcode.cn/circle/discuss/xeEwYl/) | [20220602] | | 4. [Floyd正确性证明](https://leetcode.cn/circle/discuss/Nbzix4/) | [20220602] | | 5. [最大流最小割定理证明](https://leetcode.cn/circle/discuss/tMIy36/) 🤯🤯 | [20220719] | | 6. [Edmonds-Karp复杂度证明](https://leetcode.cn/circle/discuss/tN3sZc/) 🤯🤯 | [20220515] | | 7. [Dinic复杂度证明](https://leetcode.cn/circle/discuss/T9Xa1R/) 🤯🤯 | [20220531] | *** [2022-11-22] - 更换了「冒泡排序」中「冒泡界排序」的实现 (换了一种更容易理解的写法)。 - 全文有多处调整。 [2022-10-19] - 根据 [@strange-antonellipd4](/u/strange-antonellipd4/) (God Man) 的建议，新增了基于 Sedgewick 增量的希尔排序实现。 *** ## 十大排序分类  <!--  --> <br /> ## 复杂度和稳定性一览 **稳定性：** 所谓排序的稳定性，指的是对于存在相等元素的序列，排序后，原相等元素在排序结果中的 **相对位置相比原输入序列不变** 。例如 $nums=\{3,1,2_1,2_2\}$ ，数字 $2$ 出现了两次，下标表示他们出现的次序，若排序方法将 $nums$ 排成了 $\{1,2_2,2_1,3\}$ ，虽然排序结果正确，但改变了两个 $2$ 的相对位置。只有排序为 $\{1,2_1,2_2,3\}$ 我们才说该排序是稳定的。 如果排序对象只是数值，那么是否稳定没有区别。但若是对引用类型进行排序，排序依据是该类型中的某个可比较的数值字段，那么我们可能会希望该字段相同，但其他字段不同的元素相对位置相比原输入保持不变，这时候就需要稳定排序。 | 排序算法 | 平均时间 | 最好时间 | 最坏时间 | 空间 | 稳定性\* | | -------- | --------------------------------- | ----------------------------- | ----------------------------- | ---------- | -------- | | 冒泡 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 | | 选择 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 | | 插入 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 | | 希尔 | $O(nlogn)$ ~ $O(n^2)$ | $O(nlogn)$ | $O(n^2)$ | $O(1)$ | 不稳定 | | 希尔 | $O(nlog_3n)$ ~ $O(n^\frac{3}{2})$ | $O(nlog_3n)$ | $O(n^\frac{3}{2})$ | $O(1)$ | 不稳定 | | 归并 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ | 稳定 | | 快速 | $O(nlogn)$ | $O(nlogn)$ | $O(n^2)$ | $O(logn)$ | 不稳定 | | 堆 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(1)$ | 不稳定 | | 计数 | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | 稳定 | | 基数 | $O(d(n + k))$<br />$k$ 为常数 | $O(d(n + k))$<br />$k$ 为常数 | $O(d(n + k))$<br />$k$ 为常数 | $O(n + k)$ | 稳定 | | 桶 | $O(n)$ | $O(n)$ | $O(n^2)$ or $O(nlogn)$ | $O(n)$ | 稳定 | ``` 下列说明在正文相应章节均有更详细的描述。 ※1冒泡: 输入数组已排序时最好。 ※2选择: 时间复杂度与输入数组特点无关。 ※3插入: 输入数组已排序时最好。 ※4希尔: 复杂度取决于增量序列，两行分别为希尔增量， 和Knuth增量的希尔排序。输入数组已排序时最好。 ※5归并: 所列复杂度为「自顶向下非原地」版本。 自顶向下/自底向上，非原地/原地的时间空间复杂度见该归并排序一节。 ※6快速: 当输入数组有序，且总是选取第一个元素为主轴时， 时间复杂度退化为O(n^2)。空间开销为递归深度。 ※7堆: 原地堆排序空间复杂度为O(1)。输入数组所有数字相等时， 时间复杂度为O(n)。 ※8计数: k是计数数组大小。应用稳定性优化则稳定，否则不稳定。 朴素版本空间复杂度为O(k)，稳定性优化版本空间复杂度为O(n + k)。 ※9基数: d是最大数位数，k是计数数组大小，处理负数时k=19。 ※10桶: 稳定性取决于桶内排序是否稳定。空间取决于桶使用数组还是容器， 若采用数组为O(kn)，容器则为O(n)。所有元素放入同一个桶时复杂度最大。 最坏时间复杂度取决于采用哪种桶内排序算法。 稳定性: 存在稳定和非稳定版本时，视作「稳定」。 ``` <br /> ## 三种交换方法 对于冒泡、选择、插入等采用比较和交换元素的排序方法，由于经常执行交换操作，通常将交换动作写为 $swap$ 方法，需要交换时调用。最常见 $swap$ 写法有如下三种： 1. 方法一: 利用一个临时数 $tmp$ 来交换 $arr[i]$ ，$arr[j]$ 。 2. 方法二: 利用 $arr[i]$ 和和 $arr[j]$ 的加减运算避免临时数 $tmp$ 的开销，但由于涉及到加减法可能导致数字 **「提前溢出」** 。 3. 方法三: 利用位运算中的 **异或** 运算，能够避免 $tmp$ 的开销且不会导致数字溢出。 需要特别注意的是， **「方法二」和「方法三」要避免 $i = j$ ，若 $i = j$ ，执行 $swap$ 后将导致该数字变为 0**。实际上自我交换总是不必要的，因此应当保证 $swap$ 被调用时 $i != j$，这样就无需 $if$ 语句了。 ```java // 方法一: 利用临时数tmp private void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // 方法二: 利用加减运算 private void swapCal(int[] arr, int i, int j) { if(i == j) return; // 若无法保证swapCal被调用时满足 i != j，则需有此句，否则i == j时此数将变为0 arr[i] = arr[i] + arr[j]; // a = a + b arr[j] = arr[i] - arr[j]; // b = a - b arr[i] = arr[i] - arr[j]; // a = a - b } // 方法三: 利用异或运算 private void swapXOR(int[] arr, int i, int j) { if(i == j) return; // 若无法保证swapXOR被调用时满足 i != j，则需有此句，否则i == j时此数将变为0 arr[i] = arr[i] ^ arr[j]; // a = a ^ b，也可写成 arr[i] ^= arr[j]; arr[j] = arr[i] ^ arr[j]; // b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a， 也可写成 arr[j] ^= arr[i]; arr[i] = arr[i] ^ arr[j]; // a = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b， 也可写成 arr[i] ^= arr[j]; } ``` <br /> ## 冒泡排序 ### 算法描述 对于要排序的数组，从第一位开始从前往后比较相邻两个数字，若前者大，则交换两数字位置，然后比较位向右移动一位。也就是比较 $arr[0]$ 和 $arr[1]$ ，若 $arr[0] > arr[1]$ ，交换 $arr[0]$ 和 $arr[1]$ 。接着比较位移动一位，比较 $arr[1]$ 和 $arr[2]$ ，直到比较到 $arr[n - 2]和$ $arr[n - 1] (n = arr.length)$ 。第1轮从前到后的比较将使得最大的数字 **冒泡** 到最后，此时可以说一个数字已经被排序。每一轮的比较将使得当前未排序数字中的最大者被排序，未排序数字总数减 1。第 $arr.length - 1$ 轮结束后排序完成。 如下[动图](https://tva1.sinaimg.cn/large/008i3skNgy1gze7lbis8sg309k059jxz.gif)展示了 $\{4,6,2,1,7,9,5,8,3\}$ 的冒泡排序过程（未应用优化）。  <!--  --> **稳定性：稳定。** 冒泡排序始终只交换相邻元素，比较对象大小相等时不交换，相对位置不变，故稳定。 <br /> ### 优化 **提前结束优化** 当某一轮比较均未发生交换，说明排序已完成，可设置一个布尔值记录一轮排序是否有发生交换，若无则提前退出循环结束程序。 **冒泡界优化** 记录前一轮交换的最终位置，该位置之后的元素为已排序状态，下一轮的交换只需执行到该处。容易看出此优化包含了提前结束优化。见「代码」-「冒泡界优化」。 <br /> ### 复杂度分析 时间复杂度：两层 $for$ 循环，第 1 轮比较 $n - 1$ 次 $(n = arr.length)$ ，最后一轮比较 1 次。总比较次数为 $n*(n - 1) / 2$ 次，时间复杂度为 $O(n^2)$。当输入数组为已排序状态时，在应用提前结束优化的情况下，只需一轮比较，此时为最佳时间复杂度 $O(n)$。 空间复杂度：算法中只有常数项变量，$O(1)$。 <br /> ### 代码 无优化的基本冒泡排序代码此处不列出。 <br /> #### 提前结束优化 ```java public int[] bubbleSort(int[] arr) { if (arr.length < 2) return arr; // n - 1轮次执行，当前 n - 1 个元素排好后，最后一个元素无需执行，故i < arr.length - 1 for (int i = 0; i < arr.length - 1; i++) { // 本轮执行是否有交换的标志，若无则false，若有则true boolean swapped = false; // 每轮循环，通过依次向右比较两个数，将本轮循环中最大的数放到最右 for (int j = 1; j < arr.length - i; j++) { // 若左大于右则交换，并将swapped置为true if (arr[j - 1] > arr[j]) { swap(arr, j - 1, j); swapped = true; } } // 若无交换，表示当前数组已完全排序，退出大循环 if (!swapped) break; } return arr; } ``` <br /> #### 冒泡界优化 ```java public int[] bubbleSort(int[] arr){ if(arr.length < 2) return arr; // 上一轮最后交换的下标，即发生 swap(num, i, j) 时的 i int lastSwappedIdx = arr.length - 1; // 若上一轮最后交换的下标 > 0 ，继续 while(lastSwappedIdx > 0){ // 当前轮次发生交换的下标 int curSwappedIdx = 0; // 每一轮 i 只需要考察到 lastSwappedIdx 前一位 for(int i = 0; i < lastSwappedIdx; i++){ if(arr[i] > arr[i + 1]){ swap(arr, i, i + 1); curSwappedIdx = i; // 更新 curSwappedIdx } } // 若当前轮次未发生交换，则 lastSwappedIdx = 0 ，则在下一次 while 判断时退出，完成排序 lastSwappedIdx = curSwappedIdx; } return arr; } ``` <br /> ## 选择排序 ### 算法描述 对于要排序的数组，设置一个 $minIdx$ 记录最小数字下标。先假设第 1 个数字最小，此时 `minIdx = 0` ，将 $arr[minIdx]$ 与后续数字逐一比较，当遇到更小的数字时，使 $minIdx$ 等于该数字下标，第1轮比较将找出此时数组中最小的数字。找到后将 $minIdx$ 下标的数字与第 1 个数字交换，此时称一个数字已被排序。然后开始第2轮比较，令 `minIdx = 1`，重复上述过程。每一轮的比较将使得当前未排序数字中的最小者被排序，未排序数字总数减 1。第 $arr.length - 1$ 轮结束后排序完成。 如下[动图](https://tva1.sinaimg.cn/large/008i3skNgy1gze7srslbag309k059125.gif)展示了 $\{4,6,2,1,7,9,5,8,3\}$ 的选择排序过程（单元选择）。  <!--  --> 微优化：在交换前判断 $minIdx$ 是否有变化，若无变化则无需交换。当数组大致有序时，能够减少无效交换带来的开销。 **稳定性：不稳定。** 存在跨越交换。找到本轮次最小值之后，将其与本轮起始数字交换，此时若中间有与起始元素同值的元素，将打破稳定性。 例: 7 7 2 。第一轮交换第一个 7 和 2，则两个 7 位置关系改变。 <br /> ### 双元选择优化 在遍历寻找最小值下标 $minIdx$ 时，可以同时寻找最大值下标 $maxIdx$ ，这样就可以一轮遍历确定两个元素的位置，遍历次数减少一半，但每轮次的操作变多，因此该优化 **只能少量提升选择排序的速度** (复杂度介于单元选择排序复杂度及其一半之间，只有系数上的区别)。 <br /> ### 复杂度分析 时间复杂度：两层 $for$ 循环，第1轮比较 $n - 1$ 次 ( `n = arr.length` ) ，最后一轮比较 1 次。总比较次数为 $n*(n - 1) / 2$ 次，时间复杂度为 $O(n^2)$。 双元选择优化版本也是 $O(n^2)$。 冒泡排序和选择排序的比较次数均为 $O(n^2)$，但选择排序的交换次数是 $O(n)$，而冒泡排序的平均交换次数仍然是二次的。 空间复杂度：算法中只有常数项变量，$O(1)$。 <br /> ### 代码 #### 单元选择排序 ```java public int[] selectionSort(int[] arr) { if (arr.length < 2) return arr; for (int i = 0; i < arr.length - 1; i++) { // 当前 N-1 个元素排好后，最后一个元素无需执行，故 i < arr.length - 1 int minIdx = i; for (int j = i + 1; j < arr.length; j++) { // 找到本轮执行中最小的元素，将最小值下标赋值给 minIdx if (arr[j] < arr[minIdx]) minIdx = j; } swap(arr, i, minIdx); } return arr; } ``` <br /> #### 双元选择排序 ```java public int[] selectionSortDouble(int[] arr) { if (arr.length < 2) return arr; int n = arr.length; for (int i = 0; i < n - 1 - i; i++) { // 每轮确定两个数字，因此上界也会动态变化 int minIdx = i, maxIdx = i; for (int j = i + 1; j < n - i; j++) { if (arr[j] < arr[minIdx]) minIdx = j; if(arr[j] > arr[maxIdx]) maxIdx = j; } if(minIdx == maxIdx) break; // 若本轮最大值等于最小值，说明未排序部分所有元素相等，无需再排序 swap(arr, i, minIdx); if(maxIdx == i) maxIdx = minIdx; // 在交换 i 和 minIdx 时，有可能出现 i 即 maxIdx 的情况，此时需要修改 maxIdx 为 minIdx swap(arr, n - 1 - i, maxIdx); } return arr; } ``` <br /> ## 插入排序 ### 算法描述 对于待排序数组，从第 2 个元素开始 (称作插入对象元素) ，比较它与之前的元素 (称作比较对象元素) ，当插入对象元素小于比较对象元素时，继续往前比较，直到不小于 (`≥`) 比较对象，此时将插入对象元素插入到该次比较对象元素之后。重复这个插入过程直到最后一个元素作为插入对象元素完成插入操作。 如下 [动图](https://tva1.sinaimg.cn/large/008i3skNgy1gze7ygeszkg309k0amai1.gif) 展示了 $\{4,6,2,1,7,9,5,8,3\}$ 的简单插入排序过程。  <!--  --> **稳定性：简单插入和折半插入 (二分插入) 排序是稳定的。** 对于大小相同的两个数字，简单插入和折半插入均使得后来的数字靠右放置 （因为条件是 `≥` ），因此不会改变其相对位置。 <br /> ### 折半插入优化 注意到插入排序的每一轮向前插入都使得该元素在完成插入后，**从第一个元素到该元素是排序状态**（指这部分的相对排序状态，在它们中间后续可能还会插入其他数字），利用这一点，对一个新的插入对象向前执行折半插入，能够显著减少比较的次数。另一种优化是增量递减插入排序，也叫 **希尔排序** ，将在希尔排序章节中介绍。 折半插入的关键在于找到插入位置，折半过程代码如下。这实际上是二分查找「模版一」中的「小于等于」情形。如果你尚不能熟练且准确地写出如下代码，这说明你对二分查找写法不熟悉，推荐阅读我写的这篇全面解析二分查找的文章: [二分查找从入门到入睡](https://leetcode.cn/circle/discuss/ooxfo8/)。 ```java // 模版一，小于等于情形 private int binarySearch(int[] arr, int l, int r, int target){ while(l <= r){ int c = l + (r - l) / 2; if(arr[c] <= target) l = c + 1; else r = c - 1; } return l; } ``` <br /> ### 复杂度分析 时间复杂度：两层 $for$ 循环，外层总轮次为 $n - 1$ 轮 ( `n = arr.length` ) ，当原数组逆序时，移动次数为 $n*(n - 1) / 2$ 次，最坏时间复杂度为 $O(n^2)$，平均时间复杂度同为 $O(n^2)$。当原数组已基本有序时，接近线性复杂度 $O(n)$。例如原数组已完全排序，则算法只需比较 n - 1 次。 ※ 折半插入总的查找(比较)次数虽为 $O(nlogn)$，但平均移动 (每轮移动一半的数字) 次数仍是 $O(n^2)$。 空间复杂度：算法中只有常数项变量，$O(1)$。 <br /> ### 代码 #### 简单插入排序 ```java // 简单插入排序：内层用 for public int[] insertionSortUseWhile(int[] arr) { if (arr.length < 2) return arr; for (int i = 1; i < arr.length; i++) { int target = arr[i], j = i - 1; for (; j >= 0; j--) { if(target < arr[j]) arr[j + 1] = arr[j]; else break; } arr[j + 1] = target; } return arr; } ``` ```java // 简单插入排序，内层用 while public int[] insertionSort(int[] arr) { if (arr.length < 2) return arr; for (int i = 1; i < arr.length; i++) { // N-1轮次执行 int target = arr[i], j = i - 1; while (j >= 0 && target < arr[j]) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = target; // 若发生移动，此时的插入对象数字≥j位置的数字，故插入位置为j + 1，若未移动也成立，无需判断 } return arr; } ``` <br /> #### 折半插入排序 ```java public int[] insertSortBinary(int[] arr) { if (arr.length < 2) return arr; // n - 1 轮次执行 for (int i = 1; i < arr.length; i++) { // 通过二分查找得到插入位置 int target = arr[i]; int pos = binarySearch(arr, 0, i - 1, target); for (int j = i; j > pos; j--) { // 移动 arr[j] = arr[j - 1]; } arr[pos] = target; // 插入 } return arr; } ``` <br /> ## 希尔排序 ### 算法描述 [希尔排序](https://en.wikipedia.org/wiki/Shellsort) 是 **简单插入排序的改进** ，它基于以下事实。 1. 简单插入排序对 **排序程度较高的序列** 有较高的效率。假设初始序列已完全排序，则每一轮均只需比较一次，将得到 $O(n)$ 的线性复杂度，冒泡排序和选择排序做不到这一点，均仍需 $O(n^2)$ 次比较 (冒泡排序在应用提前结束优化后可以做到) 。 2. 简单插入排序每次比较最多将数字移动一位，效率较低。 Donald Shell 在 1959 年发表的 [论文](http://penguin.ewu.edu/cscd300/Topic/AdvSorting/p30-shell.pdf) 中，针对这两个事实，提出如下方法。对原待排序列中相隔 $gap$ 的数字执行简单插入排序，然后缩小 $gap$，对新的 $gap$ 间隔的数字再次执行简单插入排序。以一种规则减少 $gap$ 的大小，当 $gap$ 为 1 时即简单插入排序，因此希尔排序也称作 **增量递减排序**。希尔在论文中提出的增量序列生成式为 $n / 2^k$，`k = 1, 2, 3, ...` ，例如 `n = 11`，则增量序列为 $\{1,2,5\}$ 。在讨论希尔排序时，可将其称为 **Shell增量**，另有更优的 **Hibbard增量**、**Knuth增量**、**Sedgewick增量** 等。 程序开始时 $gap$ 较大，待排元素较少，因此排序速度较快。当 $gap$ 较小时，基于第一点，此时待排序列已大致有序，排序效率接近线性复杂度。因此能够期待希尔排序复杂度将优于 $O(n^2)$。详细见「复杂度分析」。 **稳定性：不稳定。** `gap > 1` 时，跨越 $gap$ 的插入可能会改变两个相同值元素的位置关系。例如 $\{0, 1, 4, 3_1, 3_2, 5, 6\}$ ，当 `gap = 2` 时，对 $\{0, 4, 3, 6\}$ 简单插入排序后得到 $\{0, 1, 3_2, 3_1, 4, 5, 6\}$ ，原数组中的两个 3 的相对位置发生了变化。 <br /> ### 复杂度分析 时间复杂度：希尔排序的时间复杂度与增量序列的选择有关。**最优复杂度增量序列尚未明确**。 **Shell增量** (Shell, 1959): $n / 2^k$，最坏时间复杂度 $Θ(n^2)$。 **Hibbard增量** (Hibbard, 1963)：$\{1, 3, 7, 15,...\}$ ，即 $2^k - 1,k = 1, 2, 3, ...$ ， 最坏时间复杂度 $Θ(n^\frac{3}{2})$。 **Knuth增量** (Knuth, 1971)：$\{1, 4, 13, 40,...\}$ ，即 $(3^k - 1) / 2，k = 1, 2, 3, ...$ ，最坏时间复杂度 $Θ(n^\frac{3}{2})$。 **Sedgewick增量** (Sedgewick, 1982): $\{1, 8, 23, 77, 281... \}$ ，即 $4^k + 3*2^{k-1} + 1$ (最小增量 1 直接给出)，$k = 1,2,3,...$ ，最坏时间复杂度 $Θ(n^\frac{4}{3})$。 平均 / 最坏复杂度的证明需要借助数论和组合数学，本文不做讨论。 当输入数组已排序时，达到最好时间复杂度。 空间复杂度：算法中只有常数项变量，$O(1)$ 。 <br /> ### **逆序数** 希尔排序是较早出现的 **突破二次复杂度** 的排序算法，下面从 **逆序数** 的角度来直观地证明为何希尔排序能够突破二次复杂度。 以数值从小到大为「顺序」，则在一个排列中，如果任意一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个 **逆序**，一个排列中逆序的总数就称为这个排列的 **逆序数**。排序的过程就是不断减少逆序数 **直到逆序数为 0** 的过程。 回顾冒泡排序和简单插入排序，算法的每一次交换，都只交换相邻元素（简单插入排序中元素每次右移也看作交换），因此每次交换只能减少一个逆序。冒泡排序和简单插入排序的元素平均交换次数均为 $O(n^2)$， 也即逆序数 (或逆序数减少次数) 为 $O(n^2)$。 如果能跨越多个数字进行交换，则可能一次减少多个逆序。在选择排序中，每轮选到最小元素后的交换即是跨越多个元素的，交换次数 (减少逆序数的操作) 为 $O(n)$，要少于冒泡和简单插入排序，只是因为比较次数仍是 $O(n^2)$， 所以整体复杂度为 $O(n^2)$。 现在来分析跨越多个元素的交换如何减少逆序数，假设 $arr[i]>arr[j],i<j$。对于任意的 $arr[k] (i < k < j)$： 1. 若 $arr[k] < arr[j]$ ，交换 $arr[i] 和 $arr[j] 后，三者的逆序数从 2 变为 1。 2. 若 $arr[k] > arr[i]$ ，交换 $arr[i] 和 $arr[j] 后，三者的逆序数从 2 变为 1。 3. 若 $arr[i] > arr[k] > arr[j]$，交换 $arr[i]$ 和 $arr[j]$ 后，三者的逆序数从 3 变为 0 。 $arr[k] = arr[i]$ 或 $arr[k] = arr[j]$ 的情况一样，都使得三者逆序数从 2 变为 1 ，下图省略。  <!--  --> 对 $arr[i]$ 和 $arr[j]$ 的逆序消除，使得逆序 **至少** 减少一次，并 **有机会减少大于一次的逆序** (情况3)，因此能够以比 $n^2$ 低阶的次数消除所有逆序。 实际上归并排序，快速排序，堆排序均实现了 **长距离交换元素**，使得复杂度优于 $O(n^2)$。 <br /> ### 代码 从下列实现可看出，不同增量的代码仅 $gap$ 初始化和增量递减上有差异，此差异反映了各自不同的增量。 <br /> #### Shell增量 ```java // 希尔排序：采用Shell增量 N / 2^k public int[] shellSortShell(int[] arr) { if (arr.length < 2) return arr; int n = arr.length; for (int gap = n / 2; gap > 0; gap /= 2) { // gap 初始为 n/2，缩小gap直到1 for(int start = 0; start < gap; start++) { // 步长增量是gap，当前增量下需要对gap组序列进行简单插入排序 for (int i = start + gap; i < n; i += gap) { // 此for及下一个for对当前增量序列执行简单插入排序 int target = arr[i], j = i - gap; for (; j >= 0; j -= gap) { if (target < arr[j]) arr[j + gap] = arr[j]; else break; } arr[j + gap] = target; } } } return arr; } ``` ~~**尤其需要注意的是**，网上有大量**错误的「Shell增量」希尔排序写法**写成如下形式，gap直接从 n / 2开始，虽然gap减小到1时变成简单插入排序，可以得到正确结果，但增量序列并不一定满足「Shell增量」的定义，实际上只有当n为2的整数次幂时才满足。~~ 删除内容为作者早先的错误认识，实际上 $Shell$ 增量并未要求增量序列必须为 $\{1,2,4,8,16,...\}$ ，而是无论 $n$ 等于多少，都直接从 $n / 2$ 开始，不断除 2 直到 `gap = 1`。详情可参考 Donald Shell 原论文 [A High-Speed Sorting Procedure](https://dl.acm.org/doi/pdf/10.1145/368370.368387)。原论文 TABLE 1 给出了长度为 11 的序列 $\{3, 11, 6, 4, 9, 5, 7,8,10, 2, 1\}$，首个 $gap$ 为 `gap = 11 / 2 = 5`，接着是 `gap = 2` ，`gap = 1`。 <br /> #### Hibbard增量 ```java // 希尔排序： 采用Hibbard增量 {1, 3, 7, 15,...} public int[] shellSortHibbard(int[] arr) { if (arr.length < 2) return arr; int n = arr.length, gap = 1; while (gap < n / 2) gap = gap * 2 + 1; // 初始化gap (Hibbard增量序列) for (; gap > 0; gap /= 2) { // 缩小gap直到1 for(int start = 0; start < gap; start++) { // 步长增量是gap，当前增量下需要对gap组序列进行简单插入排序 for (int i = start + gap; i < arr.length; i += gap) { // 此for及下一个for对当前增量序列执行简单插入排序 int target = arr[i], j = i - gap; for (; j >= 0; j -= gap) { if (target < arr[j]) arr[j + gap] = arr[j]; else break; } arr[j + gap] = target; } } } return arr; } ``` <br /> #### Knuth增量 ```java // 希尔排序： 采用Knuth增量 {1, 4, 13, 40,...} public int[] shellSortKnuth(int[] arr) { if (arr.length < 2) return arr; int n = arr.length, gap = 1; while (gap < n / 3) gap = gap * 3 + 1; // 初始化gap (Knuth增量序列) for (; gap > 0; gap /= 3) { // 缩小gap直到1 for(int start = 0; start < gap; start++) { // 步长增量是gap，当前增量下需要对gap组序列进行简单插入排序 for (int i = start + gap; i < arr.length; i += gap) { // 此for及下一个for对当前增量序列执行简单插入排序 int target = arr[i], j = i - gap; for (; j >= 0; j -= gap) { if (target < arr[j]) arr[j + gap] = arr[j]; else break; } arr[j + gap] = target; } } } return arr; } ``` <br /> #### Sedgewick增量 ```java public int[] shellSortSedgewick(int[] arr) { if (arr.length < 2) return arr; int n = arr.length, gap = 1; List<Integer> gaps = new ArrayList<>(); gaps.add(gap); for(int k = 1; gap < n; k++){ // 计算增量序列 gap = (int) (Math.pow(4, k) + 3 * Math.pow(2, k - 1) + 1); gaps.add(gap); } for (int idx = gaps.size() - 1; idx >= 0; --idx) { // 缩小 gap 直到 1 gap = gaps.get(idx); for(int start = 0; start < gap; start++) { // 步长增量是 gap ，当前增量下需要对 gap 组序列进行简单插入排序 for (int i = start + gap; i < n; i += gap) { // 此 for 及下一个 for 对当前增量序列执行简单插入排序 int target = arr[i], j = i - gap; for (; j >= 0; j -= gap) { if (target < arr[j]) arr[j + gap] = arr[j]; else break; } arr[j + gap] = target; } } } return arr; } ``` <br /> ## 归并排序 ### 算法描述 归并排序是 **分治思想** 的应用，即将原待排数组 **递归或迭代** 地分为左右两半，直到数组长度为 1，然后合并 ($merge$) 左右数组，在合并中完成排序。详细过程需结合代码理解，如下 [动图](https://tva1.sinaimg.cn/large/008i3skNgy1gymsfclus3g309w0aq1b4.gif) 展示了 $\{4,6,2,1,7,9,5,8,3\}$ 的归并排序过程（自顶向下非原地）。合并过程采用 **非原地** 合并方法，即依次比较两部分已排序数组，将比较结果依次写入 **新空间** 中。后续会介绍一种称作 **原地(in-place)** 归并排序的改进，使得空间复杂度达到 **常数级** (自底向上时，$O(1)$)。  <!--  --> 如下树状图中的橙色线表示递归的轨迹（自顶向下递归归并排序）。  <!--  --> **稳定性：稳定。** 合并时的此判断中的等号 `if(left[l_next] <= right[r_next])`，保证了出现相等元素时，居左的元素总会被放在左侧，即排序是稳定的。 <br /> ### 自顶向下和自底向上 可以通过 **自顶向下 (top-down)** 或 **自底向上 (bottom-up)** 的方式实现归并排序。 自顶向下 (top-down)：从输入数组出发，不断二分该数组，直到数组长度为1，再执行合并。适合用 **递归** 实现。 自底向上 (bottom-up)：从输入数组的单个元素出发，一一合并，二二合并，四四合并直到数组有序。适合用 **迭代** 实现。 后续给出 **自顶向下原地** / **自顶向下非原地** / **自底向上原地** / **自底向上非原地** 四种代码实现。 <br /> ### 原地归并 前述归并排序，每一次合并都是将两部分待合并数组的比较结果写入一个与 $arr$ 等大小的临时数组 $tmpArr$ 中，写入后再将 $tmpArr$ 中的合并结果写回到 $arr$ 中。于是 $tmpArr$ 的空间开销即为该实现的空间复杂度，为 $O(n)$。通过一种 **原地旋转交换** 的方法（俗称手摇算法/内存反转算法/三重反转算法，英文社区一般称为 [block swap algorithm](https://en.wikipedia.org/wiki/Block_swap_algorithms)），则只需要 $O(1)$ 的辅助空间（由于递归空间为 $O(logn)$，其总的空间复杂度仍为 $O(logn)$）。以下介绍旋转交换的实现方法。 以 456123 为例，欲将 456 和 123 交换位置转换为 123456，只需要执行三次旋转即可： 1. 旋转 456，得到 654 2. 旋转 123，得到 321 3. 旋转 654321 得到 123456 应用上述「手摇算法」对两个排序序列的「原地归并」过程如下。 1. 记左数组第一个数下标为 $i$ ，记右数组第一个数下标为 $j$ 。 2. $i$ 向后遍历，找到左数组中第一个 **大于** 右数组第一个数字 (即 $arr[j]$ ) 的数，此时 $arr[i]>arr[j]$ 。 3. 以 $index$ 暂存右数组第一个元素的下标 $index = j$ 。 4. 找到右数组中第一个 **大于等于** $arr[i]$ 的数，记其下标为 $j$ 。此时必有 $[i, index - 1]$ 下标范围序列 **大于** $[index, j - 1]$ 下标范围序列。 5. 通过三次翻转交换 $[i, index-1]$ 和 $[index, j - 1]$ 序列 (指下标范围)，即依次翻转 $[i, index-1]$ ，翻转 $[index, j - 1]$ ，翻转 $[i, j - 1]$ 。 6. 重复上述过程直到不满足 `(i < j && j <= r)` ※ 第4步如果找「大于」而不是「大于等于」，对于数字数组排序，结果正确，但将 **破坏稳定性**。读者可自行验证。 以 $\{1, 2, 4, 6, 7\}$ 与 $\{3, 5, 8, 9\}$ 两个已排序序列的合并为例，观察借助手摇算法实现原地归并的过程。 1. 在 $\{1, 2, 4, 6, 7\}$ 中找到第一个大于 3 的数 4 ，其下标为 2 ，$i = 2$。$index = j = 5$。在 $\{3, 5, 8, 9\}$ 中找到第一个大于 $arr[i] = arr[2] = 4$ 的数 5，其下标为 6，$j = 6$ 。 2. 如上操作使得 $[0, i - 1]$ 必是最小序列，$[index, j - 1]$ 必小于 $arr[i]$ 。因此交换 $[i, index - 1]$ 和 $[index, j - 1]$（采用三次旋转完成交换），使得这部分序列在整个数组中有序。 3. 交换后，继续执行上述过程，直到不满足该条件 ：`i < j && j <= r`。  <!--  --> <br /> ### 复杂度分析 #### 自顶向下非原地 **时间复杂度** 每次减半后的左右两半对应元素的对比和赋值 ( `tmpArr[h++] = arr[lh] <= arr[rh] ? arr[lh++] : arr[rh++];` ) 总是必须的，也即在每一层递归中 (这里的一层指的是 **递归树** 中的层) ，比较和赋值的时间复杂度都是 $O(n)$，数组规模减半次数为 $logn$，即递归深度为 $logn$，也即总共需要 $logn$ 次 $O(n)$ 的比较和赋值，时间复杂度为 $O(nlogn)$。 也可以这样求解。当 $n = 1$ 时，排序只需常数时间，可以记为 $O(1)$。$n$ 个元素的归并排序时间由 $n/2$ 个元素的归并排序的两倍，再加上将两个 $n/2$ 大小的已排序数比较及合并的耗时得到。得到如下两个式子 (第2个式子加号右边的 $n$ 表示比较及合并的时间)。 $$ \begin{aligned} T(1)&=O(1) \\ T(n)&=2 T(n / 2)+O(n) \end{aligned} $$ 对第二个式子，左右两边除以 $n$ ，得到 $$ \frac{T(n)}{n}=\frac{T(n / 2)}{n / 2}+O(1) $$ 可以不断地将括号内的 $n$ 除以 2 (假设 $n$ 为 2 的整数次幂)，从 $T(n) / n$ 写到 $T(1)$ ，得到 $$ \begin{aligned} \frac{T(n)}{n} &=\frac{T(n / 2)}{n / 2}+O(1) \\ \frac{T(n / 2)}{n / 2} &=\frac{T(n / 4)}{n / 4}+O(1) \\ \frac{T(n / 4)}{n / 4} &=\frac{T(n / 8)}{n / 8}+O(1) \\ & \cdots \\ \frac{T(2)}{2} &=\frac{T(1)}{1}+O(1) \end{aligned} $$ 将上述所有式子相加后得到如下，故复杂度为 $O(nlogn)$。 $$ \begin{gathered} \frac{T(n)}{n}=\frac{T(1)}{1}+logn*O(1) \\ T(n)=O(n)+O(nlogn) \end{gathered} $$ **空间复杂度** 递归深度为 $logn$，递归过程中需要一个长度为 $n$ 的临时数组保存中间结果，空间复杂度为 $O(n)$。 <br /> #### 自顶向下原地 **时间复杂度** 该方式的时间复杂度计算参考了[此篇文章](https://blog.csdn.net/weixin_45502929/article/details/110914032)。 当序列为 **链表** 时，手摇算法只需做如下指针调整即可（只做示意，非实际代码）。 ``` 双向链表时： tmp = index.prev index.prev = i.prev i.prev = j.prev j.prev = tmp 单向链表时： (i-1).next = index (index-1).next = j (j-1).next = i ```  <!--  --> 对于长度为 $n$ 的序列，手摇算法操作元素个数至多不超过 $n/2$ 个 (由较短的一侧决定)，容易得到下述递推式。 $$ T(n)=c \cdot \frac{n}{2}+2 T\left(\frac{n}{2}\right) $$ 由前述计算方法可复杂度为 $O(nlogn)$。 当序列为 **数组** 时，以 $\{1,3,5,7,...k\}$ 和 $\{2,4,6,8,...,n\}$ 的手摇合并为例，对于长度为 $n$ 的序列，一次手摇算法需要翻转大约一半的元素。例如第一次手摇，需翻转 $\{3, ..., k\}$ 和 $\{2\}$ ( $\{2\}$ 只有一个元素，实际不翻转) 得到 $\{k, ..., 3\}$ 和 $\{2\}$ ，然后再翻转 $\{k, ..., 3, 2\}$ 得到 $\{2, 3, ..., k\}$。下一次手摇对象是 $\{5, ..., k\}$ 和 $\{4\}$ ，翻转元素个数相比上一次减少一个，可知完成 $\{1,3,5,7,...k\}$ 和 $\{2,4,6,8,...,n\}$ 的手摇合并所需要的对元素的翻转次数是 $c*n^2$ (等差数列求和，$c$ 是一常数)，于是有下列递推式。 $$ T(n)=c n^{2}+2 T\left(\frac{n}{2}\right) $$ 仍沿用前述方法计算 $$ \begin{gathered} \frac{T(n)}{n}=\frac{T(n / 2)}{n / 2}+c n \\ \frac{T(n / 2)}{n / 2}=\frac{T(n / 4)}{n / 4}+c \frac{n}{2} \\ \frac{T(n / 4)}{n / 4}=\frac{T(n / 8)}{n / 8}+c \frac{n}{4} \\ \cdots \\ \frac{T(2)}{2}=\frac{T(1)}{1}+c \frac{n}{2^{k-1}} \end{gathered} $$ 其中 $k = logn$，由等比数列求和公式得到 $$ \begin{aligned} &\frac{T(n)}{n}=c \frac{n\left(1-\left(\frac{1}{2}\right)^{k}\right)}{1-\frac{1}{2}}+1 \\ &T(n)=2 c n^{2}-2 c n\left(\frac{1}{2}\right)^{k}+n \end{aligned} $$ 故复杂度为 $O(n^2)$。 上述复杂度为 **最坏及平均情形**， **最好情形是输入数组已排序**，则无需手摇，但序列长度为 $n$ 时需要的比较判断次数是 $n$，于是最好情形的递推式如下，复杂度为 $O(nlogn)$。 $$ T(n)=2 T(n / 2)+n $$ **空间复杂度** 递归深度为 $logn$，手摇算法仅需 $O(1)$ 的辅助空间，综合来看空间复杂度为 $O(logn)$。 <br /> #### 自底向上非原地 & 自底向上原地 **时间复杂度** 同自顶向下非原地 / 原地的分析类似，只是程序运行过程从递归变为了迭代。 **空间复杂度** 自底向上非原地归并：迭代过程中需要一个长度为 $n$ 的临时数组保存中间结果，空间复杂度为 $O(n)$。 自底向上原地归并：手摇算法仅需 $O(1)$ 的辅助空间，其他空间开销均为常数级，空间复杂度为 $O(1)$。 <br /> #### 总结 四种归并排序的时空复杂度总结如下（待排序序列是数组形式，不考虑链表形式）。 | 归并排序 | 平均时间 | 最好时间 | 最坏时间 | 空间 | 稳定性 | 备注 | | -------------- | ---------- | ---------- | ---------- | --------- | ------ | ------------------------------------------------------------ | | 自顶向下非原地 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ | 稳定 | 递归深度 $O(logn)$，辅助空间为 $O(n)$ | | 自顶向下原地 | $O(n^2)$ | $O(nlogn)$ | $O(n^2)$ | $O(logn)$ | 稳定 | 空间消耗为递归深度手摇交换仅需 $O(1)$ 空间最好时间在输入数组有序时取得 | | 自底向上非原地 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ | 稳定 | 无递归深度，辅助空间为 $O(n)$ | | 自底向上原地 | $O(n^2)$ | $O(nlogn)$ | $O(n^2)$ | $O(1)$ | 稳定 | 手摇交换仅需 $O(1)$ 空间 | 根据上述分析，原地相比非原地，空间消耗较少，采用 **自底向上原地归并排序** 时空间复杂度为常数级 $O(1$)，但需要 $O(n^2)$ 的时间复杂度。是一种以时间换空间的做法，通常空间不为瓶颈时，应采用 **效率更高的非原地归并排序。** <br /> ### 代码 #### 自顶向下非原地归并 ```java public int[] mergeSort(int[] arr) { if (arr.length < 2) return arr; int[] tmpArr = new int[arr.length]; mergeSort(arr, tmpArr, 0, arr.length - 1); return arr; } // mergeSort 递归方法 private void mergeSort(int[] arr, int[] tmpArr, int l, int r) { if(l < r) { int c = l + (r - l) / 2; mergeSort(arr, tmpArr, l, c); mergeSort(arr, tmpArr, c + 1, r); merge(arr, tmpArr, l, c, r); } } // 非原地合并方法 private void merge(int[] arr, int[] tmpArr, int l, int c, int r) { int lh = l, rh = c + 1, h = l; // lh: left head, rh: right head, h: tmpArr head while (lh <= c && rh <= r) { tmpArr[h++] = arr[lh] <= arr[rh] ? arr[lh++] : arr[rh++]; } while (lh <= c) tmpArr[h++] = arr[lh++]; // 左半边还有剩余，加入 tmpArr 末尾 while (rh <= r) tmpArr[h++] = arr[rh++]; // 右半边还有剩余，加入 tmpArr 末尾 for(; l <= r; l++) arr[l] = tmpArr[l]; // 将 tmpArr 拷回 arr 中 } ``` <br /> #### 自顶向下原地归并 ```java public int[] mergeSort(int[] arr) { if (arr.length < 2) return arr; mergeSort(arr, 0, arr.length - 1); return arr; } // mergeSort 递归方法 private void mergeSort(int[] arr, int l, int r) { if(l < r) { int c = l + (r - l) / 2; mergeSort(arr, l, c); mergeSort(arr, c + 1, r); merge(arr, l, c, r); } } // 原地归并（手摇算法） private void merge(int[] arr, int l, int c, int r) { int i = l, j = c + 1; // #1 while(i < j && j <= r) { while(i < j && arr[i] <= arr[j]) i++; // #2 int index = j; // #3 while(j <= r && arr[j] < arr[i]) j++; // #4 注意是 arr[j] < arr[i]，即找到j使得arr[j] 为第一个大于等于 arr[i]值 exchange(arr, i, index - 1, j - 1); // #5 } } // 三次翻转实现交换 private void exchange(int[] arr, int l, int c, int r) { reverse(arr, l, c); reverse(arr, c + 1, r); reverse(arr, l, r); } // 原地翻转 private void reverse(int[] arr, int l, int r) { while(l < r) { swap(arr, l++, r--); } } ``` <br /> #### 自底向上非原地归并 ```java public int[] mergeSortBU(int[] arr) { if (arr.length < 2) return arr; int n = arr.length; int[] tmpArr = new int[n]; for(int gap = 1; gap < n; gap *= 2) { // 基本分区合并(随着间隔的成倍增长，一一合并，二二合并，四四合并...) for(int l = 0; l < n - gap; l += 2 * gap) { // leftEnd = left+gap-1; rightEnd = left+2*gap-1; int r = Math.min(l + 2 * gap - 1, n - 1); // 防止最后一次合并越界 merge(arr, tmpArr, l, l + gap - 1, r); } } return arr; } ``` | nums | gap = 3时的合并过程 | | -------------------------- | ------------------------------------------------------------ | | 1,3,5,2,4,6,7,9,11 | left = 0, [1,3,5] 与 [2,4,6]合并<br />left = 6 不满足 6 < 9 - 3，最后一个「左段」[7,9,11]无需合并 | | 1,3,5,2,4,6,7,9,11,8,10,12 | left = 0, [1,3,5] 与 [2,4,6]合并<br />left = 6, [7,9,11] 与 [8,10,12]合并<br />left = 12 不满足 12 < 12 - 3 | | 1,3,5,2,4,6,7,9,11,8 | left = 0, [1,3,5] 与 [2,4,6]合并<br />left = 6, [7,9,11] 与 [8]合并<br />left = 12 不满足 12 < 10 - 3 | <br /> #### 自底向上原地归并 ```java // 归并排序四：自底向上原地 public int[] mergeSortBUInPlace(int[] arr) { if (arr.length < 2) return arr; int n = arr.length; for(int gap = 1; gap < n; gap *= 2) { for(int l = 0; l < n - gap; l += 2 * gap) { // 基本分区合并(随着间隔的成倍增长，一一合并，二二合并，四四合并...) int r = Math.min(l + 2 * gap - 1, n - 1); // leftEnd = left+gap-1; rightEnd = left+2*gap-1; merge(arr, l, l + gap - 1, r); } } return arr; } ``` <br /> ## 快速排序 ### 算法描述 与归并排序一样，快速排序也是一种利用 **分治思想** 的排序方法，确定 **主轴及分区** 是快速排序的核心操作。首先在数组中确定一个主轴元素 (例如以第一个元素为主轴元素)，然后遍历数组，将数组分为两部分， **小于** 主轴的元素放在 (最终的) 主轴下标 $p$ 的左侧， **大于等于** 主轴的放在右侧，这个过程由后文介绍的「分区方法 $partition$ 」实现。当前主轴位置确定后，继续递归地对主轴左右两侧数组执行这个过程，每次递归都传入待排序数组 $arr$ 和本次要处理的部分的左右界，只处理这个范围内的序列。当所有递归都到达基准情形时，排序完成。因为是原地交换，递归过程中 $arr$ 总是在动态排序，递归过程无需返回，为尾递归形式。 详细过程请读者结合代码理解，如下 [动图](https://tva1.sinaimg.cn/large/008i3skNly1gynuubbcdpg306q03gdl9.gif) 展示了 $\{4,6,2,1,7,9,5,8,3\}$ 的快速排序过程 (以第一个元素为主轴) 。  <!--  --> <br /> #### 主轴的选取 1. **主轴为起始元素** ( $quickSortSimple$ )。每次选取当前数组第一个元素作为主轴。 - 优点：实现简单。 - 缺点：若输入是较为有序的数组，$pivot$ 总是不能均匀地分割数组。若输入数组本身有序，**复杂度退化到 $O(n^2)$**。 2. **主轴为随机下标元素** ( $quickSortRandom$ )。每次随机选取当前数组的下标，将该下标元素作为主轴。 ```java int randIdx = new Random().nextInt(r - l + 1) + l; // randIdx 为 [left + 1, right] 下标范围内的随机数 swap(arr, l, randIdx); // 交换当前 arr[left] 与 arr[randIdx] ``` - 优点：避免了主轴为起始元素时对于基本有序的输入，因不能均匀分割数组导致复杂度退化的情况。 - 缺点：随机数的选取本身消耗一定的性能。 3. **主轴为左中右三数大小居中者** ( $quickSortMedian3$ )。每次比较当前数组起始、中间和末尾三个元素的大小，选择大小居中者为主轴。 ```java // 三数取中方法 (将 arr[l], arr[c], arr[r] 三者居中者置于下标 l 处) public void median3(int[]arr, int l, int r) { int c = l + (r - l) / 2; if (arr[l] > arr[c]) swap(arr, l, c); // 左中，大者居中 if (arr[c] > arr[r]) swap(arr, c, r); // 中右，大者居右，此时最大者居右 if (arr[c] > arr[l]) swap(arr, l, c); // 左中，大者居左，此时中者居左 } ``` - 优点：实现相对简单，且有效避免简单快排中的 **劣质分割**。 - 缺点：三数取中方法消耗一定性能。 快速排序也可以与其他排序相结合，例如当元素较少时使用简单插入排序能够获得更高的排序效率，实际上这就是 JDK 的做法，这里不展开介绍。 <br /> **分区方法 (partition)** 快速排序中的 **核心方法为 $partition$**。 $partition$方法执行后，**主轴左边元素均小于主轴，主轴右边元素均大等于主轴元素** ，返回主轴下标 $p$ 。 选定一个数作为主轴后 (无论是上述哪种方法选取主轴元素， **都先将选定的主轴置于当前数组的起始位置** )，设置一个 $j (j = l + 1)$ 动态地寻找最终的主轴下标。从左到右将主轴后的所有元素依次与主轴元素比较，若小于主轴则将该数字与下标为 $j$ 的数字交换，$j$ 右移一位，使得 **$j$ 的前一位总是当前最后一个小于主轴的元素**。遍历比较结束后，交换下标为 $l$ 与 $j - 1$ 的数字，并将当前主轴的下标 $j - 1$ 返回。 ```java // partition 方法 private int partition(int[] arr, int l, int r) { int j = l + 1; for (int i = j; i <= r; i++) { if (arr[i] < arr[l]) { swap(arr, i, j); // 交换后的 arr[j] 为当前最后一个小于主轴元素的元素 j++; } } swap(arr, l, j - 1); // 主轴元素归位 return j - 1; } ``` **稳定性：不稳定。** 执行 $partition$ 方法确定了主轴位置后，将一开始设置的主轴元素与最后一个小于主轴的元素 $x$ 交换时，若中间有与 $x$ 同值的元素，则稳定性被破坏。 例：7 2 4 4 8 9 7 为主轴元素，$partition$ 过后交换 7 和第二个 4 ，则两个 4 的位置关系发生变化。 <br /> ### 非递归单轴快排(利用栈迭代) 前述快排以递归形式写出，递归地确定 $[l, r]$ 区间的主轴位置 $p$ 并对新的左区间 $[l, p - 1]$ 和右边区间 $[p + 1, r]$ 区间执行同样的过程。若要求不以递归形式实现快排，容易想到利用 **栈保存区间左右界**，每次 $partition$ 划分确定 $p$ 后将得到的 $p$ 左右两侧的区间的 $l,r$ 界压入栈中。过程如下： 1. 初始时区间左右界是 $0, arr.length -1$ ，将他们压入栈（按 $r, l$ 顺序入栈）。 2. 以 $while$ 询问当前栈是否空，不空则弹出栈顶的一对界（依次为 $l，r$ ）。 3. 若满足 $l < r$ ，则对当前这对 $l,r$ 界的区间执行一次 $partition$ 方法，得到该区间的主轴下标 $p$ 。 4. 若满足 $l < p$ ，则将 $p$ 左侧区间的左右界压入栈（按 $p - 1,l$ 顺序入栈）。并列地，若满足 $r > p$ ，则将 $p$ 右侧区间的左右界压入栈（按 $r,p + 1$ 顺序入栈） 5. $while$ 结束时排序完成，返回此时的 $arr$ 。 非递归快排代码实现后续给出，与递归快排一样，在 $partition$ 方法前加入如下两行实现主轴的随机选取； ```java int randIdx = new Random().nextInt(r - l + 1) + l; // randIdx 为 [left + 1, right] 下标范围内的随机数 swap(arr, l, randIdx); // 交换当前 arr[left] 与 arr[randIdx] ``` 在 $partition$ 方法前加入如下一行实现主轴的三数取中选取。 ```java median3(arr, l, r); ``` <br /> ### 双轴快排 **双轴快排是单轴快排的改进**，初次学习双轴快排需要仔细深入地理解各处细节，因此本小节将详细介绍其实现细节，展示确定双轴位置既区间划分的过程。 前述快排每次递归确定当前区间的主轴，并利用该主轴将当前区间划分为左右两个部分。双轴快排则以 **两个轴** $(pivot1, pivot2)$ 将当前区间划分为 **三个子区间**，双轴三区间的划分结果要满足如下。为方便叙述，将 $[left, pivot1)$ 称作区间1，$(pivot1, pivot2)$ 称作区间2， $(pivot2, right]$ 称作区间3，其中 $pivot1$ ，$pivot2$ 指的是最终位置，区间1，区间2，区间3均指划分后的最终区间。 ``` 区间1: arr[i] < arr[pivot1], i ∈ [left, pivot1) 区间2: arr[pivot1] ≤ arr[i] ≤ arr[pivot2], i ∈ (pivot1, pivot2) 区间3: arr[i] > arr[pivot2], i ∈ (pivot2, right] ``` 对三个子区间执行同样的过程，直到无法划分时排序完成。 算法主要过程和说明如下，结合后续代码实现的注释可准确把握各处细节。 1. $dualPivotQuickSort$ 执行开始，首先以 `if(left < right)` 为条件，只对大小大于等于 2 的区间执行双轴快排。 2. 以如下语句 **令左右两端元素中较小者居左** ，后续以 $left$ 为初始 $pivot1$ (下标)，$right$ 为初始 $pivot2$ (下标)，保证 $pivot1$ 为左右两端元素中的较小者。 在程序后续内容中，$arr[left]$ 为 $pivot1$ 的值(左轴值)，$arr[right]$ 为 $pivot2$ 的值(右轴值)。 ```java if(arr[left] > arr[right]) { swap(arr, left, right); } ``` 1. 设置 $index = left + 1$ ，$lower = left + 1$，$upper = right - 1$ 。 $index$ 表示当前考察的元素下标。 $lower$ 是用于推进到 $pivot1$ 最终位置的动态向右扩展的下标（扩展区间1），在程序的任意时刻总有 $[left, lower)$ 的元素 **确定在区间1中** 。 $upper$ 是用于推进到 $pivot2$ 最终位置的动态向左扩展的下标（扩展区间3），在程序的任意时刻总有 $(upper, right]$ 的元素 **确定在区间3中** 。 当循环结束时 $lower--$ 和 $upper++$ 为最终的 $pivot1$ 和 $pivot2$ 的位置。 ``` 初始时lower == left + 1，表示区间1元素个数为1， 因为lower以左(不含lower)才是确定在区间1中的元素。 在遍历结束后以两个swap完成双轴归位时， 最后一个确定在区间1的元素会与arr[left]交换。 所以说我们一开始就知道left处的元素最终一定在区间1中， 因此初始时令lower == left + 1。 upper == right - 1的初始取值也是基于同样的原因。 如果现在还无法很好地理解这一点，先将整个过程看完后再回过头来多推敲几次。 ``` 2. 从此处开始，代码行为是要遍历从 $left + 1$ 到 $right - 1$ 的所有元素，通过与 $arr[left]$ (左轴值) 和 $arr[right]$ (右轴值) 的比较，以及元素交换操作，将 **每一个元素正确地置于区间1，区间2和区间3** 中，与此同时，以 $lower$ 的动态右移和 $upper$ 的动态左移，不断扩展这三个区间。 **通过 $index++$，从左到右依次遍历所有元素**，当所有元素遍历完成，也就意味着所有元素都已归于其应属的区间。显然，这些操作应在一个 **循环** 之内，下面进入该循环。 1. 首先，循环的边界条件是 `while(index <= upper)` 。虽然还未开始分析 $upper$ 的动态变化，但已经知道 $upper$ 以右 (不含 $upper$ ) 的元素是确定在区间3中的，$index$ 向右推进的时候不能超过 $upper$ ，因为下标为 $upper + 1$ 的元素是已确定在区间3中的 (但下标为 $upper$ 的元素尚未确定其归属)，所以是 $<=$。 2. 以 `if(arr[index] < arr[left])` 考察 $arr[index]$ 是否应在区间1，若满足则在区间1。这意味需要将该元素置于 $lower$ 左侧，且区间1需向右扩展1位，通过如下两行，交换 $arr[index]$ 和 $arr[lower]$ 后 $lower++$ 来完成。 ```java swap(arr, index, lower); lower++; ``` 3. 类似地，以 `else if(arr[index] > arr[right])` 考察 $arr[index]$ 是否应在区间3，若满足则在区间3。这意味着需要将该元素置于 $upper$ 右侧，且区间3需向左扩展1位。与上一步(4.2)不同的是，不能直接执行如下两行，即交换 $arr[index]$ 和 $arr[upper]$ 后 $upper--$ 。因为如果被交换的当前的 $arr[upper]$ 也是应当位于区间3中的元素，交换后，继续考察下一个元素，且因为考察界满足 i$ndex <= upper$ ，将导致该元素无法再被考察，也就无法将其正确地放入区间3中。而上一步并不存在该问题(因为与 $arr[index]$ 交换的 $arr[lower]$ 一定是属于区间2的元素)。 ```java swap(arr, index, upper); upper--; ``` 因此，在执行上述两行之前，应该实现一种操作，使得与 $arr[index]$ 交换的 $arr[upper]$ 不是区间3中的元素。于是可以先从当前 $arr[upper]$ 往左考察是否有 $arr[upper] > arr[right]$ ，若满足则表示 $arr[upper]$ 确定在区间3中，于是 $upper--$ 扩展区间3，直到不满足时表示此时 $arr[upper]$ 确定为不在区间3中的元素，于是才交换 $arr[index]$ 和 $arr[upper]$，然后 $upper--$ ，如下。需要注意的是 $while$ 中还有一个条件，即 $index < upper$ ，因为区间3左扩不可使 $index == upper$ ，否则之后的第二条 $upper--$ 将导致 $upper$ 为一个已经确定了区间归属的元素的位置（ $arr[index - 1]$ 为已考察过元素）。 ```java while(arr[upper] > arr[right] && index < upper) { upper--; } swap(arr, index, upper); upper--; ``` 如上，交换 $arr[index]$ 和 $arr[upper]$ 后，此时的 $arr[index]$ 确定不在区间3中，但在区间1还是区间2中仍需明确，否则之后 $index++$ 跳过该元素后将可能导致该元素归属错误。于是再对其执行一次与4.2相同的步骤。 ```java if(arr[index] < arr[left]) { swap(arr, index, lower); lower++; } ``` 上述 $if$ 和 $elseif$ 完成了对一个属于区间1和区间3元素考察和处理，不满足 $if$ 且不满足 $elseif$ 的元素属于区间2，其已处于 $(lower, upper)$ 之间，无需移动。 前述操作完成了对 $arr[index]$ 的考察和处理（移动或不移动），于是 $index++$ ，考察下一个元素。 3. 当 `while(index <= upper)` 结束时，所有元素考察处理完毕，此时最后一个确定在区间1的元素下标是 $lower--$ ，最后一个确定在区间3的元素下标是 $upper++$ 。如下，通过交换将初始轴归于其正确的位置。最后对三个子区间分别递归地执行双轴快排。 ```java lower--; upper++; swap(arr, left, lower); swap(arr, upper, right); dualPivotQuickSort(arr, left, lower - 1); // 区间1 dualPivotQuickSort(arr, lower + 1, upper - 1); // 区间2 dualPivotQuickSort(arr, upper + 1, right); // 区间3 ``` 下图展示了双轴快排对 $\{29, 46, 21, 90, 14, 1, 68, 34, 55, 8\}$ 的双轴位置确定也即区间划分的过程。浅蓝色表示未排序，绿色表示左轴值，深蓝色表示右轴值，黄色表示区间1，灰色表示区间2，橙色表示区间3。  <!--  --> <br /> ### 复杂度分析 时间复杂度：平均 / 最好为 $O(nlogn)$，最坏为 $O(n^2)$。 单轴快排每次 $partition$ 主轴均居中，则递归深度为 $i$ 的 $partition$ 有 $2^i$ 个， 这 $2^i$ 个 $partition$ 需要比较的次数是 (除去 $2^{i-1}$ 个主轴元素的元素个数) $n - 2^{i-1}$。给出如下复杂度估计。 $$ \begin{aligned} T(n) &=\sum_{i=1}^{\log n}\left(n-2^{(i-1)}\right) \\ &=n \log n-\left(1-2^{\operatorname{logn}}\right) /(1-2) \\ &=n \log n-n+1 \end{aligned} $$ 可知时间复杂度为 $O(nlogn)$。 也可通过如下递推式导出。 $$ T(n)=2 T(n / 2)+O(n) $$ 严格来说等号右边应该为 $2T((n-1)/2)+O(n)$，因为确定轴之后轴元素不参与两分区划分，但并不影响结果的正确性，求解该递推式的方法在归并排序中已介绍过，最终同样得到时间复杂度为 $O(nlogn)$。 ※ 观察前一个式子 $T(n)=nlogn-n+1$ ，我们发现该式子虽然与归并排序时间复杂度同阶，但单从式子上看，比归并排序得到的结果要更小。这大概也是快速排序能够从一众 $O(nlogn)$ 复杂度的排序方法中脱颖而出的一个原因。 双轴快排递推式如下，用同样的方法可得到 $O(nlog_3n)$。对数的底数为3，相比单轴快排的底数2，双轴快排的复杂度更低，效率更高。 $$ T(n)=3 T(n / 3)+O(n) $$ **最坏情形** 时间复杂度： 对于单轴快排，当输入为已排序数组，且采用首位为主轴的方式，第 $i$ 次 $partition$ 后主轴左右两部分总是 $left = null$ ，$right = n - i,$ 第 $i$ 次 $partition$ 需要比较 $n - i$ 次，共有 $n$ 次 $partition$ ，总比较次数 $O(n^2)$。类似于对已排序的数组做 **选择排序**。 左右两端取轴的双轴快排对于已排序数组，同样是 $O(n^2)$ 的最坏情形。 空间复杂度：递归形式的快排，取决于递归深度，为 $O(logn)$。非递归形式的快排，保存分区信息的栈深度与递归深度相同，空间复杂度也是 $O(logn)$。 不同于归并排序中需要借助一个临时数组保存每次合并的结果，快速排序以原地交换元素的形式，避免了 $O(n)$ 的数组开销。 <br /> ### 代码 #### 单轴快排递归实现 ##### 首位轴 ```java // 单轴快排：首位为轴 public int[] quickSortSimple(int[] arr) { if (arr.length < 2) return arr; quickSortSimple(arr, 0, arr.length - 1); return arr; } // 单轴快排递归方法：首位为轴 private void quickSortSimple(int[] arr, int l, int r) { if (l < r) { // 若left == right，表示此时 arr 只有一个元素，即为基准情形，完成递归 int p = partition(arr, l, r); quickSortSimple(arr, l, p - 1); quickSortSimple(arr, p + 1, r); } } ``` <br /> ##### 三数取中轴 ```java // 单轴快排：三数取中 public int[] quickSortMedian3(int[] arr) { if (arr.length < 2) return arr; quickSortMedian3(arr, 0, arr.length - 1); return arr; } // 单轴快排递归方法：三数取中 private void quickSortMedian3(int[] arr, int l, int r) { if (l < r) { median3(arr, l, r); // 执行median3将左，中，右三数中值放到left位置上 int p = partition(arr, l, r); quickSortMedian3(arr, l, p - 1); quickSortMedian3(arr, p + 1, r); } } // 将left, center, right下标三个数中，大小居中者放到left下标处 private void median3(int[]arr, int l, int r) { int c = l + (r - l) / 2; if (arr[l] > arr[c]) swap(arr, l, c); // 左中，大者居中 if (arr[c] > arr[r]) swap(arr, c, r); // 中右，大者居右，此时最大者居右 if (arr[c] > arr[l]) swap(arr, l, c); // 左中，大者居左，此时中者居左 } ``` <br /> ##### 随机轴 ```java // 单轴快排：随机轴 public int[] quickSortRandom(int[] arr) { if (arr.length < 2) return arr; quickSortRandom(arr, 0, arr.length - 1); return arr; } // 单轴快排递归方法：随机轴 private void quickSortRandom(int[] arr, int l, int r) { if (l < r) { int randIdx = new Random().nextInt(r - l) + l + 1; // 在 [left + 1, right] 范围内的随机值 swap(arr, l, randIdx); // arr[l] 与它之后的某个数交换 int p = partition(arr, l, r); quickSortRandom(arr, l, p - 1); quickSortRandom(arr, p + 1, r); } } ``` <br /> #### 单轴快排迭代实现(利用栈) ##### 首位轴 ```java // 单轴快排迭代实现（利用栈）：首位为轴 public int[] quickSortStackSimple(int[] arr) { if(arr.length < 2) return arr; Deque<Integer> stack = new ArrayDeque<>(); // 保存区间左右边界的栈，按right到left的顺序将初始区间界入栈 stack.push(arr.length - 1); stack.push(0); while(!stack.isEmpty()) { // 判断栈是否空，不空则弹出一对left，right界 int l = stack.pop(), r = stack.pop(); if(l < r) { // 执行partition的前提是 left 小于 right int p = partition(arr, l, r); stack.push(p - 1); stack.push(l); stack.push(r); stack.push(p + 1); } } return arr; } ``` <br /> ##### 三数取中轴 ```java // 单轴快排迭代实现（利用栈）：三数取中 public int[] quickSortStackMedian3(int[] arr) { if(arr.length < 2) return arr; Deque<Integer> stack = new ArrayDeque<>(); // 保存区间左右边界的栈，按right到left的顺序将初始区间界入栈 stack.push(arr.length - 1); stack.push(0); while(!stack.isEmpty()) { // 判断栈是否空，不空则弹出一对left，right界 int l = stack.pop(), r = stack.pop(); if(l < r) { // 执行partition的前提是 left 小于 right median3(arr, l, r); int p = partition(arr, l, r); stack.push(p - 1); stack.push(l); stack.push(r); stack.push(p + 1); } } return arr; } ``` <br /> ##### 随机轴 ```java // 单轴快排迭代实现（利用栈）：随机轴 public int[] quickSortStackRandom(int[] arr) { if(arr.length < 2) return arr; Deque<Integer> stack = new ArrayDeque<>(); // 保存区间左右边界的栈，按right到left的顺序将初始区间界入栈 stack.push(arr.length - 1); stack.push(0); while(!stack.isEmpty()) { // 判断栈是否空，不空则弹出一对left，right界 int l = stack.pop(), r = stack.pop(); if(l < r) { // 执行partition的前提是 left 小于 right int randIdx = new Random().nextInt(r - l + 1) + l; swap(arr, l, randIdx); int p = partition(arr, l, r); stack.push(p - 1); stack.push(l); stack.push(r); stack.push(p + 1); } } return arr; } ``` <br /> #### 双轴快排 ```java public int[] dualPivotQuickSort(int[] arr) { if (arr.length < 2) return arr; dualPivotQuickSort(arr, 0, arr.length - 1); // 后两个参数是下标值 return arr; } /* * 区间1 区间2 区间3 * +------------------------------------------------------------+ * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | * +------------------------------------------------------------+ * ^ ^ ^ * | | | * lower index upper */ private void dualPivotQuickSort(int[] arr, int left, int right) { if(left < right) { // 排序对象是right大于left的区间（即大小大于等于2的区间） // 令左右两端元素中较小者居左，以left为初始pivot1，right为初始pivot2 // 即arr[left]为选定的左轴值，arr[right]为选定的右轴值 if(arr[left] > arr[right]) { swap(arr, left, right); } int index = left + 1; // 当前考察元素下标 int lower = left + 1; // 用于推进到pivot1最终位置的动态下标，总有[left, lower)确定在区间1中 int upper = right - 1; // 用于推进到pivot2最终位置的动态下标，总有(upper, right]确定在区间3中 // [lower, index)确定在区间2中，[index, upper]为待考察区间。 // upper以右（不含upper）的元素都是确定在区间3的元素，所以考察元素的右界是upper while(index <= upper) { // 若arr[index] < arr[left]，即arr[index]小于左轴值，则arr[index]位于区间1 if (arr[index] < arr[left]) { // 交换arr[index]和arr[lower]，配合后一条lower++，保证arr[index]位于区间1 swap(arr, index, lower); // lower++，扩展区间1，lower位置向右一位靠近pivot1的最终位置 lower++; } // 若arr[index] > arr[right]，即arr[index]大于右轴值，则arr[index]位于区间3 else if(arr[index] > arr[right]) { // 先扩展区间3，使得如下while结束后upper以右（不含upper）的元素都位于区间3 // 区间3左扩不可使index == upper，否则之后的第二条upper--将导致upper为一个已经确定了区间归属的元素的位置（即index - 1） while(arr[upper] > arr[right] && index < upper) { upper--; } // 交换arr[index]和arr[upper]，配合后一条upper--，保证arr[index]位于区间3 swap(arr, index, upper); upper--; // 上述交换后，index上的数字已经改变，只知道此时arr[index] ≤ arr[right]，arr[index]有可能在区间1或区间2， // 若arr[index] < arr[left]，即arr[index]小于左轴值，则arr[index]位于区间1 if(arr[index] < arr[left]) { // 交换arr[index]和arr[lower]，配合后一条lower++，保证arr[index]位于区间1 swap(arr, index, lower); // lower++，扩展区间1，lower位置向右一位靠近pivot1的最终位置 lower++; } } index++; // 考察下一个数字 } // while(index <= upper)结束后最后一个确定在区间1的元素的下标是lower--， // 最后一个确定在区间3的元素下标是upper++。 lower--; upper++; // 双轴归位。此时的lower，upper即分别为最终pivot1(初始时为left)，最终pivot2(初始时为right)。 swap(arr, left, lower); swap(arr, upper, right); // 对三个子区间分别执行双轴快排 dualPivotQuickSort(arr, left, lower - 1); // 区间1 dualPivotQuickSort(arr, lower + 1, upper - 1); // 区间2 dualPivotQuickSort(arr, upper + 1, right); // 区间3 } } ``` <br /> ## 堆排序 ### 算法描述 堆排序算法建立在 [堆数据结构](https://en.wikipedia.org/wiki/Heap_(data_structure)) 的基础上，本节假设读者对堆数据结构已有基本了解。 将输入数组建立为一个 **大顶堆**，反复取出堆顶逆序排列 (最先取出的放在最后) ，并对剩余元素重建大顶堆，即可将原数组从小到大排列完成排序。 一个直接的想法是在原数组之外新建一个数组保存每次取得的堆顶，这样会有 $O(n)$ 的空间开销，可以用一种称作 **「原地堆排序」** 的技巧避免此开销，具体做法如下。 1. 首先将原待排序数组 $arr[]$ 建立为一个大顶堆 ( $heapify$ 堆化方法)。 2. 交换堆顶和当前未排序部分中最末尾元素，则堆顶元素已排序（此时在数组最末尾）。 3. 剩余元素中 **只有当前堆顶** (上一步被交换的末尾元素) 可能造成 **堆失序**，因此只需对堆顶调用一次调整堆序的下滤 ($siftDown$) 操作 (操作范围为未排序部分) ，即可恢复未排序部分的堆序。 4. 重复 2，3 直到所有元素已排序，返回 $arr[]$ 。 上述通过交换堆顶与当前未排序部分末尾元素的做法，避免了额外的空间开销，即 **原地堆排序**，程序结束后返回的 $arr[]$ 为已排序状态。 **稳定性：不稳定。** 交换可能会破坏稳定性。例：输入数组 $\{1, 2_{red}, 2_{green}\}$ ，灰色表示已排序。排序后最终为 $\{1, 2_{green}, 2_{red}\}$ ,可以看到 $2_{red}$ 和 $2_{green}$ 的相对顺序相比输入已改变。  <!--  --> <br /> #### 堆化方法 (heapify) 将原输入数组看作一棵 [完全二叉树(Complete Binary Tree)](https://www.programiz.com/dsa/complete-binary-tree) 。根节点下标为 0，于是根据完全二叉树的结构性质，任意一个节点 (下标为 $i$ ) 的左子节点下标为 $2 * i + 1$，右子节点下标为 $2 * i + 2$，父节点下标为 $(i-1) / 2$。 **堆化过程即使得整棵树满足堆序性质**，也即任意一个节点大于等于其子节点（大顶堆）。 一句话总结堆化操作：对最后一个非叶子节点到根节点，依次执行下滤操作 ($siftDown$) 。 从最后一个非叶子开始下滤的原因是此节点之后的节点均为叶子节点，叶子节点无子节点，故其本身已满足堆序性质，也就无下滤的必要 (也不会下滤)。每一次下滤使得该节点及其之后的节点都满足堆序性质，直到根节点。 ※ 最后一个非叶子节点 (也即最后一个元素的父节点) 下标为 $(n - 1) / 2$，$n$ 为数组长度。 如下 [动图](https://tva1.sinaimg.cn/large/008i3skNgy1gyopuk6qs7g30i603ntby.gif) 是将输入数组 $\{4, 6, 2, 1, 7, 9, 5, 8, 3\}$ (1为最后一个非叶子结点) 堆化成大顶堆 $\{9, 8, 5, 6, 7, 2, 4, 1, 3\}$ 的过程。  <!--  --> <br /> #### 下滤方法(siftDown) **下滤 (siftDown) 是堆排序的核心方法**，在堆排序中的如下两种操作中调用： - 排序开始时 **创建大顶堆** 的堆化方法 - 每次排序堆顶时用于 **恢复未排序部分的堆序** 该方法在堆数据结构中用于删除堆顶元素操作，因此先介绍下滤在删除堆顶元素操作中的处理过程。 如下 [动图](https://tva1.sinaimg.cn/large/008i3skNgy1gyosplo6zzg30i603nwga.gif) 展示了删除大顶堆 $\{9, 8, 5, 6, 7, 2, 4, 1, 3\}$ 堆顶元素 9 的过程（动图中出现的100表示堆顶，值为9）。 1. 删除堆顶，堆中元素减 1，将当前最后一个元素 3 暂时置为堆顶。 2. 可以看到，此时只有该堆顶元素 3 导致堆失序，于是交换其与左右子节点中的较大者。 3. 对元素 3 重复操作 2 ，直到恢复堆序。 恢复堆序的过程就是将影响堆序的元素不断向下层移动 (并交换) 的过程，因此形象地称之为下滤 ($siftDown$) 。 ※ 注意，此处沿用 JDK 源码中下滤操作的方法名 $siftDown$，**sift 为过滤之意**，网上有的博客文章将其讹误成 shift，请读者仔细分辨。  <!--  --> 可以看到，对节点 $x$ 的下滤操作的本质是恢复以 $x$ 为根节点的树的堆序。因此在堆化操作中，只需要分别依次地对最后一个非叶子节点到根节点执行下滤操作，即可使整棵树满足堆序。在排序过程中，每次原地交换后 (交换当前堆顶与当前未排序部分最后一个元素)，只有新堆顶影响堆序，对其执行 **一次** 下滤操作 (范围为未排序部分) 即可使未排序部分重新满足堆序。 <br /> ### 复杂度分析 时间复杂度：原地堆排序的时间复杂度为 $O(nlogn)$。 建堆时间复杂度: $O(n)$，证明如下。 以完全二叉树为例，以根节点为第 1 层，共 $h$ 层。第 $k$ 层有 $2^{k-1}$ 个元素，该层每个元素至多下滤 $h - k$ 次。于是所有元素最大下滤次数总和为： $$ S=\sum_{k=1}^{h-1} 2^{k-1}(h-k) $$ $$ S=h-1+2(h-2)+4(h-3)+\ldots+2^{h-2} $$ $$ 2S=2(h-1)+4(h-2)+8(h-3)+\ldots+2^{h-1} $$ 下式 $2S$ 减去上式 $S$ 得到 $$ S=-h+1+2+4+\ldots+2^{h-1}=2^{h}-1-h $$ 我们已经知道，该堆总元素数为 $n = 2^h - 1$，因此 $S=n-h=n-log(n+1)$ ，建堆时间复杂度为 $O(n)$。 原地交换至排序完成时间复杂度：$O(nlogn)$，证明如下。 当前堆顶通过交换完成排序时，其下滤次数取决于当前树高，设当前未排序元素个数为 $i$ ，其下滤次数最多为层高减1 (根节点为第1层) ，可估计为 $logi$。每排序一次堆顶，待排序部分元素个数减1，于是从一个大顶堆开始完成排序所需时间取决于 $n - 1$ 次堆顶下滤 (下滤范围分别为 $n, n -1, n-2,...,1$ ) 次数总和最大值 (实际上只剩一个元素时排序已经完成，对于最后一个元素无需下滤，不过考虑到 $log1=0$ 并不影响结果，因此 $i$ 仍从 1 开始)。 $$ \sum_{i=1}^{n} \log i $$ 由 [Stirling公式](https://en.wikipedia.org/wiki/Stirling%27s_approximation) 得到 $$ \sum_{i=1}^{n} \log i=\log (n !)=n \log n-n \log e+\Theta(\log n) $$ 于是时间复杂度为 $O(nlogn)$。最好 / 平均 / 最坏时间复杂度均为 $O(nlogn)$。 但若考虑数组所有元素均相等，则建堆和原地交换时下滤次数为0，时间复杂度取决于建堆和原地交换时的比较次数，为 $O(n)$， ※ $Stirling$ 公式详细证明过程可参考：[谈Stirling公式](http://episte.math.ntu.edu.tw/articles/mm/mm_17_2_05/index.html) 再次强调「建堆时间」与「排序时间」的区别： - 建堆时间：所有元素从其所在位置开始下滤的时间总和 - 排序时间：所有元素从堆顶位置开始下滤的时间总和 空间复杂度：原地对排序算法中只有常数项变量，$O(1)$。 <br /> ### 代码 ```java // 堆排序 public int[] heapSort(int[] arr) { if (arr.length < 2) return arr; heapify(arr, arr.length - 1); // 构建大顶堆 for (int i = arr.length - 1; i > 0; i--) { // i > 0 即可，无需写成 i >= 0，当 N-1 个元素排序时，最后一个元素也已排序 swap(arr, 0, i); // 交换堆顶和当前未排序部分最后一个元素 siftDown(arr, 0, i - 1); // i - 1 是未排序部分最后一个元素下标，传入此参数确保下滤不会超过此范围 } return arr; } // 堆化方法 private void heapify(int[] arr, int r) { for (int hole = (r - 1) / 2; hole >= 0; hole--) { // (r - 1) / 2 为最后一个叶子节点的父节点下标 siftDown(arr, hole, r); } } // 下滤方法 private void siftDown(int[] arr, int hole, int r) { int target = arr[hole], child = hole * 2 + 1; // target 是要下滤的结点的值 while(child <= r) { // child 最大为 r if (child < r && arr[child + 1] > arr[child]) child++; // #1 if (arr[child] > target) { // 若 child 大于 target arr[hole] = arr[child]; // 则 arr[child] 上移到下标 hole 处 hole = child; // hole 更新为 child (下滤) child = hole * 2 + 1; // 更新 child ，也可以写成 child = child * 2 + 1 } else break; // 若 arr[child] <= target ，说明下标 hole 处已经满足堆序，退出 while } arr[hole] = target; // 将 target 填 入hole 中 } ``` 下滤方法 $siftDown$ 中 `#1` 行的详细说明： ```java if (child < r && arr[child + 1] > arr[child]) child++; ``` - 满足第一个条件 `child < r` 表示 $hole$ 有右孩子，不满足则 $hole$ 无右孩子，跳过 - 第二个条件 `arr[child + 1] > arr[child]` 只在第一个条件成立前提下进行判断（因此不必担心 `arr[child + 1]` 越界） - 若两个条件均满足，表示 $hole$ 有右孩子且右孩子更大，令 $child$ 为右孩子下标 - 此 $if$ 过后，$child$ 为 $hole$ 的孩子中值较大者的下标 <br /> ## 计数排序 ### 算法描述 计数排序是我们介绍的第一种 **非比较排序**，通常 **适用于整数数组**，是一种利用整数特点取得 **线性复杂度** 的非比较排序方法。假设待排序数组 $arr$ 为正整数数组， **朴素** 的计数排序过程如下： 1. 创建一个计数数组 $countArr$ ，其大小为 $arr$ 中的最大值 $max$ 再加 1。 2. 遍历 $arr$ ，每读取一个$arr[i]$ ，直接令$countArr[arr[i]]++$。 3. 从下标 1 开始遍历 $countArr$ ，依次输出 $counter[i]$ 个 $i$ ，即为排序结果。 朴素做法有两个明显的缺陷： - 无法处理负数。 - 空间冗余。当元素个数较多，但很多相等元素使得元素分布 **集中在较小范围** 时，$max+1$ 大小的 $countArr$ 中大部分空间是多余的。改进方法很简单，即创建大小为 $max - min + 1$ 的 $countArr$ ，$max$ 和 $min$ 分别是 $arr$ 中最大和最小元素。后续代码将采用该改进。 如下 [动图](https://tva1.sinaimg.cn/large/008i3skNly1gyr7qbd8iyg307t07fe82.gif) 展示了 $\{4,6,2,1,7,9,5,8,3,1,1\}$ 的计数排序过程 (不稳定版) 。  <!--  --> **稳定性：取决于是否采用稳定性优化版本。** 采用则稳定，不采用则不稳定，稳定优化方法见后。 <br /> ### **稳定性优化** 未经优化的计数排序 **不稳定** 。通过计数来排序，当遍历 $countArr[i]$ 输出排序结果时，只是连续地输出 $countArr[i]$ 次 $i + min$ ，稳定性得不到保证 (比如动图中，后放入的 1 会先输出) 。要保证稳定，必须使 **先记录的先输出**。可以通过对 $countArr$ **变形** 来满足稳定性，使得遍历到同一个数字，例如 $k$ 时，能够将不同位置的 $k$ 按他们在 $arr$ 中出现的顺序放入到输出数组中。具体做法如下。 1. 得到 $countArr$ 后，遍历一次 $countArr$ ，使得每一个 $countArr[i]$ 的值都是从 $countArr[0]$ 到 $countArr[i]$ 中值不为 0 的项的值之和（前缀和）。例如对于待排序数组 $\{5, 5, 4, 4, 1, 1\}$ ，得到大小为 `5 - 1 + 1 = 5` 的 $countArr$ ，具体为 ${2, 0, 0, 2, 2}$ ，表示有两个1，0个2，0个3，2个4，2个5。按照前述方法将其变形为 $\{2, 0, 0, 4, 6\}$ ，表示 1 的最大位置为第 2 位 (下标为1)， 4 的最大位置为 4 (下标为 3 )， 5 的最大位置为 6 (下标为 5 )。 2. 在输出排序结果时，新建一个大小等于 $arr$ 的 $sortedArr$ 数组，于是 $countArr[arr[i] - min] - 1$ 即为 $arr[i]$ 这个数应当放入 $sortedArr$ 的位置(下标)，即 $sortedArr[countArr[arr[i] - min] - 1] = arr[i]$ ，以倒序从 $arr.length$ 遍历到 0 ，每次向 $sortedArr$ 填入一个数字后，令 $countArr[arr[i] - min]--$ 。遍历结束后得到的 $sortedArr$ 即为 $arr$ 的稳定排序结果 (建议实际动手验证这个过程) 。 <br /> ### 复杂度分析 时间复杂度：朴素版为 $O(max)$，$max$ 为原数组中最大值。改进版为 $O(n + k)$，$n$ 为元素个数， $k$ 计数数组大小。当元素个数较少但最大最小值差值很大时，复杂度取决于 $k$ 。 空间复杂度：不考虑输入数组 $arr$ ，朴素版的 $countArr$ 的大小为 $k+1$ ，故空间复杂度为 $O(k)$。稳定性优化版为 $O(n + k)$， $n$ 为 $sortedArr$ 的大小，等于 $arr$ 的大小。 <br /> ### 代码 #### 不稳定计数排序 ```java public int[] countingSortUnstable(int[] arr) { if (arr.length < 2) return arr; int n = arr.length, min = arr[0], max = arr[0]; for (int i = 1; i < n; i++) { // 确定 min 和 max min = Math.min(min, arr[i]); max = Math.max(max, arr[i]); } int[] countArr = new int[max - min + 1]; // arr 最多有 max-min+1 种数字 for (int i = 0; i < n; i++) { // 计数 countArr[arr[i] - min]++; // arr[i] 的值出现一次，则 countArr[arr[i]-min] 加 1 } int index = 0; for (int i = 0; i < countArr.length; i++) { // 依次取出 for (int j = 0; j < countArr[i]; j++) { arr[index] = i + min; // 排序 index++; } } return arr; } ``` <br /> #### 稳定计数排序 ```java public int[] countingSort(int[] arr) { if (arr.length < 2) return arr; int n = arr.length, min = arr[0], max = arr[0]; for (int i = 1; i < n; i++) { // 确定 min 和 max min = Math.min(min, arr[i]); max = Math.max(max, arr[i]); } int[] countArr = new int[max - min + 1]; // arr 最多有 max-min+1 种数字 for (int i = 0; i < n; i++) { // 计数 countArr[arr[i] - min]++; // arr[i] 的值出现一次，则 countArr[arr[i]-min] 加 1 } for (int i = 1; i < countArr.length; i++) { // 变形 countArr[i] += countArr[i - 1]; } int[] sortedArr = new int[n]; // 根据 sortedArr, arr, countArr 三者关系完成 sortedArr 的输出 for (int i = n - 1; i >= 0; i--) { // 逆序输出保持稳定性 int countIdx = arr[i] - min; // arr[i] 元素对应 countArr 中的下标 int sortedIdx = countArr[countIdx] - 1; // 在排序后数组中的下标 sortedArr[sortedIdx] = arr[i]; // 在排序后数组中填入值 countArr[countIdx]--; // countArr[countIdx] 已排序一位，下一个该位置的数的排位要靠前一位 } return sortedArr; } ``` <br /> ## 基数排序 ### 算法描述 **非比较排序**，「基」指的是数的位，例如十进制数 123，共有百十个位，共 3 「位」。基数排序 **按数字的位进行循环**，每一轮操作都是对**当前位 (基数) 的计数排序**，使得输出到 $arr$ 后所有数字在截止到当前位上 (即去掉未考察的位后) 是排序状态，考察完最大位后完成排序。具体过程如下： 1. 求最大位。遍历待排序数组 $arr$ ，找到绝对值最大的数字，计算其位数 (称其为宽度 $width$ )，例如 $arr$ 中最大数为 123 ，则 $width = 3$ 。 2. 数组的数字为 $n$ 进制，就创建大小为 $n$ 的计数数组 $countArr$ ，也可以称为 $n$ 个桶。 3. 开始针对「位」的 $for$ 循环，循环次数等于 $width$ ，每一轮对 **当前所有数字的当前位** 执行一次 **计数排序**。 4. 每次计数排序结束后将结果写回 $arr$ 。 5. $for$ 循环结束后返回排序结果 $arr$ 。 如下 [动图](https://tva1.sinaimg.cn/large/008i3skNgy1gysb1jsbaog30cc07rwkq.gif) 演示 $\{6674, 1560, 5884, 2977, 2922, 4127, 5390, 7870, 1193, 7163\}$ 的基数排序过程。  <!--  --> **也可以不使用计数排序**，而是创建一个二维数组 (可看作19个桶) 保存每次遍历的中间结果，此写法耗费的空间较大 (每个桶的大小都要等于 $arr$ 大小 +1，空间复杂度为 $O(19n)$ )，是稳定排序，不详细说明，可参考后续给出的代码实现。 - 以计数排序为基础的基数排序，每一位循环时都对所有数做该位的计数排序。 - 不以计数排序为基础的基数排序，每一位循环时都将所有数按顺序放入相应的桶中。 <br /> **稳定性：稳定。** 基数排序要求对每一位的排序 (计数排序或非计数排序) 必须是稳定排序，否则无法得到正确结果。例如对 $\{25,13,24\}$ 执行排序。第一轮针对个位的排序过后得到 $\{13,24,25\}$ ，若对位的排序不稳定，则第二轮针对十位上的 $\{1,2,2\}$ 的排序将可能得到 $\{13,25,24\}$ ，排序结束得到错误结果。基于稳定的位排序 (例如稳定的计数排序) 的基数排序，也一定是稳定的。 <br /> ### 处理负数优化 若存在负数，可以先找到最小值 (负数) ，对 $arr$ 中的每个数，都加上此最小值的绝对值，排序完成后再减回去。但加法可能使得 **数字越界**，一种更好的办法是计数排序时 **将 $countArr$ 的大小扩展为 19**，以 $[0, 19]$ 对应可能出现的 $[-9, 9]$ 。因此在每轮求当前基数时，要在原基数结果上 +9 以对应 $countArr$ 的下标。 后续代码给出利用计数排序的应用此优化的版本。 <br /> ### 复杂度分析 时间复杂度： $d$ 为绝对值最大的元素位数，总共进行 $d$ 轮计数排序，$O(n+k)$ 是计数排序的复杂度，其中 $k$ 是位的取值范围，如果是非负数，则 $k=10(0\sim 9)$，如果包含负数，则 $k=19(-9 \sim 9)$ 。所以总的时间复杂度为 $O(d(n+k))$。 空间复杂度： 利用计数排序的基数排序，空间复杂度与计数排序相同，为 $O(n + k)$。 不利用计数排序的计数排序，将以19个（应用处理负数优化）「桶」的二维数组作为排序过程中的存储空间，故空间复杂度为 $O(19n)$，当 $n$ 显著大于 19 时也可认为其空间复杂度为 $O(n)$。 <br /> ### 代码 #### 以计数排序为基础 ```java public int[] radixSort(int[] arr) { if (arr.length < 2) return arr; int n = arr.length, max = Math.abs(arr[0]); for (int i = 1; i < n; i++) { // 找到 arr 中绝对值最大者 max = Math.max(max, Math.abs(arr[i])); } int width = 0, base = 10; while (max != 0) { // 求最大数的位数 width++; max /= base; } int[] sortedArr = new int[n]; for (int i = 0; i < width; i++) { // 每一轮都对当前位(基数)执行一次计数排序 int[] countArr = new int[19]; // 为应对有负数的情况，countArr范围为[-9, 9] for (int num : arr) { // 根据每一个数字当前位的数字，累计相应位置的计数 int bucketIdx = (num % base) / (base / 10) + 9; // 求当前位上的 (+9处理负数) countArr[bucketIdx]++; } for (int j = 1; j < countArr.length; j++) { // 变形 countArr[j] += countArr[j - 1]; } for (int j = n - 1; j >= 0; j--) { // 逆序输出保持稳定性 int countIdx = (arr[j] % base) / (base / 10) + 9; // arr[j] 元素当前位对应 countArr 中的下标 int sortedIdx = countArr[countIdx] - 1; // 在排序后数组中的下标 sortedArr[sortedIdx] = arr[j]; // 在排序后数组中填入值 countArr[countIdx]--; // countArr[countIdx] 已排序一位，下一个该位置的数的排位要靠前一位 } arr = Arrays.copyOf(sortedArr, n); // 完成当前位的计数排序后将排序结果拷贝回原数组 base *= 10; // base进一位，准备下一轮对高一位的计数排序 } return arr; } ``` <br /> #### 不以计数排序为基础 ```java public int[] radixSortWithoutCount(int[] arr) { if (arr.length < 2) return arr; int n = arr.length, max = Math.abs(arr[0]); // 找到arr中绝对值最大者 for (int i = 1; i < arr.length; i++) { max = Math.max(max, Math.abs(arr[i])); } int width = 0, base = 10; while (max != 0) { // 求最大数的位数 width++; max /= base; } int[][] buckets = new int[19][n + 1]; // 19个桶处理负数，n+1 的用意是让每个桶的第一个位置保存该桶的元素个数 for (int i = 0; i < width; i++) { // 在每一位上将数组中所有具有该位的数字装入对应桶中 for (int num : arr) { int idx = (num % base) / (base / 10) + 9; int cnt = buckets[idx][0]; buckets[idx][cnt + 1] = num; buckets[idx][0]++; } int arrIdx = 0; for (int j = 0; j < buckets.length; j++) { // 将当前所有桶的数按桶序，桶内从低到高输出为本轮排序结果 for (int k = 1; k <= buckets[j][0]; k++) { arr[arrIdx++] = buckets[j][k]; } } for (int[] bucket : buckets) bucket[0] = 0; // 每一轮过后将桶计数归零 base *= 10; // 调整base } return arr; } ``` <br /> ## 桶排序 ### 算法描述 桶排序将原数组划分到称为 **「桶」** 的多个区间中，然后对每个桶单独进行排序，之后再按桶序和桶内序输出结果。适合于分布较均匀的数据，具体做法如下。 1. 根据数据规模按照 **一定的方法** 将待排序数组 $arr$ 划分为多个区间，每个区间称作一个桶。 2. 每个桶可以是数组，也可以是泛型容器，用于保存 $arr$ 中落在该桶范围内的数。 3. 对每一个桶都单独排序，需要 **以适当的排序** 方法支持，例如插入排序，快速排序等。 4. 所有桶完成排序后，按桶序，桶内序依次输出所有元素，得到 $arr$ 的排序结果。 <br /> **稳定性：取决于桶内排序方法的稳定性。** <br /> ### 复杂度分析 时间复杂度： 找最大最小值和分配桶均耗费 $O(n)$，之后的复杂度取决于每个桶内的排序算法复杂度之和。假设有 $k$ 个桶，且数据分布均匀，若采用 $O(n^2)$ 的排序算法，那么总排序时间复杂度为 $O(n^2/k)$，若采用 $O(nlogn)$ 的排序算法，总排序时间复杂度为 $O(k(n/k)log(n/k))$，即 $O(nlog(n/k))$。若桶内排序采用 $O(nlogn)$ 算法，且 $k$ 的大小适当，例如 $k = n/p$，$p$ 是一个较小的数例如2，3等。那么整体的时间复杂度约为 $O(n)$。虽然形式上为线性复杂度，但其 $n$ 的系数较大，**未必优于** $O(nlogn)$ 的排序算法。 当所有元素都被分到同一个桶中，达到最大时间复杂度，为 $O(n^2)$ 或 $O(nlogn)$ (取决于桶内排序采用的排序方法)。 空间复杂度：取决于桶的数据结构，若采用静态数组，由于每个桶都需要保证有 $n$ 个位置，则空间复杂度为 $O(kn)$，若采用泛型容器，则为 $O(n)$。 <br /> ### 代码 ```java public int[] bucketSort(int[] arr) { if(arr.length < 2) return arr; int n = arr.length, k = n / 3, min = arr[0], max = arr[0]; // k=n/3 个桶 for (int i = 1; i < n; i++) { // 确定 min 和 max min = Math.min(min, arr[i]); max = Math.max(max, arr[i]); } List<ArrayList<Integer>> buckets = new ArrayList<>(k); for (int i = 0; i < k; i++) { // k 个桶 buckets.add(new ArrayList<>()); // 每个桶是一个ArrayList<Integer> } double interval = (max - min) * 1.0 / (k - 1); // 桶间隔 for (int num : arr) { // 遍历arr，根据元素值将所有元素装入对应值区间的桶中 int bucketIdx = (int) ((num - min) / interval); // arr[i] (num) 元素应该装入的桶的下标 buckets.get(bucketIdx).add(num); // 装入对应桶中 } for (ArrayList<Integer> bucket : buckets) { Collections.sort(bucket); // 桶内排序(调用库函数，从小到大) } int index = 0; for (ArrayList<Integer> bucket : buckets) { for (int sortedNum : bucket) { arr[index] = sortedNum; // 复用输入数组arr index++; } } return arr; } ``` <br /> ## 决策树 可以利用 **决策树** 来理解 **基于比较的排序** 算法的复杂度的理论下界为什么是 $O(nlogn)$。 > 本节内容学习自 Weiss 的 [数据结构与算法分析：Java语言描述](https://leetcode.cn/link/?target=https%3A%2F%2Fawesome-programming-books.github.io%2Falgorithms%2F数据结构与算法分析：Java语言描述.pdf) 。 $n$ 个不同元素组成的序列，有 $n!$ 种可能的排列。考虑这样一棵决策树，根处存放着所有 $n!$ 种可能的排序，比较其中两个元素 $a$ 和 $b$ ，只有两种可能 $a > b$ 或者 $a < b$（不考虑等于）。$a$ 和 $b$ 的大小关系确定后，都将去除根处 $n!$ 种排列中的一半。将 $a > b$ 确定后的剩下的一半可能作为根的左子节点，$a < b$ 确定后剩下的另一半可能作为根的右子节点，每次确定某两个元素的大小后，都会剩下一半可能，作为左右子节点加入到决策树中，因此该决策树是一棵叶子节点总数为 $n!$ 的二叉树，决策步数为到达排序状态的序列的叶子节点的深度。 对于深度为 $d$ (根节点在 0 深度处)的二叉树，其叶子结点数量至多为 $2^d$，当二叉树为 **完美二叉树 (perfect binary tree)** 时达到最大值。于是对应地，具有 $n$ 个叶子节点的二叉树，深度至少为 $⌈logn⌉$ ，当二叉树为 **完全二叉树 (complete binary tree)** 时深度最浅。 于是具有 $n!$ 个叶子节点的二叉树的深度至少为 $⌈log(n!))⌉$，这个深度就是通过比较得到排序结果的最少比较次数。根据 [Stirling公式](https://en.wikipedia.org/wiki/Stirling%27s_approximation) 得到如下结果，因此，通过比较来排序的算法的时间复杂度 **下界** 为 $O(nlogn)$。 $$ \sum_{i=2}^{n} \log i=\log (n !)=n \log n-n \log e+\Theta(\log n) $$  <!--  --> <br /> ## 实战应用 与元素大小相关的问题基本上都可以用排序来解决，例如从数组中取出前 $k$ 个大(小)，第 $k$ 个大(小)数等。也有通过适当的排序过程获取某些信息的问题，例如求逆序数等。 等。 | 题目 | 难度 | 题解 | | ------------------------------------------------------------ | ---- | ------------------------------------------------------------ | | [912. 排序数组](https://leetcode.cn/problems/sort-an-array/) | 中等 | 直球题 | | [462. 最少移动次数使数组元素相等 II](https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/) | 中等 | [题解](https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/solution/yukiyama-er-fen-cha-zhao-by-yukiyama-jg0d/) | | [剑指 Offer 51. 数组中的逆序对](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/) | 困难 | [题解](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/by-yukiyama-elnl/) | | [539. 最小时间差](https://leetcode.cn/problems/minimum-time-difference/) | 中等 | [题解](https://leetcode.cn/problems/minimum-time-difference/solution/-by-yukiyama-togv/) | | [215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/) | 中等 | [题解](https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/by-yukiyama-agaa/) | | ==== 持续更新中 ==== | | | 🐮🐮🐮 牛啊朋友，你竟然真的看到这里了。 *** 【本文更新日志】 [2022-07-28] - 根据 [@welliem](/u/welliem/) (welliem) 的提醒，改进「计数排序」$countArr$ 变形部分的代码，相比原实现更快。感谢 welliem 🙏 [2022-07-19] - 更正了关于基数排序稳定性的说法，更正前文章声称基数排序稳定性取决于计数排序的稳定性，这句话是错误的。因为在基数排序中，对每一位的排序，无论采用计数排序还是非计数排序，该排序都必须稳定，否则所有位排完后，排序可能错误。详情请看「基数排序」-「算法描述」中的相关说明。该错误由 [@vclip](/u/vclip/) (白) 发现，感谢白总！🙏 [2022-06-05] - 「实战应用」新增「[215. 数组中的第K个最大元素](https://leetcode.cn/problems/kth-largest-element-in-an-array/)」和「[539. 最小时间差](https://leetcode.cn/problems/minimum-time-difference/)」题解。 [2022-05-21] - 更正部分swap相关代码。修改前若swap采用「方法二」的加减法交换或「方法三」的异或交换，将可能出现同元素交换情况，这将导致该元素变为0，详情请看「[三种交换方法](#三种交换方法)」一节。 [2022-05-20] 更新 - 在「方法二」和「方法三」的 $swap$ 实现代码中增加一行 $if$ ，以避免 $i == j$ 时的错误。此修改由 [@lcfgrn](/u/lcfgrn/) (道哥刷题) 指出，非常感谢！🙏 实际上应保证排序过程中不出现自己与自己交换的情形出现，这样就无需 $if$ 语句了。 - 重写「希尔排序」之「Shell增量」代码，~~并指出网上流传甚广的一种错误写法~~ （是作者搞错了，详情请见「希尔排序」一节）。新增「Knuth增量」、「Hibbard增量」版本的希尔排序代码。 [2022-05-19] 更新 - 更新「希尔排序」实现代码的一处错误。原代码缺少一行 $for$ ，导致对于同一增量，只有一组序列执行了简单插入排序。现已修正，该错误由 [@lxy-hub987](/u/lxy-hub987/) (啦啦啦) 同学指出，非常感谢！🎉 详情见评论区相关讨论。 - 新增462题解。今天的每日一题 [462. 最少移动次数使数组元素相等 II](https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/) 刚好有一种基于快速排序的做法，且在所有解法中平均时间复杂度最低，为 $O(n)$。顺手把这个解法的题解更新到「实战应用」中了，欢迎各位阅读指正👏。实际上连着两天的每日一题，也都有二分查找的解法，相应的二分查找解法我更新到了 [二分查找从入门到入睡](https://leetcode.cn/circle/discuss/ooxfo8/) 的「实战应用」中，也一并欢迎各位阅读指正👏。 树状数组从入门到下车 红黑树从入门到看开