排序算法

第一章：简介

一、是什么

1. 概念

排序（sort）就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

2. 分类

排序时是否需要外存

内部排序：数据都在内存中（关注如何使算法时间、空间复杂度更低）。
外部排序：数据太多，无法全部放入内存（还要关注如何使读 / 写磁盘次数更少）。

排序时的操作

交换类排序（Swap）：冒泡排序、快速排序 ……
归并类排序（Merge 合并）：归并排序 ……
插入类排序（往已排好的序列里加塞）：直接插入排序、希尔排序 ……
选择类排序（每次挑出最小 / 最大的）：简单选择排序、堆排序 ……
……

……

3. 评价指标

1）时间复杂度

2）空间复杂度

3）稳定性

相同的元素在排序后的相对顺序是否保持不变。如果保持不变，那就是稳定的，否则就是不稳定。

举例：(value, id)

[(5, 1), (3, 2), (5, 3), (2, 4)]

如果使用稳定排序

[(2, 4), (3, 2), (5, 1), (5, 3)]

如果使用不稳定排序

[(2, 4), (3, 2), (5, 3), (5, 1)]

二、常见的排序算法

冒泡排序
快速排序 (分治思想) 🌟
插入排序
希尔排序
归并排序 (分治思想) 🌟
选择排序
堆排序 🌟
基数排序
计数排序
桶排序
内省排序
平滑排序

第二章：交换类排序

一、冒泡排序

1. 核心思想

冒泡排序（Bubble Sort），这是所有排序方法中最为简单的排序方法，该排序算法的核心思想如下：

遍历整个元素序列，每次取出两个相邻的元素进行比较
如果顺序不对（看你具体的排序规则：如从小到大、首字母从 A 到 Z），就进行交换
一次遍历完成，称之为完成了一次冒泡。每一轮冒泡会确定一个数的正确位置
例如从小到大排序（升序），那么第一轮冒泡就会确定最大的数、第二轮冒泡就会确定倒数第二大的数，依此类推 ……

适用范围：顺序表或链表。

2. 代码实现

typescript

export default function bubbleSort(arr: number[]): number[] {
  let n = arr.length;
  let swapped = false; // 记录是否发生了交换

  // 外层 for 循环控制的是冒泡的次数
  for (let i = 0; i < n - 1; i++) {
    // 内层循环控制的是比较的次数
    // 因为比较是从第一个数字开始
    for (let j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 进行交换
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        // 发生了交换，置 swapped 为 true
        swapped = true;
      }
    }
    // 出了内层for循环后，判断是否发生了交换
    // 我们就需要判断是否进入过 if，如果没有进入过，说明数组已经有序
    if (!swapped) {
      break;
    }
  }
}

3. 评价指标

1）复杂度

[1] 时间复杂度

最好： $O (n)$
最好的情况就是数组本来就是有序的。没有发生任何交换操作，只在一轮的比较后就结束了。
比较次数： $n - 1$ 移动次数： $0$
因此时间复杂度是 $O (n)$
最坏： $O (n^{2})$
最坏的情况就是数组是逆序的（从大到小）。
第一轮：比较 $n - 1$ 次、交换 $n - 1$ 次，而一次交换发生了 3 次移动，所以移动次数是 $3 \times (n - 1)$
第二轮：比较 $n - 2$ 次、交换 $n - 2$ 次，而一次交换发生了 3 次移动，所以移动次数是 $3 \times (n - 2)$
…… 由此可以列出下面的公式。
比较次数： $(n - 1) + (n - 2) + \dots + 2 + 1 = \frac{n (n - 1)}{2}$
移动次数： $3 \times ((n - 1) + (n - 2) + \dots + 2 + 1) = 3 \times \frac{n (n - 1)}{2} = \frac{3 n (n - 1)}{2}$
总的操作次数 = 比较次数 + 移动次数，可以看到他们两个的最高次项都是平方级，那么加起来也一定是平方级。
平均： $O (n^{2})$
一般情况下，每一轮都需要 $O (n)$ 复杂度的比较和交换。排序的轮数也可以理解成 $O (n)$ 。
因此两者相乘 $O (n \times n)$ ，也就是 $O (n^{2})$ 。

[2] 空间复杂度

因为只用到了一些循环和交换的辅助变量，这些变量的数量不会随着 n 的增加而增长，所以空间复杂度为 $O (1)$ 。

2）稳定性

冒泡排序的核心原理是相邻的两个数进行比较，假设我们是升序排序，那么只有右边的数小于左边的时候，才会交换。相等的情况下是不会做操作的。因此冒泡排序是一种稳定的排序方式。

二、快速排序

快速排序（Quick Sort）背后采用的是分治的思想。

1. 核心思想

1）工作流程

选择基准元素
从数组中 随机选择 一个元素作为基准值（pivot）。
分区操作
将数组中所有小于基准的元素移动到基准的左侧，大于基准的元素移动到右侧。这样，基准就处于它排序后应在的位置上。整个序列就变成了 [比基准小的值] 基准值 [比基准大的值]
递归排序
对基准左右两边的子数组分别重复上述步骤，直到所有子数组都有序。

例子

假设我们有 [3, 5, 8, 1, 2, 9, 4, 7] 这个序列，这里选择 4 来作为基准值。

接下来从头到尾，把小于 4 的放到左边，大于 4 的放到右边，如下图所示：

接下来对基准值左边和右边进行相同的操作即可。

好了，这是关于快速排序的最基本的思想。下面是一个快速排序整体框架的示例代码：

javascript

// 分治函数
function partition(array, left, right){
  // todo
}

// 这是入口函数
function quickSort(array){
  function QuickSort(array, left, right){
    if(left < right){
      // 该方法内部，会选择一个元素作为基准值
      // 然后将所有小于基准值的元素，放到基准值左边，所有大于基准值的元素，放到基准值右边
      // 最后会返回基准值的索引
      let index = partition(array, left, right);
      // 拿到基准值之后，再对数组进行切割，对左右两边的子数组做相同的操作
      QuickSort(array, left, index - 1);
      QuickSort(array, index + 1, right);
    }
  }
  QuickSort(array, 0, array.length - 1);
}

const arr = [3, 5, 8, 1, 2, 9, 4, 7];
quickSort(arr);

快速排序的 partition 方法的实现有多种方式，例如：

左右指针法。
挖坑法。
新数组法。

这里我们就介绍一个最常用的左右指针法。

2）左右指针法

使用左右指针法实现 partition 方法的步骤如下：

选取某个元素作为 pivot 基准值，一般取当前数组的第一个元素或者最后一个元素，这里我们采用 最后一个元素。
从 left 一直 向后寻找，直到找到一个大于 pivot 的值，然后 right 从后往前找，找到一个小于 pivot 的值，然后 交换这两个元素的位置。
注意：基准选最右，左指针先走；基准选最左，右指针先走。
重复第 2 步，直到 left 和 right 相遇，这时将 pivot 放置在 left 的位置即可。

下面是一个具体的图解：

（1）原始数组，left 一开始指向第一个元素，right 一开始指向倒数第二个元素，最后一个元素是基准值

（2）left 从左往右走，走到 7 的位置就停下了，接下来 right 从右往左走，一开始在 3 的位置就停下了。然后两者进行交换

（3）left 继续往右走，走到 6 的位置停下，right 走到 0 的位置，然后停下，两者进行交换

（4）left 继续走，走到 9 停下来，right 继续走，走到 2 停下来，进行交换

（5）接下来 left 继续往右走，此时 left >= right 了，说明第一轮就走完了，将基准值和 array[left] 进行交换

然后走完一轮之后，基准值左边的元素都是比基准值小的，基准值右边的元素都是比基准值大的。

2. 代码实现

typescript

// 分治函数
function partition(array: number[], left: number, right: number) {
  let pivot = array[right]; // 首先是找一个基准值，我们取最后一个元素作为基准值
  let pivotIndex = right; // 基准值对应的下标

  while (left < right) {
    // 左边的left一直往右走
    while (left < right && array[left] < pivot) {
      left++;
    }
    // 上面跳出while说明找到了一个比基准值大的
    // 右边的right一直往左边走
    while (left < right && array[right] >= pivot) {
      right--;
    }
    // 上面跳出 while 说明找到了一个比基准值小的
    [array[left], array[right]] = [array[right], array[left]];
  }
  // 当跳出上面的while的时候，需要将基准值和left指向的值进行交换
  [array[left], array[pivotIndex]] = [array[pivotIndex], array[left]];
  return left;
}

// 这是入口函数
export default function quickSort(arr: number[]): number[] {
  function QuickSort(left, right) {
    // 注意下面的条件判断，是判断子数组是否还能够继续拆分
    if (left < right) {
      // 该方法内部，会选择一个元素作为基准值
      // 然后将所有小于基准值的元素，放到基准值左边，所有大于基准值的元素，放到基准值右边
      // 最后会返回基准值的索引
      let index = partition(array, left, right);
      // 拿到基准值之后，再对数组进行切割，对左右两边的子数组做相同的操作
      QuickSort(left, index - 1);
      QuickSort(index + 1, right);
    }
  }
  QuickSort(0, array.length - 1);
}

const arr = [3, 5, 8, 1, 2, 9, 4, 7];
quickSort(arr);
console.log(arr);

3. 评价指标

1）复杂度

[1] 时间复杂度

最好： $O (n l o g n)$
因为递归函数里会调用两次递归函数，所以构成了二叉递归树。因此递归次数是 $O (l o g n)$ 。
每一层中又需要进一步划分，而划分操作的复杂度是 $O (n)$ 。
可以看到递归次数乘以每层划分操作就是该算法最好的时间复杂度了。
最差： $O (n^{2})$
二叉递归树变为链式的树。因此递归次数是 $O (n)$ 。
每一层中又需要进一步划分，而划分操作的复杂度是 $O (n)$ 。
平均： $O (n l o g n)$

[2] 空间复杂度

最好： $O (l o g n)$

最坏： $O (n)$

2）稳定性

快排是一种 不稳定 排序，因为在分区的过程中，元素的交换可能影响相等元素的原始顺序。

第三章：插入类排序

一、直接插入排序

1. 核心思想

插入排序（Insertion Sort），其核心思想类似于整理扑克牌：在手中已经排好序的牌堆中，逐张拿出未排序的牌，找到合适的位置插入进去，直到所有牌都有序为止。

下面是插入排序的工作流程：

分区概念：将数组分为 已排序区间 和 未排序区间 两个部分。初始时，默认第一个元素为已排序区间，其余元素为未排序区间。
逐个插入：从未排序区间中取出第一个元素，依次与已排序区间的元素进行比较，将其插入到合适的位置，使得已排序区间依然保持有序。
移动元素：当新元素小于已排序区间中的某个元素时，需要将该元素及其后续元素依次向后移动，为新元素腾出插入位置。
重复操作：重复以上过程，直到未排序区间为空，整个数组变成有序序列。

2. 代码实现

typescript

export default function insertionSort(arr: number[]): number[] {
  // 从第二个元素开始，到最后一个元素
  // 因为会假设第一个元素已经排好顺序了
  for(int i = 1; i < arr.length; i++){
    // 取出每一个要插入的元素
    let current = arr[i]

    // 要和已排序区间里面的元素进行比较，找到正确的插入位置
    // j 一开始是已排序区间的最后一个元素
    let j = i - 1
    // 这个循环负责将已排序区间的元素往后面移动
    while(j >= 0 && arr[j] > current){
      arr[j+1] = arr[j]
      j--
    }
    // 跳出 while 循环的时候，说明当前元素已经找到插入的位置了
    arr[j+1] = current
  }

  return arr
}

代码解释：

外层 for 循环：从第二个元素开始，将每个元素看作是待插入的元素。
内层 while 循环：将当前待插入的元素和已排序区间的每一个元素逐一比较，如果当前待插入元素小于已排序元素，直接将已排序元素往后移动，直到找到正确的插入位置。

3. 评价指标

1）复杂度

时间复杂度： $O (n^{2})$
空间复杂度： $O (1)$

2）稳定性

因为插入排序，待插入的元素只有在大于前一个数的时候，已排序区域的元素才会往后移动，值相等的话，是插入到有序数列中相同数的后面的。因此，插入排序是一种稳定排序。

二、折半插入排序

1. 核心思想

折半插入排序作为插入排序的改进版，不同的地方在于 寻找插入位置时的操作。我们知道，插入排序分为两大区间，一个是前面排好序的有序队列，另一个是未排好序的乱序队列。例如：

在上面的队列中，前面的 6 到 45 已经是排好序了的有序队列，右边的 17 到 9 是还未排好序的乱序队列。现在需要对 17 进行插入操作，那么标准的插入排序是怎么样的？

标准插入排序是 挨着挨着进行比较，然后找到正确的插入位置，插入进去。

既然前面是有序的数列，因此我们在查找插入位置的时候，实际上可以使用 二分查找 来找，这样能 提升查找插入位置效率。

另外，在移动元素上，折半插入排序和标准插入排序也有区别：

标准插入排序：一边查找插入的位置，一边移动元素
折半插入排序：先通过二分查找找到插入的位置，再将插入位置之后的元素统一做移动操作

2. 代码实现

function binaryInsertionSort(arr){
  // 从第二个元素开始遍历，因为第一个元素会被视为已排序元素
  for(let i = 1; i < arr.length; i++){
    let current = arr[i]; // 当前要插入的元素
    let left = 0;
    let right = i - 1;
    
    // 这里就是使用二分查找，查找正确的插入位置
    while(left <= right){
      let mid = Math.floor((left + right) / 2);
     	if(arr[mid] < current){
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    // 跳出上面的 while 循环，说明 left > right
    // 说明找到了插入位置，插入位置就是 left 这个位置
    
    // 移动
    for(let j = i-1; j >= left; j--){
      arr[j+1] = arr[j];
    }
    
    // 插入
   	arr[left] = current;
  }
}

const arr = [7, 20, 27, 36, 55, 60, 28, 36, 67, 44, 16];
binaryInsertionSort(arr);
console.log(arr);

总结：整个折半插入相比标准插入，区别就在于查找插入位置的代码。

标准插入：

// 一边移动一边查找插入位置
while (j >= 0 && arr[j] > current) {
  arr[j + 1] = arr[j];
  j--;
}

折半插入：

// 先使用二分查找来找到插入的位置
while(left <= right){
  let mid = Math.floor((left + right) / 2);
  if(arr[mid] < current){
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}

// 跳出上面的 while 循环，说明 left > right
// 说明找到了插入位置，插入位置就是 left 这个位置

// 然后再统一的做移动操作
for(let j = i-1; j >= left; j--){
  arr[j+1] = arr[j];
}

3. 算法性能分析

1）复杂度

时间复杂度： $O (n^{2})$ 提升的是查找的效率，但是移动的次数是没有变化的。
空间复杂度： $O (1)$

2）稳定性

稳定排序。

三、希尔排序

希尔排序（Shell Sort）也称为递减增量排序算法，是插入排序的一种改进版本。

希尔排序主要利用到了插入排序的两个特点：

如果数据量比较小，即便是最坏情况 $O (n^{2})$ 也和 $O (n)$ 拉不开差距，此时效率也比较高。
如果序列基本有序，那么时间复杂度能够达到 $O (n)$ 级别。

1. 核心思想

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序。

1）增量与分组

希尔排序的核心思想是采用分组的策略来对数据进行排序。

这里可以通过一个叫增量的东西，增量的选择方式比较多，这里介绍一种常见的选择方式，那就是取序列长度的一半。

例如下面的序列：

36  27  20  60  55  7  28  36  67  44  16

在这个序列中，存在 11 个数，增量 d 就为 $⌊ \frac{11}{2} ⌋ = 5$ 。

增量实际上就是一个一个间隔值，表示间隔多少个数取下一个数字。

例如：一开始下标是 0 ==> 36，下标+增量 = 5 ==> 7

根据增量，就可以对元素进行一个分组操作。

2）工作流程

例子二

第一组

下标从 0 开始。间隔是 5，对应的下标 [0, 5, 10]，这三个下标对应的元素 [36, 7, 16]，那么这三个数字就是一组。

接下来就对这三个数进行插入排序

第二组

下标从 1 开始。间隔是 5，对应的下标就是[1, 6]，对应的元素[27, 28]

第三组

下标从 2 开始，间隔是5，取到的下标就有[2, 7]，对应的值就为[20， 36]

第四组

下标从 3 开始，间隔是 5，取到的下标有[3, 8]，对应的元素有[60, 67]

第五组

下标从 4 开始，间隔是 5，取到的下标[4, 9]，对应的元素就是 [55, 44]

同样对这两个数进行插入排序：

目前为止，增量 5 的所有分组就全部排好序了。

注意：增量为多少，就会分多少个组。

接下来需要更新增量。接下来增量就会变成上一轮增量的一半。增量 $d = ⌊ \frac{5}{2} ⌋ = 2$ 也就是说，这一次会分为两个组。

第一组

下标从 0 开始，这一组的下标就是[0, 2, 4, 6, 8, 10]，对应的元素就是[7, 20, 44, 28, 67, 36]

接下来还是针对这一组做插入排序，排序后的结果如下：

第二组

下标从 1 开始，对应的下标就是 [1, 3, 5, 7, 9]，这些下标对应的元素[27, 60, 16, 36, 55]

仍然对这一组做插入排序

至此，第二轮希尔排序也就结束了。总共是两个组。第二轮排序下来后相比第一轮又要有序一些了。

继续更新增量 $d = ⌊ \frac{2}{2} ⌋ = 1$ 其实就是一个组，对序列里面所有的数进行插入排序。目前序列已经基本有序，涉及到的交换非常的少：

这一轮只有 44 和 55 进行交换，然后整个排序结束。

总结：

一开始增量比较大，意味着分组多，但是每一组的元素比较少，所以效率比较高。
后面增量会越来越小，意味着分组减少，每一组的元素会增多，但是随着增量的减少，每一组组内的元素也越来越有序。所以效率也很高。

另外说一下增量 [5, 2, 1]，每次取一半。增量是不断在减少的，因此希尔排序又被称之为 缩小增量排序。

关于增量的选择有很多其他的方式，不同的方式，效率不同。但是不管哪一种方式，最后一轮增量一定为 1。

2. 代码实现

1）写法一

javascript

function shellSort(arr){
  let n = arr.length; // 数组的长度
  let gap = Math.floor(n / 2); // gap就是增量

  // 外面的循环表示的是增量的轮数，增量有几个数，这里就会循环多少次
  while(gap > 0){
    // 根据当前的增量值，对每一组进行一个插入排序
    // 这个 for 循环就是在处理同一组的元素
    for(let i = gap; i < n; i++){
      let temp = arr[i]; // 暂存当前的元素
      let j = i; // 将 j 设置为当前索引 i，主要是用来寻找插入位置

      // 将当前元素按照间隔进行插入排序
      while(j >= gap && arr[j - gap] > temp){
        arr[j] = arr[j - gap];
        j -= gap;
      }

      arr[j] = temp; // 将暂存的元素放入到正确的位置
    }

    // 更新 gap 值
    gap = Math.floor(gap / 2);
  }
}


const arr = [36, 27, 20, 60, 55, 7, 28, 36, 67, 44, 16];
shellSort(arr);
console.log(arr);

外层第一个 while 循环：负责循环增量。
内层的 while 循环：查看每一个分组间隔的元素是否正确，不正确的话就将当前元素与间隔内前一个元素进行交换。
中间的 for 循环：这个循环实际上是在处理同组的元素。

数组为：[36, 27, 20, 60, 55, 7, 28, 36, 67, 44, 16]
下标为：[ 0,  1,  2,  3,  4, 5,  6,  7,  8,  9, 10]
gap = 5;
for循环第一轮
i: 5
取到的元素：7、36（第一组）
i: 6
取到的元素：28、27（第二组）
i: 7
取到的元素：36、20（第三组）
i: 8
取到的元素就是 67、60（第四组）
i: 9
取到的元素就是 44、55（第五组）
i: 10
取到的元素就是 16、7、36（第一组）

2）写法二

javascript

function shell_sort(arr) {
  for (let gap = arr.length >> 1; gap > 0; gap >>= 1) { // 计算 gap
    for (let i = gap; i < arr.length; i++) {
      let temp = arr[i], j; // 保存 gap 索引的值、创建 i 的副本, 用于不断计算同一分组中前一项的索引
      for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }
  }

  return arr;
};

3. 算法分析

1）复杂度

时间复杂度：O(nlogn)
空间复杂度：O(1)

2）稳定性

不稳定。

第四章：归并类排序

一、归并排序

归并排序（Merge Sort），这是一种基于 分治法 的排序算法。

1. 核心思想

基本思想：将一个大的数组分成若干个小的数组，直到每个小数组只有一个元素为止。然后再将这些小数组合并成一个有序的数组。

[1] 工作流程

1）分割：将原始数组分成两个部分，递归的将每一个部分的数组继续分割，直到每个部分只包含一个元素。

2）合并：将分割好的部分，两两合并，合并的时候保持顺序，最终合并成一个有序的数组。

“拆分”非常好理解，每次砍一半。

关键是“合并”，究竟是如何合并成有序的？

[2] 合并过程

那么这里以最后一步为例：[4, 5, 7, 8] 和[1, 2, 3, 6] 进行合并。

定义两个指针，第一个指向第一个有序数组的第一个元素；第二个指向第二个有序数组的第一个元素。需要创建一个临时数组，临时数组的长度 = 两个数组长度之和。两个有序数组的第一个元素进行比较，谁小，谁就放入到临时数组的一个元素位置
放入临时数组之后，j 右移指向第二个有序数组的第二个元素。
继续 i 和 j 对应的元素进行比较，4 和 2 比较，仍然是 2 比较小，将 2 放入到 temp 数组的第二个元素的位置。
接下来 j 继续往右边移动，指向第二个有序数组的第三个元素。
继续 i 和 j 对应的元素进行比较，4 和 3 比较，仍然是 3 比较小，将 3 放入到 temp 数组的第三个元素的位置。
接下来 j 继续往右边移动，指向第二个有序数组的第四个元素。
继续 i 和 j 对应的元素进行比较，这一次就是 4 和 6 进行比较，这一次是 4 是比较小，将 4 放入到 temp 数组的第四个元素的位置
接下来就是 i 继续往右边移动，指向第一个有序数组的第二个元素。
继续 i 和 j 对应的元素进行比较，这一次是 5 和 6 进行比较，这一次是 5 是比较小，将 5 放入到 temp 数组的第五个元素的位置
接下来就是 i 继续往右边移动，指向第一个有序数组的第三个元素。
接下来继续上面的操作，这一次是 7 和 6 进行比较，6 比较小，将 6 放入到 temp 数组的第六个元素的位置
这一次应该是 j 往右边移动。但是这一次 j 已经无法往右边移动。说明第二个有序数组所有的元素已经遍历结束。
只需要将第一个有序数组的剩余元素，全部放入到 temp 数组里面即可
最后，再将 temp 这个临时数组里面所有的元素拷贝到原数组中，合并结束

2. 代码实现

typescript

// 这个方法负责合并
function merge(left, right) {
  let result = []; // 临时数组
  let leftIndex = 0; // 左数组的索引，默认指向第一个元素
  let rightIndex = 0; // 右数组的索引，默认指向右数组的第一个元素

  while (leftIndex < left.length && rightIndex < right.length) {
    // 里面就判断究竟是左边数组的元素小还是右边数组元素小
    // 将小的元素放入到临时数组里面
    if (left[leftIndex] <= right[rightIndex]) {
      // 说明左边的元素更小
      // 将左边元素放入到临时数组里面
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      // 说明右边元素更小
      // 将右边元素放入到临时数组里面
      result.push(right[rightIndex++]);
    }
  }

  // 代码来到这里，说明 left 或者 right 总之有一边已经结束了
  // 将另外一个数组剩余的所有元素放入到临时数组里面
  if (leftIndex < left.length) {
    // 说明左边数组有剩余
    result = result.concat(left.slice(leftIndex));
  }

  if (rightIndex < right.length) {
    // 说明右边数组有剩余
    result = result.concat(right.slice(rightIndex));
  }

  return result;
}

// 这个方法主要是负责拆
export default function mergeSort(arr: number[]): number[] {
  if (arr.length < 2) {
    // 如果进入此分支，说明数组不能够再拆了，该数组已经是单独的一个元素了
    // 直接返回该数组
    // 这个其实就是递归的出口
    return arr;
  }

  // 如果没有进入上面的 if，那么就需要拆分数组，就是对半分
  const mid = Math.floor(arr.length / 2);

  // 根据上面计算出来的中间值，将整个数组分为左半部分和右半部分
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  // 下一步，就是合并左右两个子数组
  return merge(left, right);
}

3. 算法性能分析

1）复杂度

时间复杂度：O(nlogn)
空间复杂度：O(n)，因为在归并排序中，需要额外的空间来存储临时数组用于合并操作。

2）稳定性

归并排序是一种稳定排序。

如果遇到相等的元素，是优先将左边数组的元素放入临时数组。

typescript

if (left[leftIndex] <= right[rightIndex]) {
  // 说明左边的元素更小
  // 将左边元素放入到临时数组里面
  result.push(left[leftIndex]);
  leftIndex++;
} else {
  // 说明右边元素更小
  // 将右边元素放入到临时数组里面
  result.push(right[rightIndex++]);
}

关键就是 left[leftIndex] <= right[rightIndex]，因此在左右数组元素相等的情况下，优先放入左边数组的元素。

假设修改一下 left[leftIndex] < right[rightIndex]，这么一改，就变成优先取右边数组的元素放入临时数组，就会导致不稳定。

第五章：选择类排序

一、简单选择排序

1. 基本概念

选择排序（Selection Sort），这是一种简单直观的排序算法，其核心思想在于每次从待排序的数组中选出最小（或最大）的元素，并将其放到数组的起始（或末尾）位置，从而逐步构建有序区间。

它的工作原理是：

划分区间：将数组分为 已排序区间 和 未排序区间 两部分。初始时已排序区间为空，未排序区间即整个数组。
选择最小元素：在未排序区间中，找到最小（或最大）的元素。
交换位置：将找到的最小（或最大）元素与未排序区间的第一个元素交换位置，这样该元素就加入到了已排序区间中。
重复操作：对剩余的未排序区间重复上述步骤，直到整个数组排序完毕。

2. 代码实现

typescript

export default function selectionSort(arr: number[]): number[] {
  const n = arr.length;

  // 指向未排序区间的起始位置
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i; // 假设当前的 i 所对应的数就是最小值
    // 内层for循环每次都是从 i 的右侧那一个到最后一个
    // 内层for循环的目的是找到最小值的索引
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) { // 只有不相等时, 才需要进行交换操作
      // 做一个交换
      let temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
}

3. 算法分析

1）复杂度

时间复杂度： $O (n^{2})$
空间复杂度： $O (1)$

2）稳定性

选择排序在每一轮选择中会改变元素的相对顺序，因此选择排序是一种 不稳定 的排序。

二、堆排序

1. 是什么

2. 代码分析

3. 算法分析

[1] 复杂度

时间复杂度：
最佳： $O (n \times k)$ 最差： $O (n \times k)$ 平均： $O (n \times k)$
空间复杂度： $O (n + k)$

[2] 稳定性

稳定排序。

第六章：非比较类排序

一、基数排序

1. 是什么

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

算法步骤

取得数组中的最大数，并取得位数，即为迭代次数 $N$ （例如：数组中最大数值为 1000，则 $N = 4$ ）。
A 为原始数组，从最低位开始取每个位组成 radix 数组。
对 radix 进行计数排序（利用计数排序适用于小范围数的特点）。
将 radix 依次赋值给原数组。
重复 2~4 步骤 $N$ 次。

2. 代码分析

3. 算法分析

[1] 复杂度

时间复杂度：
最佳： $O (n \times k)$ 最差： $O (n \times k)$ 平均： $O (n \times k)$
空间复杂度： $O (n + k)$

[2] 稳定性

稳定排序。

排序算法 ​

第一章：简介 ​

一、是什么 ​

1. 概念 ​

2. 分类 ​

3. 评价指标 ​

二、常见的排序算法 ​

第二章：交换类排序 ​

一、冒泡排序 ​

1. 核心思想 ​

2. 代码实现 ​

3. 评价指标 ​

1）复杂度 ​

[1] 时间复杂度 ​

[2] 空间复杂度 ​

2）稳定性 ​

二、快速排序 ​

1. 核心思想 ​

1）工作流程 ​

2）左右指针法 ​

2. 代码实现 ​

3. 评价指标 ​

1）复杂度 ​

[1] 时间复杂度 ​

[2] 空间复杂度 ​

2）稳定性 ​

第三章：插入类排序 ​

一、直接插入排序 ​

1. 核心思想 ​

2. 代码实现 ​

3. 评价指标 ​

1）复杂度 ​

2）稳定性 ​

二、折半插入排序 ​

1. 核心思想 ​

2. 代码实现 ​

3. 算法性能分析 ​

1）复杂度 ​

2）稳定性 ​

三、希尔排序 ​

1. 核心思想 ​

1）增量与分组 ​

2）工作流程 ​

2. 代码实现 ​

1）写法一 ​

2）写法二 ​

3. 算法分析 ​

1）复杂度 ​

2）稳定性 ​

第四章：归并类排序 ​

一、归并排序 ​

1. 核心思想 ​

[1] 工作流程 ​

[2] 合并过程 ​

2. 代码实现 ​

3. 算法性能分析 ​

1）复杂度 ​

2）稳定性 ​

第五章：选择类排序 ​

一、简单选择排序 ​

1. 基本概念 ​

2. 代码实现 ​

3. 算法分析 ​

1）复杂度 ​

2）稳定性 ​

二、堆排序 ​

1. 是什么 ​

2. 代码分析 ​

3. 算法分析 ​

[1] 复杂度 ​

[2] 稳定性 ​

第六章：非比较类排序 ​

一、基数排序 ​

1. 是什么 ​

2. 代码分析 ​

3. 算法分析 ​

[1] 复杂度 ​

[2] 稳定性 ​

排序算法

第一章：简介

一、是什么

1. 概念

2. 分类

3. 评价指标

二、常见的排序算法

第二章：交换类排序

一、冒泡排序

1. 核心思想

2. 代码实现

3. 评价指标

1）复杂度

[1] 时间复杂度

[2] 空间复杂度

2）稳定性

二、快速排序

1. 核心思想

1）工作流程

2）左右指针法

2. 代码实现

3. 评价指标

1）复杂度

[1] 时间复杂度

[2] 空间复杂度

2）稳定性

第三章：插入类排序

一、直接插入排序

1. 核心思想

2. 代码实现

3. 评价指标

1）复杂度

2）稳定性

二、折半插入排序

1. 核心思想

2. 代码实现

3. 算法性能分析

1）复杂度

2）稳定性

三、希尔排序

1. 核心思想

1）增量与分组

2）工作流程

2. 代码实现

1）写法一

2）写法二

3. 算法分析

1）复杂度

2）稳定性

第四章：归并类排序

一、归并排序

1. 核心思想

[1] 工作流程

[2] 合并过程

2. 代码实现

3. 算法性能分析

1）复杂度

2）稳定性

第五章：选择类排序

一、简单选择排序

1. 基本概念

2. 代码实现

3. 算法分析

1）复杂度

2）稳定性

二、堆排序

1. 是什么

2. 代码分析

3. 算法分析

[1] 复杂度

[2] 稳定性

第六章：非比较类排序

一、基数排序

1. 是什么

2. 代码分析

3. 算法分析

[1] 复杂度

[2] 稳定性