我们上大学的时候，学习算法的第一类算法就是排序算法，不知道大家学得怎么样，反正我当时学得不是太清晰，以至于很多年过去了我也只懂得冒泡排序算法的逻辑，即便是手写冒泡排序有时候都还磕磕绊绊，需要好几轮调试修改。

前段时间开始看《算法》这本书，也就是黄色那本很厚的算法参考书。

看完之后感觉自己以前都不算一个程序员，因为对代码的思考更多还是靠着业务逻辑去理解，但是代码实现很多时候跟实际业务逻辑是不一样的。

以下是我对排序这一章节的核心思路的整理和理解：

冒泡排序

for (let i = 0; i < data.length; i++) {
  for (let j = 0; j < data.length - i - 1; j++) {
    if (data[j] > data[j+1]) {
      swap(j, j+1, data)
    }
  }
}

这里我省略了swap的代码，后面也不会再强调，swap函数就是给两个下标和列表变量，然后交换两个下标对应的数据，非常简单，应该大部分程序员都可以理解：

function swap(i, j, data) {
  const temp = data[i]
  data[i] = data[j]
  data[j] = temp
}

冒泡排序简单来说就是：每次比较相邻的两个数据，将较大的数据移到右边（从小到大顺序排序）。

所以实际上真正起作用的是j的循环，而外层的i循环可以理解为轮次数，因为我们总共需要data.length个数据进行排序。而每一轮，都会将1个数据摆放到合适的位置，所以下一轮的时候就需要剔除这部分数据，减少无用的比较。所以每轮j都循环到data.length-i-1为止。减i是不处理最后i个数据，减1是因为我们是j和j+1比较，所以为了避免越界，最多循环到data.length-1。

冒泡排序是最简单易懂的排序，口诀就是：比较相邻的两个数据，进行i轮循环。

选择排序

for (let i = 0; i < data.length; i++) {
  let min = i
  for (let j = i+1; j < data.length; j++) {
    if (data[j] < data[min]) {
      min = j
    }
  }
  if (min !== i) {
    swap(min,i,data)
  }
}

选择排序的逻辑也很简单，每次循环遍历之后，找出剩下数据中最小的数，将它放到i的位置，其实有点像打牌的时候码牌的动作。

它的排序效率其实跟冒泡一样都是O(n^2)，但是由于它的插入数量只有n次，相比起冒泡来说，在计算机内存优化的角度来说是更优异一些的。

插入排序

for (let i = 1; i < data.length; i++) {
  const temp = data[i]
  let j = i-1
  for (; j >= 0; j--) {
    if (data[j]>temp) {
      data[j+1] = data[j]
    } else {
      break
    }
  }
  data[j+1] = temp
}

插入排序，将列表分为了前后两个部分，以i为分割，前一部分为有序部分，后一部分为无序部分，每轮循环，需要判断i的所在位置，j循环则是在搜索i的理想位置（第一个小于i的位置），同时为了给插入留出空间，需要将当前j移到j+1位置。

这个算法还有一个简化版本：

for (let i = 1; i < data.length; i++) {
  for (let j = i-1; j >= 0; j--) {
    if (data[j] > data[j+1]) {
      swap(j, j+1, data)
    } else {
      break
    }
  }
}

这样做其实是在每轮判断的时候就处理了插入操作，看起来逻辑跟冒泡是差不多的，都是相邻之间判断，但是冒泡排序是不判定已排序部分，而插入是在已排序部分反向冒泡。

以上是三种基础排序算法，它们的效率都是O(n^2)。

希尔排序

希尔排序是对插入排序的一个扩展，一个小小的改动导致排序的时间效率突破了O(n^2)的局限。

for (let gap = Math.floor(data.length / 2); gap >= 1; gap=Math.floor(gap/2)) {
  for (let k = 0; k < gap; k++) {
    for (let i = gap + k; i < data.length; i+=gap) {
      for (let j = i - gap; j >= gap; j-=gap) {
        if (data[j]>data[j+gap]) {
          swap(j, j+gap, data)
        } else {
          break
        }
      }
    }  
  }
}

可以看到我们引入了一个gap变量，它表示每次比较的步进间隔，插入排序可以理解为是一个gap为1的希尔排序。

k循环是为了方便计算i，因为每一个数据都应当被遍历到，而gap会导致会有一些数据被跳过。k的存在就是保证这些被跳过的gap之间的数据被遍历到。

举个例子来帮助理解：假设有一个数组[12,3,7,5,4,6,9,1,2,10,11,8]，它的长度是12，设现在的gap为4，则实际上我们把这个数组分为了4份，分别是：

d[0],d[4],d[8]为一组，

d[1],d[5],d[9]为一组，

d[2],d[6],d[10]为一组，

d[3],d[7],d[11]为一组，

而i层循环需要对这4组中的其中一组执行插入排序。所以k的意义就是再遍历这4组，保证4组都被执行插入排序。

有人会说，这不是增加了两层循环吗？按理说时间效率应该是O(n^4)啊，怎么说时间效率突破了O(n^2)呢？

实际上这样的理解是不对的，因为最外层的两层循环并不以n为基数，而由于每次循环之后，数组实际上都会变得有序一点，所以导致j层的循环实际上不会循环太多次，特别是最后一次循环的时候，gap已经减为1，大多数人会觉得应该会变得跟插入排序一样的效率了吧，但是由于当gap为2的时候已经排过一轮序了，所以当gap=1时，j层循环只会在临近的两个元素之间比较，循环次数远远达不到n次。

希尔排序的时间复杂度计算目前来说还是一个比较困难的事，但是从执行结果上来看，它的最差效率不会超过O(n^3/2)，而且希尔排序的效率还与gap的选取有关，选择不同的gap效率就会不同。

归并排序

function merge(a1, a2) {
  const ret = []
  let i = 0, j = 0
  while (i < a1.length || j < a2.length) {
    ret.push(a1[i] < a2[j] ? a1[i++] : a2[j++]
  }
  while (i < a1.length) {
    ret.push(a1[i++])
  }
  while (j < a2.length) {
    ret.push(a2[j++])
  }
  return ret
}
function sort(data) {
  if (data.length < 2) {
    return data
  }
  const right = data.splice(Math.floor(data.length / 2))
  const left = data
  return merge(sort(data),sort(right))
}

归并排序是一种采用分治思路的排序算法，它的思路也很简单，两个有序数组的合并非常简单，只需要使用两个变量分别遍历两个数组然后将较小的插入到返回值中。

那么怎么得到两个有序数组呢？可以把当前的无序数组拆分到只剩两个元素，这时候再反过来进行数组的合并不就行了？

这一思想逻辑称为分治思想：将一个大问题拆解成较容易解决的小问题，通过解决小问题从而解决大问题。

堆排序

堆是一种使用数组构建的完全二叉树。这里稍微解释一下两个名词：数组构建和完全二叉树。

一般来说，我们接触到的二叉树都是使用链表构建的，但是其实也可以通过应用一些简单规则来在数组中构建二叉树。

堆的规则是当前下标的2n和2n+1保存比当前值小的元素，0下标弃之不用。

可以简单计算一下会发现正好是数组的每一位都能得到填充，假设当前的下标是1，则2n和2n+1分别是2和3，2的2n和2n+1是4，5；3的2n和2n+1是6，7。具体的证明过程就不在这里展开了。

完全二叉树是指，二叉树的叶子总是从左到右排列，且叶子层数不会超过2层。

好的，那么怎么利用堆来进行排序呢？

堆分为最大堆和最小堆，最大堆有一个特点，它的1下标是整个堆最大的元素，然后根据堆的规则，2和3元素小于1，4和5元素小于2，以此类推。

所以利用堆排序的方法就分为两步：

1. 构建最大堆
2. 删除最大堆的第一个元素，从代码角度来说，是交换最大堆的堆首和堆尾，然后将堆的长度减一。

function buildMaxHeap(data) {
  data.unshift(0)
  for (let i = Math.floor(data.length / 2); i >= 1; i--) {
      sink(data, i, data.length)
  }
}

function sink(arr, i, n) {
  let largest = i
  const left = 2*i
  const right = 2*i+1
  if (left < length && arr[left] > arr[largest]) {
    largest = left
  }
  if (right < length && arr[right] > arr[largest]) {
    largest = right
  }
  if (largest !== i) {
    swap(i, largest, arr)
    sink(arr, largest, length)
  }
}

function sort(data) {
  buildMaxHeap(data)
  for (let i = data.length - 1; i >= 1; i--) {
    swap(1, i, data)
    sink(data, 1, i)
  }
  data.shift()
  return data
}

简单解释一下：

buildMaxHeap是构建最大堆的方法，它先往列表的首位增加一个0下标，该下标不参与排序，但是却是堆规则必须存在的一个占位，这里填充什么都可以，由于我们是数字类型列表（在TS情况下），为了不出现类型判断冲突，所以我们填充一个0。

sink是堆的一个内置方法，它用来将当前位置与两个子节点比较，然后将较小的元素排在后面，以达到维持堆基本规则的作用。

sink方法还用了比较取巧的代码，首先比较left和largest，如果left元素大于largest元素，让largest等于left，然后再判断right和largest。

这里是编程中的一种抽象思维的体现，具体表现在：right只需要跟largest比较，而不需要管largest值是i还是left，代码抽象思维逻辑就是我只需要处理自己该处理的事，事情交到我手里之前是否正确由我前面的步骤去确定。

最后sink方法需要交换i和largest，然后继续向下递归。

sort方法就如我前面说的那样，分为两个步骤：构建最大堆和排序，排序完成之后删掉用来占位的0下标。

这里其实是一个原地排序算法，所以逻辑上是不需要返回data，但是也可以在排序之前复制一个副本用来排序，看具体需求。

快速排序

快速排序目前来说被认为是排序效率最好的排序方法，而且它本身的逻辑也极其简单。

function fastSort(data, start, end) {
  if (start >= end) { return }
  let target = data[start]
  let i = start, j = end + 1
  while(i<j) {
    // 寻找第一个大于target的左侧数
    while (data[++i]<=target) {
      if (i === end) { break }
    }
    // 寻找第一个小于target的右侧数
    while (data[--j]>target) {
      if (j === start) { break }
    }
    
    // 越界终止
    if （i > j) { break }
    // 交换左右数
    swap(i, j, data)
  }
  // 将target与j交换，
  swap(start, j, data)
  // 递归执行
  fastSort(data, start, j-1)
  fastSort(data, j+1, end)
}

function sort(data) {
  fastSort(data, 0, data.length-1)
}

快速排序的思想也是极其简单的，我们每次找一个数，使这个数左边的数都小于这个数，右侧的数都大于这个数。然后递归地处理所有数。

总结

冒泡排序循环对比临近的两个元素，将较大的放在两个元素中右边的位置；

选择排序每轮循环找一个最小值，将最小值放在未排序元素的最左边；

插入排序为当前元素在左侧已排序元素中找到一个合适的位置插入；

希尔排序是对插入排序的一个扩展，将步进距离从1变成gap；

归并排序是采用分治思路，将当前待排元素分为两组，待两组元素都排序完成之后，将两组元素归并到一起；

堆排序是利用堆的特点进行排序，最大堆的堆首总是最大元素，通过堆的sink方法可以维持堆的基本特性；

快速排序也是采用分治思想，在当前序列中选一个元素，然后将剩下的元素分为左右两个部分，将当前元素放在中间，然后递归执行左右两个子序列。

扩展

其实还有一些其他的排序算法，比如基于字符串的低位优先排序LSD和高位优先排序HSD，也是一种很取巧的思路。

我还写了一个网站用来以动画方式显示各种排序算法，有兴趣的可以去玩玩。