第11章 排序算法

11.1 排序算法基础

常见的排序算法非常的多，有：冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、希尔排序、计数排序、桶排序、基数排序、内省排序，平滑排序等等。常见的排序算法是前6种，其中前3种排序是基础。桶排序的效率较高，但应用较少，多数编程语言的底层采用归并排序与快速排序。

11.1.1 排序的基本概念

排序（Sorting）是一个十分常见的功能，在平时生活中也是随处可见的。比如生活中：图书馆的书按编号从小到大摆放，考试成绩单按分数从高到低排列，手机里的照片按时间先后显示——这些都是排序。

在计算机科学中，排序更具体地指：给定一个包含 n 个元素的序列，将其中的元素按照某个关键字（key）的非递减或非递增顺序重新排列，输出一个有序序列。例如把 [5, 2, 8, 1, 9] 变成 [1, 2, 5, 8, 9]（升序）或 [9, 8, 5, 2, 1]（降序），这个过程就是排序。在实际开发中，直接调用编程语言对应的API就可以实现排序，但这些API也是基于排序算法实现的（多数采用归并与快排），我们所要学习。

所以排序，简单来说，就是将一组数据按照某种特定的顺序（规则）重新排列的过程。我们刚才提到的算法（冒泡、选择、归并、快排等）就是实现这个过程的不同策略，它们在时间复杂度、空间复杂度和稳定性上各有取舍。

11.1.2 人与计算机排序的差异

现在有个需求，需要对一组身高不等的10个人进行排序。我们要如何排序？

如果是由人来排序，事情会非常简单，因为我们只需要扫一眼就能看出来谁最高谁最低，然后让最低或者最高的站在前面，其他人依次后移，按照这样的方法，依次类推就可以了，在我高中排队跑操时，就有这种根据身高排列的需求。

人排序有个特点，可以统筹全局，直接获取到最高或者最低的结果。哪怕人挤人 密度太高，通常情况下也有足够的空间，可以稍微走开点，让人眼可以分清面前的内容，所以不需要考虑空间的问题。但人排序也有缺点，首先是容易出错，当数据量庞大时，就很难排序出来，其次在精度上也不足（相差一厘米不到，很难快速分辨）。

计算机排序与人类排序有着本质的不同。人在面对少量数据时，可以一眼扫过去，迅速判断出顺序；人与人之间也无需固定的空间，互相推推嚷嚷就能腾出位置、调换前后。但计算机做不到这些——它无法通览全部数据，在同一时间只能对两个元素进行比较，必须依赖严密的逻辑和特定的指令，一步一步地解决问题。在人类看来很简单的事情，对计算机而言却需要遵循一套明确的规则才能完成。

然而，计算机也有它独特的优势。它虽然"笨拙"，却无比忠实——只要你写出了正确的指令，它就能不知疲倦地重复执行无数次而不出差错，也无需担心数据量的大小。想象一下，让人去排序一万甚至十万条数据，恐怕早已眼花缭乱，而这对计算机来说不过是多花一点时间罢了。

11.1.3 排序算法的分类标准

所以排序算法就是研究如何对一个集合进行高效排序的算法，也是在面试时非常常见的面试题型之一。

维基百科对排序算法的解释是：在计算机科学与数学中，一个排序算法（英语：Sorting algorithm）是一种能将一串资料依照特定排序方式排列的算法。虽然排序算法从名称来看非常容易理解，但是从计算机科学发展以来，在此问题上已经有大量的研究。

由于排序非常重要而且可能非常耗时，所以它已经成为一个计算机科学中广泛研究的课题，而且人们已经研究出一套成熟的方案来实现排序。因此，幸运的是我们并不需要是发明某种排序算法，而是站在巨人的肩膀上即可。

在计算机科学所使用的众多排序算法通常依以下4点标准分类：

（1）计算的时间复杂度：使用大O表示法，也可以实际测试消耗的时间；

（2）内存使用量（甚至是其他电脑资源）：比如外部排序，使用磁盘来存储排序的数据；

（3）稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序；

（4）排序的方法：插入、交换、选择、合并等等；

大O表示法在前文有学习过，即通过数量级来测试性能。

内存使用量，指的是排序过程中需要占用多少额外的存储空间。有些算法只需要在原数组上操作，几乎不需要额外内存，这类叫"原地排序"（如快速排序）。但当数据量大到内存放不下时，就必须借助磁盘等外部存储来辅助完成排序，这就是所谓的"外部排序"。所以内存使用量直接决定了一个算法能不能在资源有限的环境下运行。

稳定性，说的是排序后，两个值相同的元素是否还保持着原来的先后顺序。举个例子，有两个学生都考了90分，排序前小明排在小红前面，排序后如果小明仍然在小红前面，这个排序就是稳定的；如果顺序颠倒了，就是不稳定的。这在只看分数时似乎无所谓，但如果你需要先按分数排、再按姓名排这种多条件排序场景，稳定性就很重要了。PS：稳定性不是说偶尔会出错的概率。

排序的方法，指的是算法在排序时所采用的基本策略。比如"交换"是通过不断交换两个元素的位置来实现排序（冒泡排序就是典型）；"插入"是把元素逐个插到已排好序的部分中去；"选择"是每次从剩余元素中选出最小（或最大）的放到正确位置；"合并"则是先把数据拆分成小块，分别排好序后再合并起来。

因为排序算法的种类非常多，而没有任何一种排序算法是在所有场景下都最优的。分类的目的，本质上是为了帮助我们在面对不同的实际需求时，能够快速选择最合适的算法。打个比方，就像我们要出行，可以选择步行、骑车、开车或坐飞机。如果只是去楼下便利店，步行就够了；但如果要跨城市出差，大概率会选高铁或飞机。选择的依据是什么？无非就是距离、时间、费用这几个维度。排序算法的分类逻辑也是一样的——我们从时间复杂度、内存占用、稳定性、排序方法这几个维度去衡量，就能清楚每种算法的优势和局限，从而在具体场景中做出合理的选择。

比如，数据量小且几乎有序时，插入排序简单高效；数据量大时，快速排序的平均性能优异；如果要求排序结果稳定（相等元素保持原有顺序），归并排序就是更好的选择；而当内存有限、数据存在磁盘上时，就需要考虑外部排序的方案。

所以分类不是为了分类本身，而是为了建立一套选型的框架，让我们面对具体问题时不必盲目尝试，而能有据可依地做出判断。这是一套经典的方法论框架，用优化好的逻辑来决策。

11.2 简单排序算法

在维基百科列出的排序算法有二三十种，但多数排序算法在平时是难以遇到的，包括一些语言的底层也很少会使用到。一般情况下，在刚入门时，会先掌握冒泡排序、选择排序以及插入排序，这三种排序算法相对好理解且更简单一些。接着我们会学习归并排序和快速排序，很多语言的底层都有这两种排序的影子。堆排序则是可以在不使用额外空间的情况下对数据进行高效排序。

在历史上，希尔排序有重要地位，是第一个将排序的时间复杂度拉到到O(n²)以下。那时候的人们认为是无法突破的，直到希尔排序的出现，在该转折点之后，更快的排序算法如春笋般喷涌而出，但希尔排序如今使用较少。排序算法的时间复杂度如图11-1所示。

图11-1 排序算法的时间复杂度

因为接下来要学习多种排序算法，所以本章在讲解思路时，采用以下统一学习顺序：

（1）介绍某种排序算法：如果该排序算法有一些历史背景或者故事，我们也会一起介绍。

（2）分析某种排序算法的思路步骤。

（3）某种排序算法的图解。

（4）排序算法的代码实现过程（一步步手写实现）。

（5）排序算法的复杂度分析。

（6）排序算法的小结。

我们要学习非常多种类的排序算法，那么我们可以先从一个最简单的排序算法入手：冒泡排序。

11.2.1 冒泡排序

冒泡排序（Bubble Sort）是一种简单直观的排序算法。它的基本思路是：重复地遍历待排序序列，依次比较相邻的两个元素，如果它们的顺序不对就交换位置。每完成一趟遍历，当前未排序部分中的最大值就会像气泡一样"浮"到序列的末尾，随后将其从下一轮比较中排除。如此反复，直到整个序列有序为止——这也正是"冒泡排序"这一名称的由来。

冒泡排序的思路流程如下：

（1）从第一个元素开始，逐一比较相邻元素的大小。

（2）如果前一个元素比后一个元素大，则交换位置。

（3）在第一轮比较结束后，最大的元素被移动到了最后一个位置。

（4）在下一轮比较中，不再考虑最后一个位置的元素，重复上述操作。

（5）每轮比较结束后，需要排序的元素数量减一，直到没有需要排序的元素。

（6）排序结束。

以上流程会一直循环，直到所有元素都有序排列为止。每一次循环都是可以知晓需要循环几次的，因此采用for循环而不是while循环。冒泡排序的流程图如图11-2所示。

图11-2 冒泡排序流程图

假设有一组数据（5个）需要冒泡排序，每一趟通过相邻比较与交换，将当前未排序部分中的最大值"推"到末尾，从而使有序区从右向左逐步扩大，直到整个序列有序。即每轮比较会筛出一个目标数组中的最大数据到最后，在下一轮筛选中会将上一轮的"最大数据"排除在外，重新筛选出目标数组的最大数据，直到筛选数组中只剩下一个数据为止（即最小的数据）。

这么做，意味着一共需要n-1轮筛选（只剩下最后一个数据无需筛选，因此减1），每一轮参与筛选的数据量逐轮递减（第 i 轮比较 n-i 对相邻元素），因为每轮结束后都会有一个已归位的元素被排除出下次筛选的范围。。PS：n是数组内的数据个数。

图11-3 冒泡排序-交换图解

在编写代码前，我们先想清楚两个设计思路：

（1）排序算法需要返回排序后的数组吗？

（2）排序算法是否要直接对传入的数组改变？

两个设计思路指向的是同一个问题，是否要对原有数据进行改变？这是都可以的，例如在JavaScript的Array系列API方法中，Array.prototype.splice()和Array.prototype.toSpliced()两个实例方法。这两个方法的作用其实是一样的，但确是不同的两种方法理念，在MDN文档里将其称为复制方法和修改方法，有些方法不会修改调用该方法的现有数组，而是返回一个新的数组。它们通过首先构造一个新数组，然后填充元素来实现。复制始终是浅层次的——该方法从不复制一开始创建的数组之外的任何内容。

非修改方法（即复制方法）往往在API命名中会以to作为开头，但这不是一定的，而是后续逐渐形成的规范。

复制方法的通用性会更强，且不改变原数组符合纯函数的思想（不引起副作用），因此我们采用该方式，那么在TypeScript中，就需要对函数的返回形式做出要求，初始化函数格式如下：

▼
typescript
复制代码
// 冒泡函数初始化
export default function bubbleSort(arr: number[]): number[] {
  return arr
}

测试方式如下：

▼
typescript
复制代码
// 冒泡函数的常见测试用例
const nums = [20,6,4,2,24]
const newNums = bubbleSort(nums)
console.log(newNums)

接下来编写冒泡排序的代码逻辑，冒泡排序有两个重点：

（1）交换数据：可以采用临时变量C作为中间站来实现变量A与B的交换，亦或者用解构的方式（代码采用该方式）。

（2）筛选规则：共需要两层循环，外层循环次数为n-1，内层循环为n-1-i（i为筛选出去的数据个数），数组下标从0开始，如果循环次数是数组长度，那么会越界，因此要么length-1，要么采用Array.prototype.at()。

筛选规则是冒泡排序的专属标志，但交换不是，因此交换数据可以抽象成一个函数方法。

▼
typescript
复制代码
// 交换方法
export function swap(arr: number[], i: number, j: number) {
  // 交换方式一: 使用临时变量
  // const temp = arr[i]
  // arr[i] = arr[j]
  // arr[j] = temp
  // 交换方式二: 使用解构赋值
  [arr[i], arr[j]] = [arr[j], arr[i]]
}

在获取循环次数时，我们通常不用length表示，而是用变量n来存储。因为n是number的开头缩写，同时也可以代表大O表示法中的n，即数据的数量，会比length更易于理解。因此在业务中，会用length，而在算法中用n。

▼
typescript
复制代码
export default function bubbleSort(arr: number[]): number[] {
  const n = arr.length

  // 外层for循环: 0~n-1
  for (let i = 0; i < n; i++) {
    // 内层循环是找到最大值
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        swapped = true
      }
    }
  }

  return arr
}

如果我们每次写完一个排序算法，就需要针对性的写一份测试用例，那这个过程是有点繁琐的。那么面对这种情况，既可以使用现成的第三方测试工具库，也可以直接让AI给出完整的测试用例，自己封装起来使用。

现在编写一个testSort()函数工具，用于帮助我们测试排序算法。传入排序算法函数，打印排序前的原数组和排序后的新数组。

▼
typescript
复制代码
// 编写一个工具, 直接帮助测试排序算法
type SortAlgoFn = (arr: number[]) => number[]
export function testSort(sortFn: SortAlgoFn) {
  // 1.随机一个长度为10的数组(数组中存放多个数字)
  const nums = Array.from({ length: 10 }, () => {
    return Math.floor(Math.random() * 200)
  })

  // 2.使用排序对数组进行排序
  console.log("排序前的原数组:", nums)
  const newNums = sortFn(nums)
  console.log("排序后的新数组:", newNums)
}

但排序算法依旧需要人去主动判别是否正确，可以令testSort()函数工具返回布尔值或者以打印的形式输出排序后的算法是否有正确的顺序。封装isSorted()方法，通过判断数组内的数据是否满足由小到大的排列顺序。

▼
typescript
复制代码
export function isSorted(arr: number[]): boolean {
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) return false
  }
  return true
}

// 编写一个工具, 直接帮助测试排序算法
type SortAlgoFn = (arr: number[]) => number[]
export function testSort(sortFn: SortAlgoFn) {
  // 1.随机一个长度为10的数组(数组中存放多个数字)
  const nums = Array.from({ length: 10 }, () => {
    return Math.floor(Math.random() * 200)
  })

  // 2.使用排序对数组进行排序
  console.log("排序前的原数组:", nums)
  const newNums = sortFn(nums)
  console.log("排序后的新数组:", newNums)
  console.log("是否排序后有正确的顺序?", isSorted(newNums))
}

测试用例也可以使用第三方库"hy-algokit"中的compareSort()测试方法，有两个参数：

（1）参数1：数组，可同时传入多个需要测试的排序算法。

（2）参数2：数据量，用于测试的具体数量的随机数据。

输出模板：使用xxx算法，排序xxx个元素，消耗时间为xxx毫秒。当完成所有排序算法的编写后，可以一次性运行起来，因此后续小节不一一展示运行效果。我们会在最后总结的时候，将排序算法一次性运行起来比对。

冒泡排序可以做一个优化，假如在一轮循环中，没有发生任何一次实际的交换，则说明后续的排序是已经归类好了，后续的循环没有实际意义（因为已经排序好了）。那么就可以直接跳出循环，结束排序。利用标记变量swapped来判断当前循环是否有发生交换，若有则继续循环，若无则跳出循环结束排序。

▼
typescript
复制代码
export default function bubbleSort(arr: number[]): number[] {
  const n = arr.length

  // 外层for循环: 0~n-1
  for (let i = 0; i < n; i++) {
    let swapped = false
    // 内层循环是找到最大值
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        swapped = true
      }
    }
    if (!swapped) break
  }
  return arr
}

在冒泡排序中，每次比较两个相邻的元素，并交换他们的位置，如果左边的元素比右边的元素大，则交换它们的位置。这样的比较和交换的过程可以用一个循环实现。冒泡排序的时间复杂度有3种情况：

（1）最好情况：O(n)。即待排序的序列已经是有序的，此时仅需遍历一遍序列，不需要进行交换操作。

（2）最坏情况：O(n²)。即待排序的序列是逆序的，需要进行n-1轮排序，每一轮中需要进行n-i-1次比较和交换操作。

（3）平均情况：O(n²)。即待排序的序列是随机排列的，每一对元素的比较和交换都有1/2的概率发生，因此需要进行n-1轮排序，每一轮中需要进行n-i-1次比较和交换操作。PS：和最坏情况在一个数量级内，但平均情况的实际交换次数比最坏情况的要少。

由此可见，冒泡排序的时间复杂度主要取决于数据的初始顺序，最坏情况下时间复杂度是O(n²)，不适用于大规模数据的排序。所有产生平方甚至立方的时间复杂度，随着数据量的提升会指数型的拉爆负荷。假如数据量是2，那O(n²)是2倍负荷，可如果数据量是100万，那O(n²)是100万倍的负荷，100万的平方是一万亿，这是一个难以承受的数字。

所以冒泡排序适用于数据规模较小的情况，因为它的时间复杂度为O(n²)，对于大数据量的排序会变得很慢。同时，它的实现简单，代码实现也容易理解，适用于学习排序算法的初学者。但是，在实际的应用中，冒泡排序并不常用，因为它的效率较低。因此，在实际应用中，冒泡排序通常被更高效的排序算法代替，如快速排序、归并排序等。

11.2.2 选择排序

选择排序（Selection Sort）是一种简单且易于理解的排序算法。它的基本思想是：每一轮从当前未排序的部分中找出最小（或最大）的元素，将其与未排序部分的起始位置进行交换，从而使有序区从左向右逐步扩大，直到所有元素均排序完毕。选择排序的一个显著优点与数据移动有关——如果某个元素已经位于正确的最终位置，它不会被移动；而且每次交换只涉及一对元素，其中至少有一个会被直接移到最终位置上，因此对 n 个元素进行排序总共至多只需 n-1 次交换，时间复杂度属于O(n)。在所有完全依靠交换来移动元素的排序方法中，选择排序的交换次数是非常少的。凭借其实现简单、逻辑清晰的特点，选择排序也是学习排序算法时一个很好的入门选择。

选择排序符合人的直觉做法，例如在菜市场的胡萝卜堆里挑胡萝卜，人会先扫一眼，挑出认为最好的一根，再扫一遍再挑一根。每一遍选择都会挑一个自己认为胡罗卜堆里面最好的放到手里的袋子中，这种挑选的做法就算是一种选择排序。

选择排序的思路可以这样理解：将数组看作两个部分——左边是已排序区，右边是未排序区。初始时，已排序区为空，整个数组都属于未排序区。

每一轮操作做两件事：

（1）首先，从未排序区中找出最小值。具体做法是，先把未排序区的第一个元素暂时当作最小值，然后从第二个元素开始逐一与之比较，遇到更小的就更新标记，一轮扫描结束后就能确定真正的最小值。

（2）接着，将这个最小值与未排序区的第一个元素交换位置，交换完成后，该元素就归入了已排序区，已排序区向右扩展一位，未排序区相应缩短一位。

不断重复以上过程，每一轮都会从剩余的未排序区中"选"出一个最小值归位，直到未排序区只剩一个元素时，排序自然完成。选择排序的交换图解如图11-4所示。

图11-4 选择排序-交换图解

选择排序的函数方法初始化如下：

▼
typescript
复制代码
import { testSort } from "hy-algokit"

export default function selectionSort(arr: number[]): number[] {
  return arr
}
// 测试用例
testSort(selectionSort)

快速排序最多只需要n-1次交换，每次交换前需要获取未排序部分的最大（小）值，这里以最小值为例。有两个步骤需要遍历：

（1）循环获取未排序部分的最小值然后交换。选择最小值的前提是完整比对未排序部分才能确定。

（2）一共n-1次交换，因此循环n-1次。

然后与冒泡排序同思路的优化，只有数值不一致才交换。

▼
typescript
复制代码
export default function selectionSort(arr: number[]): number[] {
  const n = arr.length

  // 外层循环作用: 经过多少轮的找最小值
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i
    // 内层循环作用: 每次找到最小值
    for (let j = 1 + i; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }

    // 只有不相等时, 才需要进行交换操作
    if (i !== minIndex) {
      swap(arr, i, minIndex)
    }
  }

  return arr
}

选择排序的时间复杂度是比较容易分析的。时间复杂度有3种情况：

（1）最好情况时间复杂度：O(n²)。即待排序的数组本身就是有序的，在这种情况下，比较次数为 n(n-1)/2，交换次数为 0。

（2）最坏情况时间复杂度：O(n²)。即待排序的数组是倒序排列的，在这种情况下，比较次数为 n(n-1)/2，交换次数为 n-1。

（3）平均情况时间复杂度：O(n²)。即待排序的数组是随机排列的，在这种情况下，比较次数仍然是固定的 n(n-1)/2，交换次数小于 n-1（因为部分轮次中最小值已在正确位置，无需交换）。

选择排序虽然比较次数始终是 O(n²)，但交换次数最多只有 O(n)，而交换操作（涉及数据写入）的开销通常远大于比较操作（仅读取），因此在交换成本较高的场景下，选择排序的实际表现会优于同为 O(n²) 的冒泡排序。

11.2.3 插入排序

插入排序像我们打扑克时，摸到一张新牌，需要插入到手牌中的合适位置一样。我们会将新牌和手牌中已有的牌进行比较，找到一个合适的位置插入新牌。如果新牌比某张牌小，那么我们就把这张牌向右移动一位，为新牌腾出位置。一直比较直到找到一个合适的位置将新牌插入，这样就完成了一次插入操作。使用插入排序来排序手中的扑克牌如图11-5所示。

图11-5 使用插入排序来排序手中的扑克牌

与打牌类似，插入排序（Insertion sort）的实现方法是：首先假设第一个数据是已经排好序的，接着取出下一个数据，在已经排好序的数据中从后往前扫描，找到比它小的数的位置，将该位置之后的数整体后移一个单位，然后再将该数插入到该位置。不断重复上述操作，直到所有的数据都插入到已经排好序的数据中，排序完成。

插入排序的思路流程如下：

（1）首先，假设数组的第一个元素已经排好序了，因为它只有一个元素，所以可以认为是有序的。

（2）然后，从第二个元素开始，不断与前面的有序数组元素进行比较。

（3）如果当前元素小于前面的有序数组元素，则把当前元素插入到前面的合适位置。

（4）否则，继续与前面的有序数组元素进行比较。

（5）以此类推，直到整个数组都有序。

（6）循环步骤2~5，直到最后一个元素，完成排序。

插入排序图解如图11-6所示。

图11-6 插入排序图解

因此插入排序采用了与选择排序类似的思路，将面前的数据区分为已排序区和未排序区，但思路从交换转移到插入，核心操作方向恰好相反，区别如下：

（1）选择排序关注的是未排序区。 每一轮从未排序区中"选"出最小值，放到已排序区的末尾。它解决的问题是"下一个该放谁"——先确定元素，位置是固定的。

（2）插入排序关注的是已排序区。 每一轮取出未排序区的第一个元素，在已排序区中找到它应该待的位置，然后"插"进去。它解决的问题是"这个元素该放哪"——元素是确定的，位置需要寻找。

这个区别也带来了一个重要的性能差异：选择排序每一轮都必须完整扫描未排序区才能确定最小值，所以比较次数是固定的 n(n-1)/2，无论数据是否有序；而插入排序在已排序区中从后往前扫描时，一旦找到合适的位置就可以停下来，所以如果数据本身接近有序，比较次数会大幅减少，最好情况下只需 n-1 次比较，时间复杂度降为 O(n)。

插入排序的代码初始化如下：

▼
typescript
复制代码
import { testSort } from "hy-algokit";

export default function insertionSort(arr: number[]): number[] {
  return arr
}

testSort(insertionSort)

插入排序的循环有两层：

（1）外层：固定的n-1次，即除了第一张默认有序牌，其余未排序区插入到有序区的次数。

（2）内层：循环次数是不确定的，所谓"不确定"指的是内层循环的比较次数。插入排序在每一轮中，会把当前元素从后往前与已排序区的元素逐个比较，但一旦找到合适的位置就会停下来，不需要把已排序区全部扫完。所以每一轮内层循环执行多少次，完全取决于数据的排列情况。

内层情况举个例子，假设已排序区是 [2, 5, 8]，现在要插入 1 和 7：

插入 7 时，从后往前比较：7 < 8？是，继续；7 < 5？不是，停下，插入到 5 后面。只比较了 2 次。

插入 1 时，从后往前比较：1 < 8？是；1 < 5？是；1 < 2？是，已经到头了，插入到最前面。比较了 3 次。

所以准确的说法应该是：外层循环固定 n-1 轮，但每轮内层循环的比较次数不确定，取决于当前元素在已排序区中的插入位置。正因如此，插入排序的总比较次数才会随数据分布变化——最好情况 O(n)，最坏情况 O(n²)。因此内层循环在不确定次数的情况下使用while循环。

▼
typescript
复制代码
import { testSort } from "hy-algokit";
export default function insertionSort(arr: number[]): number[] {
  const n = arr.length

  for (let i = 1; i < n; i++) { // 外层循环从未排序区开始 
    // 内层循环
    const newNum = arr[i]
    let j = i - 1
    while (arr[j] > newNum && j >= 0) {
      arr[j + 1] = arr[j]
      j--
    }
    arr[j + 1] = newNum
  }

  return arr
}
testSort(insertionSort)

插入排序的插入并不是真的像打牌那样"挤进去"，而是通过一个更巧妙的方式实现的：先把待插入元素取出暂存，然后从右往左逐个把比它大的元素右移一位（相当于逐步腾出一个空位），当遇到不比它大的元素时停下，最后把暂存的值放进那个腾出来的空位。

那么插入排序的时间复杂度的3种情况如下：

（1）最好情况： O(n)。如果待排序数组已经排好序，那么每个元素只需要比较一次就可以确定它的位置，因此比较的次数为 n-1，移动的次数为 0。所以最好情况下，插入排序的时间复杂度为线性级别，即 O(n)。

（2）最坏情况： O(n²)。如果待排序数组是倒序排列的，那么每个元素都需要比较和移动 i 次，其中 i 是元素在数组中的位置。因此比较的次数为 n(n-1)/2，移动的次数也为 n(n-1)/2。所以最坏情况下，插入排序的时间复杂度为平方级别，即O(n²)。

（3）平均情况：O(n²)。对于一个随机排列的数组，插入排序的时间复杂度也为平方级别，即O(n²)。

总而言之，如果数组部分有序，插入排序可以比冒泡排序和选择排序更快。但是如果数组完全逆序，则插入排序的时间复杂度比较高，不如快速排序或归并排序。毕竟插入排序的最坏情况下，有较多的元素右移行为，元素的移动比查询更消耗性能。

插入排序是一种简单直观的排序算法，它的基本思想就是将待排序数组分为已排序部分和未排序部分，然后将未排序部分的每个元素插入到已排序部分的合适位置。插入排序的时间复杂度为 O(n²)，虽然这个复杂度比较高，但是插入排序的实现非常简单，而且在某些情况下性能表现也很好，比如，如果待排序数组的大部分元素已经排好序，那么插入排序的性能就会比较优秀。总之，插入排序虽然没有快速排序和归并排序等高级排序算法的复杂性和高效性，但是它的实现非常简单，而且在一些特定的场景下表现也很好。

普通插入排序在已排序区中从右往左逐个比较来寻找插入位置，这是可以优化的，我们可以用二分查找来定位，将每一轮的查找次数从 O(n) 降低到 O(log n)。但需要注意一个关键问题：查找变快了，移动并没有变快。找到插入位置之后，仍然需要把该位置之后的所有元素逐个右移一位来腾出空间，这一步依然是 O(n)。所以二分插入排序的总体时间复杂度仍然是 O(n²)，只是减少了比较次数，移动次数不变。所以二分查找优化在数据量较大时确实能带来一定的性能提升，但瓶颈在移动操作上，无法突破 O(n²) 的上限。如果想要真正突破这个瓶颈，就需要换用归并排序或快速排序这类 O(n log n) 的算法了。

11.3 高效排序算法

在学习11.2.3小节的插入排序的最后，我们对插入排序的性能进行一定程度的思考，意识到插入排序在移动操作上无法突破O(n²)的上限，而这是制约插入排序进入高效排序算法的原因。接下来我们会学习归并排序或者快速排序是如何解决这一问题的。

11.3.1 归并排序

归并排序（Merge Sort）是一种基于"分治法"思想的经典排序算法，最早由现代计算机之父约翰·冯·诺伊曼（John von Neumann）于1945年提出。其基本思路是：先将待排序数组递归地拆分成越来越小的子数组，直到每个子数组只剩一个元素（自然有序），然后再将相邻的子数组两两合并（merge），在合并过程中完成排序，最终得到一个整体有序的数组。简单来说，就是"先拆到不能再拆，再合并的过程中排好序"。归并排序的时间复杂度稳定在 O(n log n)，无论最好、最坏还是平均情况都不会退化，因此在实际应用中被广泛使用，许多编程语言的底层排序实现都采用了归并排序或其变体。

归并排序是一个拆分重组的过程，我们以数组[30，10，8，20]为例，首先是拆分过程：

（1）[30，10]，[8，20]。

（2）[30]，[10]，[8]，[20]。

在拆分到每个子数组只剩一个元素后，完成拆分，进入重组阶段，每一次重组都会比较两个子数组的顺序进行排序：

（1）[10，30]，[8，20]。

（2）[8，10，20，30]。

但合并的时候，8如果接到10的前面，那20不是需要另外插入到10和30的中间吗？合并操作是怎么做的？这是个很好的问题。合并操作并不是把一个数组的元素"插入"到另一个数组中去，而是创建一个新的空数组，然后用双指针从两个子数组中逐个"挑"元素放进去。

以合并 [10, 30] 和 [8, 20] 为例，具体过程如下：

准备一个空的结果数组 []，指针 i 指向左数组的第一个元素，指针 j 指向右数组的第一个元素。

第一步：比较 i 指向的 10 和 j 指向的 8，8 更小，取 8 放入结果，j 后移。 结果：[8]，左 [10, 30] i→10，右 [_, 20] j→20

第二步：比较 i 指向的 10 和 j 指向的 20，10 更小，取 10 放入结果，i 后移。 结果：[8, 10]，左 [_, 30] i→30，右 [_, 20] j→20

第三步：比较 i 指向的 30 和 j 指向的 20，20 更小，取 20 放入结果，j 后移。 结果：[8, 10, 20]，左 [_, 30] i→30，右边已经取完

第四步：右数组已经没有元素了，直接把左数组剩余的 30 放入结果。 结果：[8, 10, 20, 30]

所以关键在于：合并不是在原数组上插入或移动，而是两个有序数组像拉链一样交替取元素，按顺序填入一个全新的数组。正因为两个子数组各自已经有序，所以每次只需要比较两个指针头部的元素就够了，整个过程只需扫描一遍，非常高效。这也是为什么归并排序需要额外的 O(n) 空间——就是用来存放这个新数组的。

归并排序的实现是建立在一个已知的条件下：合并两个已经有序的数组是非常容易且高效的。具体来说，合并两个有序数组时，只需要两个指针分别指向两个数组的头部，每次比较两个指针所指的元素，取较小的那个放入结果数组，然后该指针后移。整个过程只需要扫描一遍，时间复杂度是 O(n)。

但问题是，我们一开始拿到的是一个无序数组，怎么才能得到"有序的子数组"呢？归并排序的巧妙之处就在于：把数组一直拆，拆到每个子数组只有一个元素——一个元素天然就是有序的。这样就获得了最初的"有序子数组"，然后就可以利用上面那个高效的合并操作，从底向上逐层合并回去。

所以归并排序的精髓可以概括为：把"排序一个无序数组"这个困难问题，转化为"反复合并有序数组"这个简单问题。 拆分本身不做任何排序工作，真正的排序全部发生在合并阶段。而分治递归保证了每次合并时，两个子数组一定已经是有序的，从而让合并操作始终保持高效。

因此，归并排序是一种基于分治思想的排序算法，其基本思路可以分为三个步骤：

（1）步骤一：分解（Divide）：归并排序使用递归算法来实现分解过程，具体实现中可以分为以下几个步骤：

• 如果待排序数组长度为1，认为这个数组已经有序，直接返回。
• 将待排序数组分成两个长度相等的子数组，分别对这两个子数组进行递归排序。
• 将两个排好序的子数组合并成一个有序数组，返回这个有序数组。

（2）步骤二：合并（Merge）：合并过程中，需要比较每个子数组的元素并将它们有序地合并成一个新的数组：

• 可以使用两个指针 i 和 j 分别指向两个子数组的开头，比较它们的元素大小，并将小的元素插入到新的有序数组中。
• 如果其中一个子数组已经遍历完，就将另一个子数组的剩余部分直接插入到新的有序数组中。
• 最后返回这个有序数组。

（3）步骤三：归并排序的递归终止条件：

• 归并排序使用递归算法来实现分解过程，当子数组的长度为1时，认为这个子数组已经有序，递归结束。

总体来看，归并排序的基本思路是分治法，分成子问题分别解决，然后将子问题的解合并成整体的解。归并排序图解如图11-7所示。归并排序的过程分为"拆分"和"合并"两个阶段。每次拆分都把数组一分为二，所以一个长度为 n 的数组需要拆 log₂n 层才能拆到单个元素。比如 8 个元素：第一层拆成 2 组各 4 个，第二层拆成 4 组各 2 个，第三层拆成 8 组各 1 个，一共 log₂8 = 3 层。

而合并阶段也是 log₂n 层，每一层合并时，所有元素都会被比较和移动恰好一次，所以每一层的工作量是 O(n)。

总的时间复杂度 = 层数 × 每层工作量 = O(log n) × O(n) = O(n log n)。

对于归并排序来说，是不需要扫描的，只需要不断的拆分然后合并就行了。

图11-7 归并排序图解

当然了，朋友们，这其实很有意思。这让我想起来在小学阶段算数的日子，那时候多个二位数三位数相加相减，我会把所有加的划分到一堆，相减的划分到一堆，然后按大小排列起来，两两相加，再两两相加，最后把算出来相加的减去相减的。

例如：268+84-352+154-691+894+548=？

84+154+268+548+894-（352+691）=238+816+894-1043=238+1710-1043=200+1700+48-43-1000=905

除了通过合并，我还通过从个位数开始相加减的拆分，对应了归并排序"拆到单个元素"的思想，因此这道题的难度对我而言，降低到个位数的运算，属于可以轻松心算出来的程度，当熟练之后的速度也很快。

个位数开始相加减的拆分例如：84+154=80+150+4+4=50+30+150+8=238。这和归并排序是同种思想，都源于数学中的一些技巧。

归并排序的方法初始化如下：

▼
typescript
复制代码
import { testSort } from "hy-algokit"

export default function mergeSort(arr: number[]): number[] {
  // 1.分解(divide): 对数组进行分解(分解成两个小数组)
  // 2.合并(merge): 将两个子数组进行合并(双指针)
  return arr
}

testSort(mergeSort)

对数组分解，需要获取数组数据的中间位置，将其一分为二。如果直接获取数组长度除2，一旦数组是奇数，除2就会出现小数位，因此需要取整，取整后的数字归左半部分还是右半部分随意，都可以正常工作（推荐向下取整，更便于配合数组索引。 数组索引从0开始，向下取整恰好让左半部分的长度小于或等于右半部分）。类似左侧五个右侧六个，并不会影响合并。

以长度为 5 的数组为例（取整后的数字归右半部分）：

向下取整：mid = Math.floor(5 / 2) = 2，左半部分是索引 01（2 个元素），右半部分是索引 24（3 个元素）。

向上取整：mid = Math.ceil(5 / 2) = 3，左半部分是索引 02（3 个元素），右半部分是索引 34（2 个元素）。

切割之后，拿着左右两半部分继续去切割寻找中间位置，直到数组长度为1。

▼
typescript
复制代码
import { testSort } from "hy-algokit"

export default function mergeSort(arr: number[]): number[] {
  // 递归切割的结束条件：当数组长度为1甚至小于1。
  if (arr.length <= 1) return arr
  // 1.分解(divide): 对数组进行分解(分解成两个小数组)
  // 8 / 2 = 4
  // 1.1. 切割数组
  const mid = Math.floor(arr.length / 2)
  const leftArr = arr.slice(0, mid)
  const rightArr = arr.slice(mid)

  // 1.2.递归的切割leftArr和rightArr
  const newLeftArr = mergeSort(leftArr)
  const newRightArr = mergeSort(rightArr)
  
  // 2.合并(merge): 将两个子数组进行合并(双指针)
  
  return arr
}

testSort(mergeSort)

在1.2的newLeftArr和newRightArr递归调用结束之前，代码不会继续往下走。当拆分到数组内只剩下一个元素，中断递归，返回的arr会从递归切割的位置继续往下走，即合并部分流程，当合并部分结束时，我们需要将两个子数组合并的结果返回，返回的结果会继续从上一个1.2递归的切割开始继续合并，直到递归收束，一层层的释放递归所占用的运行空间，最终合并为一个完整的有序数组完整返回，递归结束。

从堆栈结构来看，分解阶段在不断压栈，直到数组长度为1开始逐层弹栈，每弹一层就执行一次合并，合并的结果作为返回值交给上一层继续合并，最终栈完全释放，得到整个有序数组。

合并阶段需要定义i与j两个指针和一个新的空数组newArr。两个指针指向相邻的两个子数组的初始下标0，开始两个指针指向的数据比较，指针指向数据小的push到newArr数组中，然后发生push行为的子数组的指针移向下一位，继续两个子数组内的数据比较，直到两个子数组的内部数据都push到newArr数组为止，合并结束，合并的结果作为返回值交给上一层继续合并。

指针指向多次移动，在代码层面可以直接视为遍历，而不固定遍历次数则使用while循环。循环结束的限制条件为：两个指针都指向子数组的末端。且由于当两个指针都指向子数组的末端，则最后一个数据元素还未push到newArr数组中，需要检查左右两部分的数组是否还有剩余，将最后的剩余push到newArr数组中。

▼
typescript
复制代码
import { testSort } from "hy-algokit"

export default function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr

  // 1.分解(divide): 对数组进行分解(分解成两个小数组)
  // 8 / 2 = 4
  // 1.1. 切割数组
  const mid = Math.floor(arr.length / 2)
  const leftArr = arr.slice(0, mid)
  const rightArr = arr.slice(mid)

  // 1.2.递归的切割leftArr和rightArr
  const newLeftArr = mergeSort(leftArr)
  const newRightArr = mergeSort(rightArr)

  // 2.合并(merge): 将两个子数组进行合并(双指针)
  // 2.1.定义双指针
  const newArr: number[] = []
  let i = 0
  let j = 0
  while (i < newLeftArr.length && j < newRightArr.length) {
    if (newLeftArr[i] <= newRightArr[j]) {
      newArr.push(newLeftArr[i])
      i++
    } else {
      newArr.push(newRightArr[j])
      j++
    }
  }

  // 2.2.判断是否某一个数组中还有剩余的元素
  // 循环完左边还有剩余
  if (i < newLeftArr.length) {
    newArr.push(...newLeftArr.slice(i))
  }
  // 循环完右边还有剩余
  if (j < newRightArr.length) {
    newArr.push(...newRightArr.slice(j))
  }

  // 3.将合并后的数组返回
  return newArr
}

testSort(mergeSort)

假设数组长度为 n，需要进行 logn 次归并操作，每次归并操作需要 O(n) 的时间复杂度，因此，归并排序的时间复杂度为 O(nlogn)。归并排序的时间复杂度的3种情况如下：

（1）最好情况： O(log n)。待排序数组已经是有序的了，那么每个子数组都只需要合并一次，即只需要进行一次归并操作。

（2）最坏情况： O(nlogn)。待排序数组是逆序的，那么每个子数组都需要进行多次合并。

（3）平均情况： O(nlogn)。假设待排序数组中任意两个元素都是等概率出现的。

无论情况如何，归并排序的分解与合并操作都是不可避免的，但性能依旧非常高效。它的核心思想是分治，即将待排序数组分成若干个子数组，分别对这些子数组进行排序，最后将排好序的子数组合并成一个有序数组。归并排序的时间复杂度为 O(nlogn)，并且在最好、最坏和平均情况下都可以达到这个时间复杂度。

在编程中，可预测的结果是非常重要的，在保持高效的性能之下，有着极强的稳定性，在任何情况都保持同样的性能效率。因此大多数编程语言的底层都会广泛应用，不会因使用场景的泛用而出现一些极端问题。

11.3.2 快速排序

快速排序（Quicksort），也被称为"划分交换排序"（partition-exchange sort），由计算机科学家 Tony Hoare（东尼·霍尔）于1960年代初期发明，最初出现在一份 ALGOL 60 的手稿中，目的是为了提升稿件的可读性。后来，Tony Hoare 将这一算法正式命名为 Quicksort。由于其思想精巧，快速排序在计算机科学中得到了广泛应用，但"快速"并不意味着它在所有场景下都是最快的排序算法——其实际性能取决于输入数据的分布、数组长度等多种因素。

快速排序在大部分情况下，都是最好最快的，而这距离归并排序的出现已经有15年之久，每一次的超越都是非常不容易的。

快速排序（Quick Sort）是一种基于分治思想的排序算法，其基本思路是通过选择一个基准元素（pivot），将数组划分为左右两部分——左部分的元素都小于或等于基准元素，右部分的元素都大于基准元素——然后对左右两部分递归地进行快速排序，最终使整个数组有序。作为一种原地排序算法，快速排序不需要额外的数组空间，平均时间复杂度为 O(nlogn)，虽然最坏情况下会退化为 O(n²)，但这种情况出现的概率极低，因此它通常被认为是一种非常高效的排序算法。快速排序的逻辑看似复杂，但只要理解了分治的基本思路，实现起来并不困难。

快速排序与归并排序都是对目标数组递归式的分解成两部分，直到最小单位为止（数组长度为1）。但快速排序在将目标数组分解到最小单位时，就已经有序，这点与归并排序不同。并且快速排序将目标数组分解成两部分并不是等分。

假设我们选择数组最后一个元素作为基准元素（pivot），对数组 [10, 28, 18, 9, 23, 11, 33, 26] 进行快速排序。

首先，选取 26 作为 pivot，然后从左到右遍历数组，将小于或等于 26 的元素放到左边，大于 26 的元素放到右边。遍历结束后，再将 pivot 放到左右两部分的中间位置，数组变为 [10, 18, 9, 23, 11, 26, 33, 28]。此时 26 已经处于最终的正确位置，它左边的元素都比它小，右边的元素都比它大。

接下来，对左半部分 [10, 18, 9, 23, 11] 和右半部分 [33, 28] 分别递归执行同样的操作。以左半部分为例，选取 11 作为 pivot，经过同样的划分过程后，数组变为 [10, 9, 11, 18, 23]，11 归位。然后继续对 11 左边的 [10, 9] 和右边的 [18, 23] 递归处理——[10, 9] 选取 9 为 pivot，划分后变为 [9, 10]；[18, 23] 选取 23 为 pivot，划分后保持 [18, 23]。右半部分 [33, 28] 的处理也是同理，选取 28 为 pivot，划分后变为 [28, 33]。

每一轮划分都会让一个 pivot 元素落到它最终的正确位置上，同时递归不断缩小待排序的子数组规模。当子数组长度缩减为 1 时，递归终止并开始逐层回溯，所有子数组的排序结果自然合在一起，最终得到完整的有序数组 [9, 10, 11, 18, 23, 26, 28, 33]。

在快速排序中，有3个关键问题需要解决：

（1）pivot 的选择。为什么选最后一个元素（例如以上案例选择的26）？选第一个、中间的、或者随机选一个行不行？不同的选择方式对性能有什么影响？什么情况下会导致最坏时间复杂度 O(n²)？

（2）划分过程的细节。遍历数组时，元素具体是怎么交换的？指针是怎么移动的？pivot 最后是怎么放到正确位置的？

（3）"原地排序"的理解。既然快速排序是原地排序，不需要额外数组，那元素是怎么在同一个数组里完成左右分区的？和归并排序需要新数组有什么本质区别？

关于 pivot 的选择

选择最后一个元素作为 pivot 只是一种最简单、最直观的实现方式，便于编码和理解，但并不是唯一的选择。实际上，选第一个元素、中间元素、甚至随机选一个元素都是完全可行的。不同的选择方式不会改变快速排序的基本逻辑，但会影响划分的均匀程度，进而影响性能。理想情况下，pivot 恰好是数组的中位数，这样每次划分都能将数组均匀地分成两半，递归深度为 logn，时间复杂度为 O(nlogn)。但如果每次选到的 pivot 都是当前子数组的最大值或最小值——比如对一个已经有序的数组选取第一个或最后一个元素作为 pivot——那么每次划分都会极度不均匀，一边有 n-1 个元素，另一边为空，递归深度退化为 n，时间复杂度就会恶化为 O(n²)。正因如此，实践中常采用"三数取中"（取首、中、尾三个元素的中间值）或随机选择 pivot 的策略，来尽量避免最坏情况的出现。

关于划分过程的细节

以 Lomuto 分区方案为例，我们用指针 i 来标记"小于等于 pivot 的区域"的右边界，初始值为数组起始位置的前一位。然后用指针 j 从左到右遍历数组（不包含 pivot 本身），每当 j 指向的元素小于或等于 pivot 时，就将 i 右移一位，然后交换 i 和 j 位置上的元素。这个操作的本质是：把每一个发现的"小元素"依次甩到数组左侧，而大于 pivot 的元素则自然地被留在右侧。当 j 遍历完整个数组后，i 的右边一位就是 pivot 应该存放的最终位置，此时将 pivot 与该位置上的元素交换，pivot 便归位了——它左边的元素全都小于或等于它，右边的元素全都大于它。等到划分到最小单位时，每个数据的左侧全都小于或等于它，右边的元素全都大于它，那这就整体符合有序排列。

关于"原地排序"的理解

从划分过程可以看出，快速排序自始至终都是在原数组上通过元素交换来完成分区的，不需要创建新的数组来存放左右两部分的数据。每一层递归只是通过传递左右边界的索引来缩小操作范围，始终操作的是同一块内存空间。这就是"原地排序"的含义。而归并排序的思路则不同：它在合并两个有序子数组时，需要一个额外的临时数组来存放合并结果，因为两个子数组的元素要按顺序交替取出，无法在原数组上直接完成而不覆盖未处理的数据。这就是两者在空间使用上的本质区别——快速排序靠交换就地完成划分，归并排序靠额外空间才能完成合并。

快速排序思路可以分解成以下8个步骤（Hoare 分区方案）：

（1）选择一个基准元素，通常选择第一个或最后一个元素作为基准元素。

（2）定义两个指针 i 和 j，分别指向数组的左右两端。

（3）从右侧开始，向左移动 j 指针，直到找到一个小于或等于基准元素的值。

（4）从左侧开始，向右移动 i 指针，直到找到一个大于或等于基准元素的值。

（5）如果 i 指针小于或等于 j 指针，交换 i 和 j 指针所指向的元素。

（6）重复步骤 3-5，直到 i 指针大于 j 指针，这时，我们将基准元素与 j 指针所指向的元素交换位置，将基准元素放到中间位置。

（7）将数组分为两部分，左侧部分包含小于或等于基准元素的元素，右侧部分包含大于基准元素的元素。

（8）对左右两部分分别进行递归调用快速排序，直到左右两部分只剩下一个元素。

我们准备在代码编写的思路是Hoare 分区方案，不是 Lomuto。两者的核心区别在于指针的运动方式。Lomuto 方案只有一个指针 j 从左往右单向遍历，另一个指针 i 只是被动地标记左侧小元素区域的边界——也就是我们之前一直在讨论的那种方式。而这里描述的是两个指针从数组两端相向而行：j 从右往左找小元素，i 从左往右找大元素，找到之后交换，直到两个指针相遇。这正是 Hoare 提出的原始分区方案。

两种方案最终的效果是一样的——都能将数组以 pivot 为界分成左小右大两部分——但实现细节不同。Hoare 方案在实际运行中交换次数通常更少，因为两个指针从两端同时逼近，能更快地找到"站错位置"的元素对并直接交换。

快速排序图解如图11-8所示。i指针从20开始往右，j指针从6开始往左。

图11-8 快速排序图解

快速排序的代码初始化如下（在原有基础上排序，无需创建新数组）：

▼
typescript
复制代码
// 快速排序函数初始化
export default function quickSort(arr: number[]): number[] {
  return arr
}

对于快速排序来说，最主要的部分在于分割。

由于快速排序一开始需要分割，左半部分需要递归分割，右半部分需要递归分割。已知的部分就有三处分割，而分割操作实际还包含了交换排序，有一定的代码量，因此分割操作最好创建partition()函数，将分割操作封装起来使用。

那么partition()函数要写在quickSort()函数内部还是外部呢？

写在外部，partition 作为一个独立的工具函数，职责清晰，quickSort 负责递归框架，partition 负责分区逻辑，各司其职。这也是大多数教材和实际项目中更常见的写法，因为它更符合"单一职责"的原则，而且如果将来需要切换分区策略（比如从 Hoare 换成 Lomuto），只需要替换 partition 函数即可，不用动 quickSort 的代码。

写在内部，好处是 partition 可以直接访问 quickSort 的参数和局部变量，形成一个自包含的整体，外部不会看到也不需要知道 partition 的存在。对于我们目前的需求来说，无需进一步考虑快速排序的其余实现方式，不需要考虑更高的复用性。因此将partition写在quickSort内部会更方便。

▼
typescript
复制代码
import { swap, testSort } from "hy-algokit"

export default function quickSort(arr: number[]): number[] {
  partition(0, arr.length - 1)

  function partition(left: number, right: number) {
    if (left >= right) return

    // 1.找到基准元素(pivot轴心)
    const pivot = arr[right]

    // 2.双指针进行交换操作(左边都是比pivot小的数字, 右边都是比pivot大的数字)
    let i = left
    let j = right - 1

    while (i <= j) {
      // 找到一个比pivot大的元素
      while (arr[i] < pivot) {
        i++
      }
      // 找到一个比pivot小的元素
      while (arr[j] > pivot) {
        j--
      }

      // 说明我们已经找到了(比pivot大的元素i)和(比pivot小的j的元素)
      if (i <= j) {
        swap(arr, i, j)
        i++
        j--
      }
    }

    // 将pivot放在正确的位置
    swap(arr, i, right)

    // 左右继续划分区域(partition)
    partition(left, j) // 左边区域划分
    partition(i + 1, right)
  }

  return arr
}

testSort(quickSort)

partition()函数方法没办法自调用，因此在一开始时，左右指针分别从整个数组的首尾开始。然后以下4步：

（1）找到基准元素。

（2）使用Hoare分区方案的双指针交换。

（3）左右递归继续划分区域，并设置好终止条件（子数组长度为1或为空，在快速排序中则是左指针大于等于右指针，意思是一致的）。

（4）递归终止后逐层返回，释放调用栈空间，无需合并，因为数组在分区过程中已经被排好序了。

快速排序的时间复杂度主要取决于基准元素的选择、数组的划分、递归深度等因素。3种情况的时间复杂度如下：

（1）最好情况： O(nlogn)。当每次划分后，两部分的大小都相等，即基准元素恰好位于数组的中间位置，此时递归的深度为 O(log n)。每一层需要进行 n 次比较，因此最好情况下的时间复杂度为 O(nlogn)。

（2）最坏情况： O(n²)。当每次划分后，其中一部分为空，即基准元素是数组中的最大或最小值，此时递归的深度为 O(n)。每一层需要进行 n 次比较，因此最坏情况下的时间复杂度为 O(n²)。需要注意的是，采用三数取中法或随机选择基准元素可以有效避免最坏情况的发生。因此最坏情况的发生概率是很低的。

（3）平均情况： O(nlogn)。在平均情况下，每次划分后，两部分的大小大致相等，此时递归的深度为 O(log n)。每一层需要进行大约 n 次比较，因此平均情况下的时间复杂度为 O(nlogn)。

需要注意的是，快速排序是一个原地排序算法，不需要额外的数组空间。快速排序在多数情况下，比归并排序更快，快两倍以上。因为归并排序实际上要先划分再合并，而快速排序只有划分不需要合并，快速排序是直接在本身数组上操作，当递归结束时，快速排序只需要释放因递归操作所占据的堆栈空间。

11.3.3 堆排序

堆排序（Heap Sort）是一种基于比较的排序算法，其核心思想是利用二叉堆这种数据结构来维护有序序列。二叉堆是一种完全二叉树，每个节点都满足父节点比子节点大（或小）的条件；在堆排序中，我们使用最大堆，即保证每个节点都比它的子节点大。

排序过程是这样的：首先将待排序数组构建成一个最大堆，然后将堆顶元素（即最大值）与堆的最后一个元素交换，使最大值归位到数组末尾的正确位置；接着将堆的大小减一，对剩余元素重新调整为最大堆，再取出堆顶，如此反复，直到堆的大小为 1，整个数组便有序了。从本质上看，堆排序是选择排序的一种优化——选择排序每轮通过线性扫描找出最大（或最小）元素，而堆排序借助最大堆的结构特性，能够以 O(logn) 的代价完成每轮的最大值选取（堆的重新调整），从而将整体时间复杂度优化到 O(nlogn)，即选n轮，每轮重建堆的效率是logn。需要注意的是，学习堆排序之前最好先理解堆结构，这样会更有利于对整个排序过程的理解。

堆排序有两种思路：

（1）原地建堆。即一开始，将数组传给堆结构，对数组本身建堆，再完成后续操作，该做法无需消耗额外空间。

（2）建立新数组，将原数组复制一份给新数组，对新数组建堆。

如果想让空间复杂度更低，选择原地建堆，空间复杂度是O(1)，但如果原数组有在多个地方被引用的需求，就最好选择建立新数组，防止数组重复多次建堆对其余引用地方产生影响。

堆排序可以分成两大步骤：构建最大堆和排序。

构建最大堆：

• 遍历待排序序列，从最后一个非叶子节点开始，依次对每个节点进行调整。
• 假设当前节点的下标为 i，左子节点的下标为 2i+1，右子节点的下标为 2i+2，父节点的下标为 (i-1)/2。
• 对于每个节点 i，比较它和左右子节点的值，找出其中最大的值，并将其与节点 i 进行交换。
• 重复进行这个过程，直到节点 i 满足最大堆的性质。
• 依次对每个非叶子节点进行上述操作，直到根节点，这样我们就得到了一个最大堆。

排序：

• 将堆的根节点（也就是最大值）与堆的最后一个元素交换，这样最大值就被放在了正确的位置上。
• 将堆的大小减小一，并将剩余的元素重新构建成一个最大堆。
• 重复以上两个步骤，直到堆的大小为 1，这样我们就得到了一个有序的序列。

堆排序图解如图11-9所示。堆排序也是将数组分类为已排序和未排序两个区域，当构建最大堆时，位于数组首位的是最大值，将数组首位的最大值与数组末尾交换，并将交换后的数组末尾归类到已排序区域，交换结束后重新构建堆结构。当经历n-1次交换时，数组已完整排序。

图11-9 堆排序图解

堆排序的代码初始化如下：

▼
typescript
复制代码
import { testSort } from "hy-algokit";

export default function heapSort(arr: number[]): number[] {
  return arr
}

testSort(heapSort)

堆排序代码编写思路如下3步：

（1）原地建堆（构建最大堆）。

（2）将堆的根节点与堆的最后一个元素交换，堆的大小减一。

（3）重复步骤1和步骤2，直到堆的大小为1。

建堆操作在第9章是有详细学习的，可以将已写好的建堆方法运用到堆排序，但就当复习，在这里重新封装一遍。建堆方法需要3个参数：

（1）参数1：建堆的数组数据。

（2）参数2：建堆的长度。

（3）参数3：下滤位置。PS：堆结构的第一个非叶子节点，计算公式：n/2 - 1（正常来说n/2就够了，但数组下标从0开始，因此需要额外减一）。

由于堆排序的步骤二需要将堆排序不断的缩减，所以我们需要对传入建堆方法的数组尾部进行裁切。

▼
typescript
复制代码
/**
 * 下滤操作函数 
 * @param arr 在数组中进行下滤操作
 * @param n 下滤操作的范围
 * @param index 哪一个位置需要进行下滤操作
 */
function heapifyDown(arr: number[], n: number, index: number) {
  while (2 * index + 1 < n) {
    // 1.获取左右子节点的索引
    const leftChildIndex = 2 * index + 1
    const rightChildIndex = 2 * index + 2

    // 2.找出左右子节点较大的值
    let largerIndex = leftChildIndex
    if (rightChildIndex < n && arr[rightChildIndex] > arr[leftChildIndex]) {
      largerIndex = rightChildIndex
    }

    // 3.判断index位置的值比更大的子节点, 直接break
    if (arr[index] >= arr[largerIndex]) {
      break
    }

    // 4.和更大位置的进行交换操作
    swap(arr, index, largerIndex)
    index = largerIndex
  }
}

通过 heapifyDown() 的第二个参数（堆的有效长度 n），可以在排序过程中逐步缩小堆的范围；第三个参数用于指定需要执行下滤的起始位置（通常为根节点）。随着堆大小不断减小，最终当 n = 1 时，数组即完成有序排列。

在堆排序过程中，每一轮只需将堆顶元素（最大值）与当前堆的最后一个叶子节点交换。交换后，仅需对被移动到堆顶的位置执行一次下滤操作，即可重新恢复堆的有序结构，而无需对整个堆重新调整。

▼
typescript
复制代码
export default function heapSort(arr: number[]): number[] {
  // 1.获取数组的长度
  const n = arr.length

  // 2.对arr进行原地建堆
  // 2.1. 从第一个非叶子节点开始进行下滤操作
  const start = Math.floor((n / 2) - 1)
  for (let i = start; i >= 0; i--) {
    // 2.2. 进行下滤操作
    heapifyDown(arr, n, i)
  }

  // 3.对最大堆进行排序的操作
  for (let i = n - 1; i > 0; i--) {
    swap(arr, 0, i)
    heapifyDown(arr, i, 0)
  }

  return arr
}

堆排序的时间复杂度分析较为复杂，因为它既涉及到堆的建立过程，也涉及到排序过程。下面我们分别对这两个步骤的时间复杂度进行分析。

步骤一：堆的建立过程。堆的建立过程包括 n/2 次堆的向下调整操作，每次调整的时间复杂度为logn，因此它的时间复杂度为 O(nlogn)。

步骤二：排序过程。排序过程需要执行 n 次堆的删除最大值操作，每次操作都需要将堆的最后一个元素与堆顶元素交换，然后向下调整堆。每次向下调整操作的时间复杂度为O(log n)，因此整个排序过程的时间复杂度为O(n log n)。

综合起来，堆排序的时间复杂度为O(n log n)。需要注意的是，堆排序的空间复杂度为 O(1)，因为它只使用了常数个辅助变量来存储堆的信息。

测试堆排序的空间复杂度可以使用第三方库hy-algokit的measureStort方法，用于测试在10万数据甚至更多数据下，排序算法的消耗时间。堆排序具有时间复杂度为 O(n log n) 的优秀性能，并且由于它只使用了常数个辅助变量来存储堆的信息，因此空间复杂度为 O(1)。但是，由于堆排序的过程是不稳定的，即相同元素的相对位置可能会发生变化，因此在某些情况下可能会导致排序结果不符合要求。

PS：“相同元素的相对位置可能会发生变化”指的是：在排序前，如果两个元素的值相同，它们在数组中有先后顺序（谁在前、谁在后）；但经过堆排序后，这种先后关系可能被打乱，比如原本在前的元素被排到后面。之所以会这样，是因为堆排序过程中会频繁将堆顶元素与末尾元素直接交换，这种跨位置的交换不会保留原有顺序，只关注大小关系，从而导致相同元素的相对顺序不再保持一致。

总的来说，堆排序是一种高效的、通用的排序算法，它适用于各种类型的数据，并且可以应用于大规模数据的排序。

11.4 高级排序算法

所谓高级排序算法，是相对于冒泡、选择、插入这些简单排序而言的。简单排序的共同特点是思路直观、实现容易，但它们都只能做到"相邻元素之间的比较和交换"，每次操作只能将一个元素移动一小步，因此时间复杂度都停留在 O(N²)。而高级排序算法的本质突破在于：它们找到了某种方式，让元素能够"跨越式"地移动到更接近最终位置的地方，从而将时间复杂度降低到 O(N²) 以下。归并排序通过分治合并实现这一点，快速排序通过基准值分区实现这一点，堆排序通过堆结构的上浮下沉实现这一点。

希尔排序之所以被视为高级排序的门槛，是因为它是第一个跳出"逐个移动"思维框架的排序算法。在希尔排序之前，所有人都在"相邻比较"的范围内做优化，而希尔排序引入了"间隔"的概念——让相距较远的元素先进行比较和交换，使得一个较小的元素可以一次跨越多个位置到达靠前的区域。这个思想看似简单，却是从 O(N²) 迈向更低复杂度的关键一步。

从理解难度上来说，希尔排序也恰好处在一个过渡地带。它的底层操作依然是我们熟悉的插入排序，只是在外面包了一层间隔递减的逻辑，所以在认知上并不需要引入全新的概念，比如递归、分治或者树形结构。但它又比简单排序多了一层抽象——你需要理解"为什么先用大间隔粗排，再用小间隔精排，整体效率反而更高"，这背后涉及对数据局部有序性的利用，已经触及了高级算法的思维方式。

所以说，希尔排序是从简单排序通往高级排序的一座桥梁：它用最朴素的手段（插入排序）实现了最关键的突破（跨越式移动），既回顾了过去，又指向了未来。理解了希尔排序，再去学习归并排序的分治思想、快速排序的分区策略，就会顺畅很多。

11.4.1 希尔排序

在简单排序算法诞生后的很长一段时间里，无论是冒泡排序、选择排序还是插入排序，时间复杂度都停留在 O(N²) 的级别，学术界甚至弥漫着"排序算法不可能突破 O(N²)"的论调，就像人们曾坚信百米短跑不可能跑进10秒一样。直到1959年，Donald Shell 提出了希尔排序，这一局面才被打破。希尔排序的核心思想是先将数据按一定间隔分组，对每组进行插入排序，再逐步缩小间隔、重复这一过程，使数据逐渐趋于有序，最终完成排序。这种"先粗调、后精调"的策略让它的时间复杂度成功突破了 O(N²) 的壁垒，并且可以通过选择不同的步长序列进一步优化性能，为后续更高效的排序算法研究打开了大门。

先回顾一下插入排序的过程：排序进行到中途时，标记符左边的数据已经有序，右边的数据尚未排序。每一步操作是取出标记符指向的数据项存入临时变量，然后从该位置向左逐一比较，将较大的有序数据项依次右移一位，直到找到合适的插入位置，再将临时变量中的数据项放入。这个过程直观且易于理解，但隐藏着一个效率瓶颈。

设想这样一种情况：一个很小的数据项恰好位于数组的最右端——那里本应是较大数据项的位置。为了把它移动到左边的正确位置，所有中间的数据项都必须逐个向右挪动一位。每个步骤平均需要移动约 N/2 次，N 个元素累计下来就是 N²/2 次移动，这就是插入排序时间复杂度为 O(N²) 的根本原因。那么，如果有一种方法能让较小的数据项直接"跳跃"到靠左的位置，而不必逐一搬动所有中间元素，排序效率就能获得质的提升——这正是希尔排序要解决的问题。

以数组 [81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15] 为例来看希尔排序的具体过程。首先设定间隔为5，把相隔5个位置的元素分为一组进行插入排序，比如 (81, 35)、(94, 17)、(11, 95) 等组内各自排好序。经过这一轮排序，虽然整体还没有完全有序，但每个数字都朝着自己最终的正确位置迈进了一大步。接着将间隔缩小为3，再次分组排序，例如 (35, 28, 75, 58, 95)、(17, 12, 15, 81) 等组内再次调整，数据又离正确位置更近了一步。

当间隔最终缩小为1时，实际上就回到了标准的插入排序。但此时数组已经经过前几轮的"粗排"变得接近有序，每个元素距离自己的最终位置都很近，因此插入排序中需要移动的次数大大减少。这就是希尔排序的精妙之处——通过先大间隔、后小间隔的多轮分组排序，让数据逐步趋于有序，最后一轮插入排序只需做少量的微调即可完成，从而整体效率远高于直接使用插入排序。

图11-10 希尔排序图解

完整的希尔排序过程如下：

第一轮：间隔 = 5

按间隔5分组（相隔5个位置的元素为一组）：

• 组0（下标 0, 5, 10）：81, 35, 41 → 排序后：35, 41, 81
• 组1（下标 1, 6, 11）：94, 17, 75 → 排序后：17, 75, 94
• 组2（下标 2, 7, 12）：11, 95, 15 → 排序后：11, 15, 95
• 组3（下标 3, 8）：96, 28 → 排序后：28, 96
• 组4（下标 4, 9）：12, 58 → 排序后：12, 58

将排序结果放回原位，得到： [35, 17, 11, 28, 12, 41, 75, 15, 96, 58, 81, 94, 95]。

第二轮：间隔 = 3

按间隔3分组：

• 组0（下标 0, 3, 6, 9, 12）：35, 28, 75, 58, 95 → 排序后：28, 35, 58, 75, 95
• 组1（下标 1, 4, 7, 10）：17, 12, 15, 81 → 排序后：12, 15, 17, 81
• 组2（下标 2, 5, 8, 11）：11, 41, 96, 94 → 排序后：11, 41, 94, 96

将排序结果放回原位，得到： [28, 12, 11, 35, 15, 41, 58, 17, 94, 75, 81, 96, 95]。

第三轮：间隔 = 1（标准插入排序）

此时数组已接近有序，逐步插入如表11-1所示。

表11-1 希尔排序第三轮插入排序

步骤	取出元素	操作	数组状态
1	12	12 < 28，插入到28前	[12, 28, 11, 35, 15, 41, 58, 17, 94, 75, 81, 96, 95]
2	11	11 < 28, < 12，插入到最前	[11, 12, 28, 35, 15, 41, 58, 17, 94, 75, 81, 96, 95]
3	35	35 > 28，无需移动	[11, 12, 28, 35, 15, 41, 58, 17, 94, 75, 81, 96, 95]
4	15	插入到12和28之间	[11, 12, 15, 28, 35, 41, 58, 17, 94, 75, 81, 96, 95]
5	41	41 > 35，无需移动	[11, 12, 15, 28, 35, 41, 58, 17, 94, 75, 81, 96, 95]
6	58	58 > 41，无需移动	[11, 12, 15, 28, 35, 41, 58, 17, 94, 75, 81, 96, 95]
7	17	插入到15和28之间	[11, 12, 15, 17, 28, 35, 41, 58, 94, 75, 81, 96, 95]
8	94	94 > 58，无需移动	[11, 12, 15, 17, 28, 35, 41, 58, 94, 75, 81, 96, 95]
9	75	插入到58和94之间	[11, 12, 15, 17, 28, 35, 41, 58, 75, 94, 81, 96, 95]
10	81	插入到75和94之间	[11, 12, 15, 17, 28, 35, 41, 58, 75, 81, 94, 96, 95]
11	96	96 > 94，无需移动	[11, 12, 15, 17, 28, 35, 41, 58, 75, 81, 94, 96, 95]
12	95	插入到94和96之间	[11, 12, 15, 17, 28, 35, 41, 58, 75, 81, 94, 95, 96]

---

最终结果：[11, 12, 15, 17, 28, 35, 41, 58, 75, 81, 94, 95, 96]。可以看到，最后一轮插入排序中大量元素已经在正确位置附近，很多步骤都"无需移动"，移动次数远少于直接对原数组做插入排序的情况。

11.4.2 希尔排序的增量序列

希尔排序的核心思想可以概括为"分组、排序、缩小间隔、再排序"。具体来说，先选定一个增量序列 d1, d2, ..., dk（其中最后一个增量 dk 必须为1），然后以当前增量 d 为间隔，将待排序数组划分为 d 个子序列，对每个子序列分别执行插入排序；接着缩小增量，重新分组并排序，如此反复，直到增量缩小为1，此时整个数组作为一个子序列进行最后一轮插入排序，排序完成。

增量序列的选择直接影响希尔排序的效率，目前常用的有希尔增量、Hibbard增量、Knuth增量等。以最经典的希尔增量为例，其计算方式为 dk = floor(n / 2^k)，即每次将增量取为前一次的一半，逐步缩小直到1。例如对于长度为13的数组，增量序列依次为6、3、1。不同的增量序列会带来不同的时间复杂度表现，这也是希尔排序研究中一个持续探讨的话题。

希尔排序的代码初始化如下（采用11.4.1小节所展示的数据）：

▼
typescript
复制代码
import { testSort } from "hy-algokit";

export default function shellSort(arr: number[]): number[] {
  return arr
}

const arr = [81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15]

testSort(shellSort)

代码编写4步骤如下：

（1）初始化间隔：根据增量序列确定初始步长（如 n/2）。

（2）分组排序：以当前间隔将数组分为多个子组，对每个子组执行插入排序。

（3）步骤1与步骤2反复执行，直到步长间隔为1，数组已接近有序。

（4）缩小间隔并重复：将间隔缩小（如除以2），重复第2步，直到间隔为1时完成最后一轮排序，算法结束。

▼
typescript
复制代码
import { testSort } from 'hy-algokit'

// 希尔排序
export default function shellSort(arr: number[]): number[] {
  const n = arr.length

  // 选择不同的增量(步长/间隔)，确认初始步长
  let gap = Math.floor(n / 2)
  
  // 6 - 3 - 1
  // 1.第一层循环: 不断改变步长的过程
  while (gap > 0) { // 直到间隔为1时，结束排序
    // 获取到不同的gap, 使用gap进行插入排序
    // 2.第二层循环: 找到不同的数列集合进行插入排序的操作
    for (let i = gap; i < n; i++) {
      let j = i
      const num = arr[i]

      // 第三层循环: while循环, 对数列进行插入排序的过程
      // 使用num向前去找到一个比num小的值
      while (j > gap - 1 && num < arr[j - gap]) {
        arr[j] = arr[j - gap]
        j = j - gap
      }

      arr[j] = num
    }

    gap = Math.floor(gap / 2)
  }

  return arr
}

// const arr = [81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15]
// console.log(shellSort(arr))

testSort(shellSort)

希尔排序代码实现的麻烦之处在于有三层循环，容易被绕晕：

（1）第一层循环（while循环）：控制间隔gap的递减过程。gap从 n/2 开始，每轮缩小一半，依次经历如 6→3→1 的变化，直到 gap 为0时退出循环。这一层决定了整个算法要进行多少轮分组排序。

（2）第二层循环（for循环）：在当前gap下，从下标 gap 开始逐一遍历数组中的每个元素。它的作用是依次取出每个待插入的元素，相当于把所有子组的插入排序交织在一起执行——而不是先排完一个子组再排下一个，这样写起来更简洁，效果完全一样。

（3）第三层循环（while循环）：这是插入排序的核心操作。取出当前元素 num 后，在它所属的子组内向前比较，每次跨越 gap 个位置，将比 num 大的元素后移 gap 位，直到找到一个不大于 num 的位置，把 num 插入进去。这和标准插入排序的逻辑完全一致，只不过步长从1变成了gap。

总的来说，第一层循环决定要进行多少轮分组排序，每轮的步长间隔会不断减半，直到步长间隔为1。第二层循环和第三层循环共同完成对各子数组的插入排序，其中第二层循环依次取出当前待插入的元素，保存到临时变量 num 中；第三层循环则在该元素所属的子数组中向前查找，将比 num 大的元素逐个后移 gap 位，直到找到不大于 num 的位置或到达子数组边界，最后将 num 放入空出的位置，完成一次插入。

希尔排序的效率与增量序列的选择密切相关，但遗憾的是，其复杂度的严格数学证明非常困难，许多增量序列的效率至今仍未被完全证明。以最原始的希尔增量（每次减半）为例，最坏情况下时间复杂度为 O(N²)，不过在通常情况下表现都会优于 O(N²)。为了进一步提升效率，研究者们提出了多种改进的增量序列。

其中比较著名的有 Hibbard 增量序列（1, 3, 5, 7, ...，通项为 2k - 1），其最坏复杂度为 O(N3/2)，猜想的平均复杂度为 O(N5/4)，但尚未被证明；还有 Sedgewick 增量序列（1, 5, 19, 41, 109, ...），其最坏复杂度为 O(N4/3)，平均复杂度为 O(N^7/6)，同样未被严格证明。尽管理论证明仍有待突破，但在实际使用中，希尔排序在大多数情况下的效率都显著高于冒泡、选择、插入等简单排序算法，是一种实用且高效的排序方案。

总的来说，希尔排序作为一种改进版的插入排序，其历史意义远大于实用价值——它打破了"排序算法不可能突破 O(N²)"的固有认知，为后续更高效的排序算法铺平了道路。虽然它的时间复杂度取决于步长序列的选择，且最优步长序列至今未被证明，仍是一个开放的研究问题，但随着归并排序、快速排序等更优秀的算法相继出现，希尔排序在实际开发中已经很少被使用了。因此，我们更多地是学习和理解它"分组缩小间隔、逐步趋于有序"的核心思想，以及它在排序算法发展史上的突破性贡献。

11.5 排序算法总结

在完成多个排序算法之后，我们可以一次性的运行这些算法，从而完成效率的比对。而这也是在11.2小节与11.3小节中，并未贴出排序算法的运行效果的原因。

完成第三方库hy-algokit的引入，然后将之前实现的所有排序算法引入新的ts文件中，复制以下代码运行。

▼
typescript
复制代码
import { compareSort } from 'hy-algokit'
import bubbleSort from './01_冒泡排序(bubbleSort)'
import selectionSort from './02_选择排序(selectionSort)'
import insertionSort from './03_插入排序(insertionSort)'
import mergeSort from './04_归并排序(mergeSort)'
import quickSort from './05_快速排序(quickSort)'
import heapSort from './06_堆排序(heapSort)'
import shellSort from './07_希尔排序(shellSort了解)'


compareSort([
  bubbleSort,
  selectionSort,
  insertionSort,
  mergeSort,
  quickSort,
  heapSort,
  shellSort
], 100000)

11.5.1 各算法复杂度对比

我们将实现的7个排序算法以10万数据量作为标准进行测试，排序算法比对总结如图11-11所示。

▼
plain
复制代码
Sorting 100000 numbers:
quickSort      :12ms
heapSort       :18ms
shellSort      :24ms
mergeSort      :25ms
selectionSort  :5860ms
insertionSort  :11410ms
bubbleSort     :20967ms

图11-11 排序算法比对总结

11.5.2 排序算法选择策略

从这组10万数据量的测试结果中，可以非常直观地看到排序算法之间的性能鸿沟。冒泡排序耗时近21秒，插入排序约11秒，选择排序接近6秒，三者都处于"秒级"的量级；而希尔排序、归并排序、堆排序、快速排序全部在30毫秒以内完成，快了几百倍。这就是 O(N²) 与 O(N log N) 之间的差距——当数据量从1万增长到10万时，简单排序的耗时会膨胀100倍，而高级排序只会增长十几倍，数据量越大，差距越悬殊。

在四种高级排序算法中，快速排序以12毫秒排在第一，堆排序18毫秒紧随其后，希尔排序和归并排序分别为24毫秒和25毫秒，表现非常接近。快速排序之所以最快，是因为它的常数因子小、缓存命中率高，在大多数随机数据场景下都是首选。但快速排序在最坏情况下（如数据已经有序或接近有序）会退化到 O(N²)，因此在对稳定性和最坏情况有要求的场景中，归并排序是更稳妥的选择——它始终保持 O(N log N) 的复杂度，而且是稳定排序。堆排序同样保证 O(N log N) 的最坏复杂度，且不需要额外的内存空间，适合内存受限的场景。

那么简单排序是否就毫无用武之地了呢？其实不然。当数据量很小（比如几十个元素）时，简单排序的常数因子小、代码开销低，反而可能比高级排序更快。事实上，很多语言标准库中的排序实现（如 TimSort）在递归到小规模子数组时，就会切换为插入排序来处理。此外，如果数据本身已经接近有序，插入排序的效率会接近 O(N)，这是其他算法难以比拟的优势。

从实用和面试角度来说，11.3小节的归并、快速和堆排序是最需要掌握的，最好能够自己写出来。

所以，排序算法的选择并没有一个放之四海而皆准的答案，需要根据具体场景来权衡。数据量大、随机分布，优先选快速排序；需要稳定排序或要求最坏情况可控，选归并排序；内存紧张且不需要稳定性，选堆排序；数据量小或接近有序，插入排序反而是最佳选择。理解每种算法的特点和适用场景，比死记哪个"最快"要重要得多。

11.5.3 排序算法面试题

排序算法有专门的面试题，例如LeetCode的912题排序数组。题目地址：912. 排序数组 - 力扣（LeetCode）。

题目如下：

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

▼
plain
复制代码
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
解释：数组排序后，某些数字的位置没有改变（例如，2 和 3），而其他数字的位置发生了改变（例如，1 和 5）。

示例 2：

▼
plain
复制代码
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
解释：请注意，nums 的值不一定唯一。

提示：

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

将我们编写的排序算法都提交上去看看结果吧！本章的排序算法到这里结束，在下一章会开始学习动态规划。