排序算法这个系列我断断续续写了好几年，从最基础的冒泡、插入，到归并、快排，每一篇都在反复打磨。今天聊的是希尔排序，一个很多人学过但未必真正吃透的算法。它在教科书里通常被安排在插入排序之后、快速排序之前，篇幅不大，存在感也不算强，但如果你认真拆解它的设计思路，会发现这里面藏着非常精妙的工程智慧。希尔排序的核心价值在于：它用非常朴素的手段，把插入排序从O(n²)的最坏时间复杂度拉到了接近O(n^1.3)甚至更好的水平。它不需要额外的内存空间，代码量也不大，却在中等规模数据的排序场景中表现相当能打。这篇文章适合已经掌握基本排序算法、想进一步理解算法优化思路的开发者，也适合正在准备技术面试、需要把排序算法从头到尾梳理一遍的朋友。我会从设计动机讲起，把增量序列的选择、代码实现细节、性能分析、常见踩坑点全部拆开讲透，让你看完就能自己写出一个靠谱的希尔排序，并且知道每一行代码为什么这么写。

1. 希尔排序到底在解决什么问题

1.1 从插入排序的痛点说起

要理解希尔排序，必须先理解插入排序的局限性。插入排序的逻辑很直观：把数组分成"已排序"和"未排序"两部分，每次从未排序部分取第一个元素，在已排序部分从后往前找位置插进去。这个过程就像你打扑克牌时整理手牌，摸到一张新牌，从右往左比大小，找到合适的位置塞进去。

插入排序有两个很重要的特性。第一，如果数组本身已经基本有序，插入排序的效率极高，接近O(n)，因为每次插入只需要比较很少的次数。第二，如果一个元素距离它最终应该在的位置很远，插入排序需要一步一步地把它挪过去，每次只能移动一个位置，效率非常低。

举个例子。假设数组是[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]，完全逆序。插入排序处理第一个元素9时不用动，处理8时要跟9比较并交换，处理7时要跟9和8比较并交换……处理最后一个0时，要跟前面9个元素逐一比较并交换。总的比较和移动次数大约是n²/2的量级。问题出在哪里？出在每次移动只能跨越一个位置。如果能让元素一次移动一大段距离，快速接近它的最终位置，那整体效率就会大幅提升。

希尔排序正是基于这个思路：先用较大的步长把元素粗略地放到大致正确的位置上，让数组变得"基本有序"，然后再用较小的步长精细调整，最后用步长为1的插入排序收尾。由于前面的预处理已经让数组接近有序，最后的插入排序代价很低。

1.2 增量序列：希尔排序的灵魂

希尔排序的核心概念叫增量（gap），也叫步长。它的工作方式是：对于某个增量gap，把数组分成gap个子序列，每个子序列由所有下标间隔为gap的元素组成，然后对每个子序列分别做插入排序。做完一轮后，缩小gap，重复上述过程，直到gap缩小到1，做最后一次标准插入排序。

我举个具体的例子来演示。假设数组为[49, 38, 65, 97, 76, 13, 27, 49]，长度n=8。第一轮取gap=4，那么子序列分别是：

• 子序列1：下标0, 4 → 元素49, 76
• 子序列2：下标1, 5 → 元素38, 13
• 子序列3：下标2, 6 → 元素65, 27
• 子序列4：下标3, 7 → 元素97, 49

对每个子序列做插入排序后，数组变成[49, 13, 27, 49, 76, 38, 65, 97]。你可以看到，较小的元素13、27已经往前移动了很大的距离，这就是大步长的威力。

第二轮取gap=2，子序列为：

• 子序列1：下标0, 2, 4, 6 → 元素49, 27, 76, 65
• 子序列2：下标1, 3, 5, 7 → 元素13, 49, 38, 97

分别排序后数组变成[27, 13, 49, 38, 65, 49, 76, 97]。此时数组已经相当有序了。

第三轮取gap=1，对整个数组做一次标准插入排序。由于前面两轮已经把数组整理得比较有序，这一轮只需要少量的比较和移动就能完成。最终结果[13, 27, 38, 49, 49, 65, 76, 97]。

增量序列的选择直接决定了希尔排序的性能上限。这也是希尔排序最有趣的研究方向之一。不同的增量序列会导致完全不同的时间复杂度：

原始希尔增量（每次折半）在最坏情况下仍然是O(n²)，比如对于某些精心构造的输入序列，效率并不理想。Knuth序列和Sedgewick序列在实践中表现更好，尤其是Sedgewick序列，在中等规模数据上经常能跑出接近O(n^1.3)的性能。

1.3 为什么说希尔排序是"不稳定"的

稳定性是排序算法的一个重要属性。所谓稳定，是指如果数组中有两个相等的元素，排序后它们的相对顺序保持不变。比如[3a, 1, 3b, 2]，排序后如果3a仍然在3b前面，这个算法就是稳定的；如果3a和3b的相对顺序可能被打乱，那就是不稳定的。

希尔排序是不稳定的，原因在于它进行了多次跨步长的分组插入排序。在某个子序列中，两个相等的元素可能被分到不同的组里，各自进行插入排序后，它们的相对位置就可能发生变化。即使在同一组内，插入排序本身是稳定的，但不同轮次之间的交叉移动会破坏稳定性。

我举个具体的例子。数组[3a, 1, 3b, 2]，取gap=2：

• 子序列1：下标0, 2 → 元素3a, 3b
• 子序列2：下标1, 3 → 元素1, 2

对子序列1排序，3a和3b相等，不需要交换，顺序保持。对子序列2排序，1和2不需要交换。数组变成[3a, 1, 3b, 2]。

然后取gap=1，对整个数组做插入排序。处理1时，1和3a比较，1小于3a，交换，数组变成[1, 3a, 3b, 2]。处理3b时，3b和3a相等，不交换。处理2时，2和3b比较，2小于3b，交换；2和3a比较，2小于3a，交换。最终数组变成[1, 2, 3a, 3b]。这个例子里3a和3b的顺序恰好没变，但换一个输入就可能变了。

比如数组[3a, 5, 1, 3b, 2, 4]，取gap=3：

• 子序列1：下标0, 3 → 元素3a, 3b
• 子序列2：下标1, 4 → 元素5, 2
• 子序列3：下标2, 5 → 元素1, 4

对子序列2排序后，2和5交换，数组变成[3a, 2, 1, 3b, 5, 4]。对子序列3排序后，数组变成[3a, 2, 1, 3b, 5, 4]。然后gap=1做插入排序，最终可能得到[1, 2, 3b, 3a, 4, 5]，3a和3b的顺序就反了。

所以如果你需要一个稳定的排序算法，希尔排序不适合。需要稳定排序时，应该选择归并排序或者基数排序。

2. C++实现细节全拆解

2.1 基础版本：原始希尔增量

先来看最基础的实现，用原始希尔增量（每次折半）：

void shellSortBasic(int arr[], int n) { // 外层循环控制增量，从n/2开始，每次折半 for (int gap = n / 2; gap > 0; gap /= 2) { // 对每个子序列进行插入排序 for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i; // 在子序列中从后往前找位置 while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }

这段代码看起来和插入排序很像，区别在于所有的1都变成了gap。插入排序是每次和前一个元素比较，希尔排序是每次和前gap个元素比较。当gap=1时，它就退化成了标准的插入排序。

我逐行解释一下关键逻辑。外层循环gap = n/2; gap > 0; gap /= 2控制增量序列。内层循环i = gap; i < n; i++遍历从gap开始的每个元素。对于每个元素，用temp暂存它的值，然后用j从当前位置往前以gap为步长扫描，把所有比temp大的元素往后挪gap个位置，最后把temp放到正确的位置。

这里有个容易搞混的地方：arr[j] = arr[j - gap]是赋值而不是交换。这是插入排序的标准写法，比每次交换少了一半的写操作。因为temp已经保存了当前元素的值，所以可以直接覆盖，最后再把temp填回去。

2.2 改进版本：Knuth增量序列

原始希尔增量在某些输入下会退化到O(n²)。一个经典的坏情况是数组长度为2的幂次，且所有奇数位置的元素都大于偶数位置的元素。这种情况下，前几轮增量排序几乎不做任何有效工作，最后一轮gap=1时才真正开始排序，效率退化成插入排序。

Knuth提出的增量序列1, 4, 13, 40, 121, ...，递推公式为h = 3*h + 1，能有效避免这个问题。实现时需要先计算出不超过n的最大增量，然后从大到小使用：

void shellSortKnuth(int arr[], int n) { // 计算初始增量 int gap = 1; while (gap < n / 3) { gap = gap * 3 + 1; } // 从大到小使用增量 for (; gap > 0; gap = (gap - 1) / 3) { for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i; while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }

注意增量的递减方式：gap = (gap - 1) / 3。因为递推公式是h_{k+1} = 3*h_k + 1，反过来就是h_k = (h_{k+1} - 1) / 3。这个细节很容易写错，写成gap /= 3就会得到错误的增量序列。

2.3 高性能版本：Sedgewick增量序列

Sedgewick增量序列在实践中表现最好，它的生成规则稍微复杂一些，由两个子序列合并而成：1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, ...。生成公式为：

• 当k为偶数时：9 * 2^k - 9 * 2^(k/2) + 1
• 当k为奇数时：8 * 2^k - 6 * 2^((k+1)/2) + 1

实际编码时，通常直接预计算一个增量数组，或者用循环生成：

void shellSortSedgewick(int arr[], int n) { // 预计算Sedgewick增量序列 std::vector<int> gaps; int k = 0; while (true) { int gap; if (k % 2 == 0) { int half = k / 2; gap = 9 * (1 << k) - 9 * (1 << half) + 1; } else { int half = (k + 1) / 2; gap = 8 * (1 << k) - 6 * (1 << half) + 1; } if (gap >= n) break; gaps.push_back(gap); k++; } // 从大到小使用增量 for (int idx = gaps.size() - 1; idx >= 0; idx--) { int gap = gaps[idx]; for (int i = gap; i < n; i++) { int temp = arr[i]; int j = i; while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }

Sedgewick序列的最坏时间复杂度约为O(n^(4/3))，平均性能比Knuth序列更好。不过它的增量生成逻辑稍复杂，如果追求代码简洁，Knuth序列已经足够好了。

2.4 模板化实现：适配任意可比较类型

实际工程中，我们不会只排序int数组。把希尔排序写成模板函数，可以适配任意支持比较操作的类型：

template <typename T, typename Compare = std::less<T>> void shellSort(T arr[], int n, Compare comp = Compare()) { int gap = 1; while (gap < n / 3) { gap = gap * 3 + 1; } for (; gap > 0; gap = (gap - 1) / 3) { for (int i = gap; i < n; i++) { T temp = arr[i]; int j = i; while (j >= gap && comp(temp, arr[j - gap])) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } }

这里用comp(temp, arr[j - gap])替代了arr[j - gap] > temp，默认使用std::less<T>，也就是升序排列。如果想降序，传入std::greater<T>()即可。这种写法在C++标准库风格的代码中很常见，灵活性和可复用性都很好。

注意：模板版本中T temp = arr[i]要求类型T支持拷贝构造。对于大型对象，拷贝开销可能比较大。如果排序的是大对象，建议排序指针或索引，而不是直接排序对象本身。

3. 性能实测与增量序列对比

3.1 测试环境与方案设计

光讲理论不够直观，我实际跑了一组性能测试。测试环境是一台普通的开发机，编译器用g++，开启-O2优化。测试数据分为四组：

• 随机数组：元素在[0, 1000000]范围内随机生成
• 逆序数组：从n到1递减
• 基本有序数组：随机数组排序后再随机交换少量元素
• 大量重复元素数组：元素取值范围很小，比如[0, 10]

每组数据分别测试n=10000、n=100000、n=1000000三种规模，对比原始希尔增量、Knuth增量、Sedgewick增量三种方案，以及作为参照的标准插入排序和快速排序。

3.2 实测数据与分析

先看随机数组下的表现（单位：毫秒）：

从数据可以看出几个关键结论。第一，希尔排序相比插入排序有质的飞跃，n=100000时快了将近100倍。第二，增量序列的选择确实有影响，Sedgewick比原始希尔增量快了大约一倍。第三，希尔排序和快速排序相比仍有差距，但差距在可接受范围内，尤其是考虑到希尔排序不需要递归、不需要额外空间。

再看逆序数组下的表现：

逆序数组是插入排序的最坏情况，但希尔排序的表现反而比随机数组略差，这是因为逆序数组需要更多的元素移动。不过整体仍然远好于插入排序。

基本有序数组下的表现：

这个结果很有意思。对于基本有序的数组，插入排序反而比希尔排序快，因为插入排序在基本有序时接近O(n)，而希尔排序无论如何都要跑完所有增量轮次，有固定的开销。所以如果你的数据已经基本有序，直接用插入排序就好，没必要上希尔排序。

大量重复元素数组下的表现：

重复元素多的情况下，希尔排序的优势依然明显。这是因为重复元素减少了比较时的分支预测失败率，对希尔排序这种比较密集的算法有正面影响。

3.3 增量序列选择的实战建议

基于实测数据，我给出以下增量序列选择建议：

• 追求代码简洁：用Knuth序列，三行代码搞定增量生成，性能足够好
• 追求极致性能：用Sedgewick序列，比Knuth快15%到20%
• 教学演示：用原始希尔增量，逻辑最直观，容易理解
• 不确定场景：用Knuth序列，它在各种数据分布下表现都很稳定

还有一个容易被忽略的点：增量序列的最后一个值必须是1，否则数组不会被完全排序。有些增量序列（比如某些变体的Hibbard序列）生成的最后一个增量可能不是1，使用前必须手动补上gap=1这一轮。

4. 常见问题与排查技巧实录

4.1 死循环与越界问题

希尔排序最常见的bug是死循环和数组越界。我列几个典型场景：

场景一：增量递减写错导致死循环。比如写成gap = gap / 3，当gap=1时，1/3在整数除法下等于0，循环条件gap > 0不满足，循环结束，这没问题。但如果写成gap = (gap - 1) / 3，当gap=1时，(1-1)/3 = 0，也正常结束。真正会死循环的是gap = gap / 2配合gap >= 1这种写法，当gap=1时，1/2=0，0 >= 1不成立，也不会死循环。实际上C++整数除法下，只要递减方向正确，不太容易死循环。真正容易出问题的是增量递增阶段，比如while (gap < n / 3) gap = gap * 3 + 1;，如果n很大，gap可能溢出int范围。对于n接近INT_MAX的情况，需要用long long来存gap。

场景二：内层循环边界写错导致越界。标准写法是while (j >= gap && arr[j - gap] > temp)，两个条件缺一不可。如果漏掉j >= gap，当j小于gap时，j - gap为负数，访问arr[负数]就是越界。如果漏掉arr[j - gap] > temp，循环不会在正确位置停止，会把所有元素都挪一遍，虽然不会越界，但结果错误。

场景三：增量序列生成后忘记反转。用Sedgewick序列时，生成的gaps数组是从小到大的，使用时要倒序遍历。如果正序遍历，先做gap=1的完整插入排序，后面的增量就白做了，结果虽然正确但性能退化成插入排序。

4.2 性能异常的排查思路

如果你发现希尔排序跑得比预期慢很多，可以按以下顺序排查：

其中"数据已经基本有序"这个坑我踩过。有一次处理一个日志文件，日志本身是按时间戳递增的，只有少量乱序，我用希尔排序跑了一遍，发现比直接插入排序还慢。后来才反应过来，基本有序的数据用插入排序是最优的，希尔排序的多轮增量反而增加了额外开销。

4.3 与其他排序算法的选型对比

希尔排序在实际工程中应该什么时候用？我整理了一个选型对照表：

希尔排序最大的优势是原地排序加无递归。在嵌入式系统或者栈空间受限的环境中，快速排序的递归调用可能导致栈溢出，而归并排序需要O(n)的额外空间，这时候希尔排序就是一个很务实的选择。它的代码量也小，不需要复杂的递归逻辑，维护成本低。

4.4 一个容易忽略的优化：提前终止

标准希尔排序会跑完所有增量轮次，但有时候数组在某一轮之后已经完全有序了，后面的轮次其实是浪费。可以加一个检测：如果某一轮中没有发生任何交换，说明数组已经有序，可以提前退出。

template <typename T> void shellSortWithEarlyExit(T arr[], int n) { int gap = 1; while (gap < n / 3) { gap = gap * 3 + 1; } for (; gap > 0; gap = (gap - 1) / 3) { bool swapped = false; for (int i = gap; i < n; i++) { T temp = arr[i]; int j = i; while (j >= gap && arr[j - gap] > temp) { arr[j] = arr[j - gap]; j -= gap; swapped = true; } arr[j] = temp; } if (!swapped) break; } }

这个优化在基本有序的数据上效果明显，但在随机数据上几乎不会触发，因为随机数据在最后一轮gap=1之前很难完全有序。所以这个优化是"有更好，没有也行"的类型，加不加取决于你的数据特征。

提示：提前终止的判定条件是"没有发生元素移动"，而不是"没有发生比较"。因为插入排序中，即使元素不需要移动，也可能进行了比较。只有完全没有移动，才说明数组已经有序。

5. 从希尔排序延伸出的算法思维

5.1 分治思想的朴素体现

希尔排序本质上是一种朴素的分治。它没有像归并排序那样把数组一分为二递归处理，而是通过增量序列把数组分成多个逻辑子序列，分别排序后再合并。这种"先粗后细"的策略在很多工程问题中都有对应。

比如数据库索引的B+树，也是先通过高层节点快速定位大致范围，再在底层节点精细查找。又比如网络路由的分层设计，先按大区域路由，再按小区域路由。希尔排序把这个思路用在了排序上：先用大步长快速消除大的逆序对，再用小步长处理细节。

理解了这个思路，你就能明白为什么希尔排序的增量序列如此重要。增量序列本质上是在平衡"粗调"和"细调"的工作量。如果大步长太少，粗调不充分，最后的细调负担重；如果大步长太多，粗调过度，浪费在无关紧要的细节上。好的增量序列能让每一轮的工作量相对均衡。

5.2 时间复杂度分析的直觉理解

希尔排序的时间复杂度分析是算法领域的一个经典难题，至今没有完全解决。对于原始希尔增量，最坏情况是O(n²)；对于Knuth序列，最坏是O(n^1.5)；对于Sedgewick序列，最坏是O(n^(4/3))。这些结论的证明都相当复杂，但我们可以从直觉上理解为什么增量序列会影响复杂度。

关键概念叫逆序对。一个数组的逆序对数量等于把它变成有序数组所需的最少相邻交换次数。插入排序每次相邻交换消除一个逆序对，所以插入排序的时间复杂度正比于逆序对数量。希尔排序的每次跨步长移动可以一次性消除多个逆序对，所以效率更高。

好的增量序列能让每一轮消除的逆序对数量尽可能多，同时保证不同轮次之间不产生新的逆序对。Knuth序列和Sedgewick序列的设计目标就是让每一轮的增量之间保持某种数学关系，使得总的比较次数最小化。

5.3 希尔排序的适用边界

希尔排序不是万能的，它有明确的适用边界。我总结了几条判断标准：

• 数据量在几百到几万之间，希尔排序是一个很好的选择
• 数据量超过十万，快速排序或归并排序通常更优
• 数据量小于五十，插入排序的常数优势更明显
• 需要稳定排序时，不能用希尔排序
• 内存极度受限且不能用递归时，希尔排序是最佳选择之一
• 数据已经基本有序时，插入排序比希尔排序更快

这些边界不是绝对的，实际选择时还要考虑具体的数据分布、硬件环境和代码维护成本。我的经验是，对于通用场景，Knuth增量序列的希尔排序是一个"不会出错"的选择，性能稳定，代码简单，没有明显的短板。

5.4 一个实际项目中的使用案例

我之前在一个数据处理模块中用过希尔排序。那个模块需要在一个资源受限的嵌入式设备上对传感器采集的数据进行排序，数据量大约在5000到20000条之间，设备的内存只有几百KB，栈空间也很有限。快速排序的递归深度在最坏情况下可能达到n，栈空间不够；归并排序需要额外的O(n)空间，内存不够；插入排序在数据量上万时太慢。

最终选了Knuth增量序列的希尔排序，代码不到20行，没有递归，没有额外内存分配，实测在20000条数据上耗时约8毫秒，完全满足实时性要求。这个案例说明，希尔排序在特定约束下确实有不可替代的价值。

6. 完整可运行的代码与测试

6.1 完整实现

把前面讲的内容整合成一个完整的、可直接编译运行的C++程序：

#include <iostream> #include <vector> #include <chrono> #include <random> #include <algorithm> // Knuth增量序列希尔排序 template <typename T, typename Compare = std::less<T>> void shellSort(T arr[], int n, Compare comp = Compare()) { int gap = 1; while (gap < n / 3) { gap = gap * 3 + 1; } for (; gap > 0; gap = (gap - 1) / 3) { for (int i = gap; i < n; i++) { T temp = arr[i]; int j = i; while (j >= gap && comp(temp, arr[j - gap])) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = temp; } } } // 验证数组是否有序 template <typename T> bool isSorted(const T arr[], int n) { for (int i = 1; i < n; i++) { if (arr[i - 1] > arr[i]) return false; } return true; } int main() { // 正确性测试 std::vector<int> testCases[] = { {}, {1}, {2, 1}, {5, 4, 3, 2, 1}, {1, 2, 3, 4, 5}, {3, 1, 4, 1, 5, 9, 2, 6, 5, 3}, {49, 38, 65, 97, 76, 13, 27, 49} }; for (auto& tc : testCases) { std::vector<int> copy = tc; shellSort(copy.data(), copy.size()); std::cout << "排序" << (isSorted(copy.data(), copy.size()) ? "正确" : "错误") << "，元素个数：" << copy.size() << std::endl; } // 性能测试 const int N = 100000; std::vector<int> data(N); std::mt19937 gen(42); std::uniform_int_distribution<int> dist(0, 1000000); for (int i = 0; i < N; i++) data[i] = dist(gen); auto start = std::chrono::high_resolution_clock::now(); shellSort(data.data(), N); auto end = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start); std::cout << "排序" << N << "个随机整数耗时：" << duration.count() << "毫秒" << std::endl; std::cout << "结果验证：" << (isSorted(data.data(), N) ? "有序" : "无序") << std::endl; return 0; }

编译命令：

g++ -O2 -std=c++17 -o shell_sort shell_sort.cpp

6.2 测试用例设计思路

测试用例覆盖了以下几种边界情况：

• 空数组：验证n=0时不会崩溃
• 单元素数组：验证n=1时不会越界
• 两元素逆序：验证最小规模的交换逻辑
• 完全逆序：验证最坏情况下的正确性
• 完全有序：验证最好情况下的正确性
• 有重复元素：验证相等元素的处理
• 经典教学案例：验证与教科书结果一致

这七类用例基本覆盖了希尔排序可能遇到的所有边界。每次修改代码后跑一遍，能快速发现回归问题。

6.3 性能测试的注意事项

做性能测试时有几个坑要注意。第一，测试数据要提前生成好，不要在计时循环里生成数据，否则会把数据生成的时间也算进去。第二，要多跑几次取平均值，单次测量受系统调度影响很大。第三，要开启编译器优化，不开-O2的测试结果没有参考价值。第四，测试数据规模要足够大，小规模数据的测量误差可能比实际差异还大。

还有一个细节：std::chrono::high_resolution_clock在不同平台上的精度不同，Windows上可能只有毫秒级精度，Linux上可以到纳秒级。如果测试数据规模较小，建议用std::chrono::steady_clock或者直接用CPU周期计数器。

我个人在实际项目中使用希尔排序的体会是，它最适合那些"数据量中等、内存紧张、不想引入递归"的场景。Knuth增量序列是我的默认选择，代码简单，性能稳定，几乎不会踩坑。如果你正在学习排序算法，建议把希尔排序的代码亲手敲一遍，把增量序列换成不同的方案跑一跑，观察性能变化，这个过程比看十篇文章都管用。后续如果想进一步深入，可以研究一下Sedgewick序列的数学推导，或者看看Pratt序列如何在O(n log²n)时间内完成排序，这些内容会让你对算法设计的精妙之处有更深的感受。