鸣谢

本文参考文章或视频链接如下：

在文章开头对相关作者表示诚挚的感谢与敬意。

什么是排序

将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。

排序分为内部排序和外部排序：

  • 内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。
  • 外部排序：外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。 待排序的记录存储在外存上，排序时把数据一部分一部分的调入内存进行排序，在排序中需要多次进行内外存的交互，对外存文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序方法就称外部排序。

稳定排序： 假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。

为什么需要排序？
系统熵决定了一个问题被解决的难易程度。 熵是一个用来衡量系统混乱程度的物理学概念。一个系统越混乱，熵越大，反之，一个系统越有序，熵越小。频繁查找的场景，一次排序，多次查找，将一个序列变成有序序列，可以很大程度降低问题的复杂性。

常见的排序算法大概有十种，下图罗列了它们的名字和时间复杂度等信息：
Snip20220213_158.png
关于排序我们先从三个最基本的排序开始介绍。

冒泡排序

选择排序

插入排序

下面我们介绍的两种算法的核心思想是 “分治”。它的思想就是将一个大问题拆分为若干个小问题，针对这些小问题分别进行求解，再将小问题的解整合到大问题的解里。

从上面这句话的介绍可以看出，用 “分治” 思想解决问题大概分为下面三个步骤：

  1. 将大问题拆分为小问题
  2. 求解每个小问题的解

  3. 将小问题的解合并到大问题的解里

    归并排序

    1. 使用归并排序对给出的数组: arr = [10, 2, 89, 43, 211, 455, 888] 进行从小到大的排序，

    思路：

  4. 首先我们要从中间对数组进行分割，分割到每个数组中只有一个元素

  5. 然后对分割的数组进行两两合并，合并时候注意一定要有序合并
  6. 当所有分割的数组都被合并完后就得到了最终排序的数组 ```javascript console.log(mergeSort([ 10, 3, 5, 89, 23, 1, 90 ])); // [1, 3, 5, 10, 23, 89, 90]

function mergeSort(arr) { const len = arr.length; // 数组的长度小于等于1的时候没必要排序，直接返回即可 if (len <= 1) return arr;

// 获取分割点 const mid = Math.floor(len / 2); // 将数组从中间分为左右两个数组 const leftArr = mergeSort(arr.slice(0, mid)); const rightArr = mergeSort(arr.slice(mid));

// 对分割后的数据进行排序合并 return mergeArr(leftArr, rightArr); } /* 合并两个有序数组：

  1. 同时遍历两个数组，比较当前元素的大小，将小的推到结果数组中；

  2. 当某个数组遍历完后，看看有没有哪个数组还剩下元素，因为数组是升序的，剩余的元素肯定比结果数组中的元素大，所以直接将剩余元素合并到结果数组中 */ function mergeArr(arr1, arr2) { const len1 = arr1.length,

     len2 = arr2.length,
 res = [];

    let i = 0,

     j = 0;

    while (i < len1 && j < len2) {

     if (arr1[i] < arr2[j]) {
     res.push(arr1[i]);
     i++;
 } else {
     res.push(arr2[j]);
     j++;
 }

    }

    if (i < len1) {

     return res.concat(arr1.slice(i));

    } return res.concat(arr2.slice(j)); }

```

快速排序