前端仔的“数据结构与算法”之路——排序

重点警告重点警告⚠️
排序我想至少作为程序员，是不会陌生。而且排序也是日常开发中必定会接触到。我们大多是直接调用语言的sort API，也许对其背后的逻辑，或是整个排序算法，熟悉程度不高的话。看完这篇，你心中肯定会有属于自己的理解。

常见的排序算法

这里引入一篇文章，感兴趣的可以细品。

十大经典排序算法（动图演示）

看图?，一图简单归纳一下。

乍一看，排序算法也太多了吧，怎么记怎么学？一个排序还用得上这么多种算法？
其实每个算法都有它自己的一些特性，都有它处理数据的逻辑。

只能由浅入深，或先把简单的常用的看懂看会，再去思考一些复杂的。
这里我个人主观感觉可以先分个优先学习顺序。

1. 冒泡排序
2. 插入排序
3. 选择排序
4. 归并排序
5. 快速排序
6. 桶排序
7. 计数排序
8. 基数排序
9. 堆排序
10. 希尔排序

认识、分析一种排序算法

排序算法有很多种，我们可以从多角度去看待它们，找找它们的共性或者特点。这样在后续的学习中记忆也会更加深刻。
可以从四个角度去思考一个排序算法。

• 这个算法的执行效率如果
• 这个算法的内存消耗怎样
• 这个算法的稳定性呢
• 这个算法的大概执行逻辑

带着四个问题去学习一种算法，会对它的理解更深刻。先一一解释一下这四个方向。

1、执行效率

时间复杂度分析（最好、最坏、平均）

从这三种情况去考虑一个算法的执行效率，才算得上相对客观的。因为其实从很大情况下，区分算法最直接的就是用它的平均时间复杂度去“简单”的判别它的效率。但是需要排序的数据都是多种可能，接近有序的，完全无序的。这些差异对算法的效率是有很大不同的。所以在考虑一种算法时，关键认识它的平均时间复杂度，其次了解和关心它的最好、最坏情况。

时间复杂度的系数、常数、低阶

在之前的学习中，我们得到的结论是，在分析时间复杂度的时候可以不考虑系数、常数、低阶这些情况，因为分析的是数据规模n的增长趋势对执行效率的影响。简单理解就是，可以说这个n很大的情况。但是在实际的工作或者软件应用中，我们直接进行的排序数据存在很多，较小数目的情况。处理几百几千上万的情况经常发送。所以我们就不得不考虑这些系数和常数、低阶。我们不一定得严格比较，但是最好是考虑其中即可。

比较次数、移动次数

排序算法是肯定离不开比较、交换或者移动的，只有进行这些逻辑判断或者数据操作，我们才能构建出有序的列表。算法的不同，它们的操作比较次数也存在差异，这个可以纳入我们理解的范畴。

2、内存消耗

就是相当于这个算法的空间复杂度。看看我们处理本身存储数据的空间外，还需要申请多少而外的空间辅助处理，才能完成排序。在排序算法中，会经常听到一个此“原地排序”，顾名思义，它需要申请的而外空间是常数，空间复杂度是O(1)。冒泡、插入、选择排序这三个算法就是属于原地排序。

3、稳定性

这点是尤为关键的一点，特别是在业务开发中，必须要考虑的因素之一。
怎么理解稳定性呢？排序的稳定性是指，如果数据在排序前，存在比较值相同的数据时，在排序过后它们的相对位置不发送改变。

[{age:10,name:'aa'},
 {age:13,name:'dd'},
 {age:10,name:'bb'},
 {age:15,name:'cc'},
...]
 
 [{age:10,name:'aa'},
 {age:10,name:'bb'},
 {age:13,name:'dd'},
 {age:15,name:'cc'},
...]

上面的例子中我们对数组以年龄进行排序，在排序过后我们希望同年龄的数据相对位置还是保持不变。这样我们在处理业务或逻辑中才能实现我们希望的效果。

4、实现逻辑

各类算法的实现逻辑也是我们需要学习了解的，哪怕不能手写直接还原，原理逻辑总要懂吧，不然都不好意思说你看过排序。排序算法怎么比较、怎么交换的关键逻辑还是必不可少的。

赶时间？先看看结论。

赶时间？如果想对排序算法有个最直观的感受，快进直接看统计图。

冒泡排序

逻辑分析

需要排序的数据，两两对比大小，交换位置，大的会被换到后方。执行第一遍冒泡后，最大的元素会被放置在最后面。反复执行n遍，所有的数据就排好了。
[a,b,c,d,e]

• a、b对比大小，假设a>b，则交换位置。第一步完成后[b,a,c,d,e]
• a、c对比大小，假设a>c，则交换位置。第二步完成后[b,c,a,d,e]
• ...
• 假设，a是数组中最大的元素，则第一轮结束后，a的位置会是末尾[b,c,d,e,a]
• 这样再执行4遍，数组就排序好了

代码实现

function sort (arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let s = false
    for (let k = 0; k < arr.length - i; k++) {
      if (k + 1 < arr.length - i && arr[k] > arr[k + 1]) {
        [arr[k], arr[k + 1]] = [arr[k + 1], arr[k]]
        s = true
      }
    }
    if (!s) break
  }
}

在代码中，其实我们每一遍，都会将一个最大的数放到最后方，所以每一次遍历其实可以少判断一个已经排在最后的数。而且如果在一次冒泡比较中，都没有执行交换位置。证明当前的排序已经是有序的了。可以直接退出循环，返回结果。

时间复杂度、稳定性、内存消耗

• 时间复杂度
  最好的情况下，我们冒泡第一遍，如果没有发生位置交换。证明已经是有序的数组。时间复杂度O(n)。
  最坏的情况下，数组是完全倒叙的，我们必须完成n遍冒泡，元素交换的次数是1累加到n-1（第一遍交换n-1次，第二遍交换n-2次），（n-1+1)*(n-1)/2。简化下来时间复杂度为O(n)。
  平均情况下，假设部分数字已经是有序的，交换次数比最坏情况下少一半。至少也是n*(n-1)/4，时间复杂度为O(n)。
• 稳定性
  如果我们遇到相同的数字是可以，选择不交换的，不要破坏原本相同数据的顺序。所以是可以做到稳定排序的。
• 内存消耗
  在js代码中我们可以看出，只而外申请了一个变量用于标示这次冒泡是否有交换。交换行为本身是在原数组上进行的，属于原地排序。空间复杂度为O(1)。

插入排序

逻辑分析

插入排序的实现逻辑和它名字几乎一样，将当前遍历到的数据插入适当的位置。插入排序的过程在理解时可以将数组分为两个段落。一个是已排序区间，第二个是未排序区间。每遍历一个元素将它插入已排序区间。
[a,b,c,d,e]
我们依然用这个序列表示

• 第一步，我们遍历第一个元素a，此时[a]本身就是已排序区间，只有它自己一个元素，[b,c,d,e]都是未排序区间。
• 第二步，遍历到b，如果b<a,则将b插入a之前，已排序区间变成[b，a]。
• 第三步，遍历到c，如果c>b,c<a，则c插入到已排序区间变成[b,c,a]
• ...
• 将所有元素遍历完成，已排序区间就是返回的结果。

在数组的操作中我们知道，插入删除数据，会涉及到数据的搬迁。当然在js语言中，我们不用处理真正内存上的数据搬迁，但是在这个排序中时，我们可以人为的处理元素在数组中位置的搬迁，这样我们可以更深刻的理解插入排序的逻辑过程。

代码实现

function insert (arr) {
  for (let i = 1; i < arr.length; i++) {
    // 如果小于前一个元素，证明需要插入
    if (arr[i] < arr[i - 1]) {
      // 待插入元素，已排序区间判断并插入
      let theI = arr[i]
      for (let k = i - 1; k >= 0; k--) {
        if (theI >= arr[k]) {
          // 待插入元素比当前元素大，执行插入
          arr[k + 1] = theI
          break
        } else {
          // 数据搬迁，当前元素比待插入元素大，后移一位，腾出空间
          arr[k + 1] = arr[k]
          if (k === 0) arr[k] = theI
        }
      }
    }
  }
}

时间复杂度、稳定性、内存消耗

• 时间复杂度
  最好情况下，数组是有序的，遍历过程中不需要插入操作，时间复杂度为O(n)。
  最坏情况下，数组完全倒叙，从第二个元素开始都要进行插入操作、数据搬迁。搬移的次数同理是，第二个元素时，搬迁一次，第三个元素时，搬迁两次。最后一个元素时搬迁n-1次。累加起来n*(n-1)/2，时间复杂度为O(n)。
  平均情况下，同理，初略感觉至少要搬迁一半的数据，进行插入吧。时间复杂度也是O(n)。
• 稳定性
  在插入操作中我们只在元素小于已排序区间中某个元素时才进行数据搬迁，对于数据大于或相等的情况，直接插入其后方，这样可以维持相等数据的相对顺序。所以它是稳定排序。
• 内存消耗
  同样的，我们处理了数据搬迁，只而外的申请了一个对比变量，它属于原地排序。它的空间复杂度为O(1)。

希尔排序

希尔排序其实是插入排序的另一种操作，比插入更高效，但同样的带来了不稳定性。所以我们一起来了解它。

逻辑分析

希尔排序，其实是通过一个“步长”，来将数组划分开来，对划分后子集的数据进行插入排序。执行完第一遍后，通过公式去减少这个“步长”，数组又被重新划分，重新将子集插入排序。一遍又一遍。直到“步长”为1时，数组不会被划分，进行最后一次插入排序，得到最终结果。
为什么兜兜转转，划分数组来做这些操作呢，其目的都是为了更好的将乱序的数组调整的再有序一些，这样最后一遍插入排序的效率就能大大提高。
怎么理解这个“步长”呢，关键也是这个步长的变化，直接影响到排序到效率。
**[a,b,c,d,e]**
假设我们初始化步长为2，则原数据会被这样划分,下标每增加2的会被划分成一个子集。
[a,c,e]、[b,d]这样下标0，2，4和1，3分别被划分成两个子集。对这两个子集分别进行插入排序。
然后改变步长，为1。这样子集就是所有元素，然后再对上一步的结果的所有元素进行插入排序，得到结果。
是的它不好理解，多看看不同的文章和代码，这样才能转化成自己的思维。去百度吧，去掘金搜。

代码实现

function shell (arr) {
  let step = Math.floor(arr.length / 2)
  while (step > 0) {
    for (let i = 0; i < arr.length; i++) {
      // 如果小于前一步长元素，证明需要插入
      if (i - step >= 0 && arr[i] < arr[i - step]) {
        // 待插入元素
        let theI = arr[i]
        for (let k = i - step; k >= 0; k -= step) {
          // 插入
          if (theI >= arr[k]) {
            arr[k + step] = theI
            break
          } else {
            // 数据搬迁，当前元素比待插入元素大，后移一个步长，腾出空间
            arr[k + step] = arr[k]
            if (k - step <= 0) arr[k] = theI
          }
        }
      }
    }
    // 步长减小
    step = Math.floor(step / 2)
  }
}

时间复杂度、稳定性、内存消耗

• 时间复杂度
  最好情况下，同插入排序一样，有序的数组，希尔只是多了几次步长变化的循环。时间复杂度也是O(n)。
  最坏情况下，数组是逆序的，需要搬迁插入的次数是一样的，时间复杂度为O(n)。
  平均情况下
  实话说，这种情况下极其难分析。
  希尔排序，可以考虑看看百科。
  它的时间复杂度其实和它步长的变化逻辑相关，结论的答案是O(n)。
• 稳定性
  在它通过步长将数组划分成不同子集时，它已经不稳定了。子集的插入排序只能保证目前这个子集是稳定的，但是随着步长的改变。子集和子集产生交集，就无法保证稳定排序了。
• 内存消耗
  看代码就可以感受到了，原地排序，只有一个变量申请用于步长。所以空间复杂度为O(1)。

最后我们再看看百科的阐述，加深印象。

优劣

选择排序

选择排序和插入排序的逻辑差不多。是选择好后再进行插入。而插入排序是，插入时按逻辑插入。
但是它其实很少出现在我们的视野中，为什么呢？
它其实是不稳定的排序，在时间复杂度和冒泡排序，插入排序一样的情况下，失去了优势。（而且它时间效率在相对有序的数组中并没有提高）

逻辑分析

在排序的过程中，把原数组分为两个区间，已排序，未排序。
每一次在未排序区间选择最小的一个元素，插入已排序区间末尾。贼好理解。

代码实现

// 选择排序
function select (arr) {
  let tail = 0
  while (tail <= arr.length - 1) {
    let min = tail
    for (let i = tail; i < arr.length; i++) {
      min = arr[min] < arr[i] ? min : i
    }
    [arr[tail], arr[min]] = [arr[min], arr[tail]]
    tail++
  }
}

时间复杂度、稳定性、内存消耗

• 时间复杂度
  由于它的逻辑是比较未排序区间，获取最小的元素进行插入。所以即使数组本身就是有序的，它一样会跑完全部逻辑。所以它三种情况下都是O(n)。
• 稳定性
  由于在选择元素后，会和已排序后的节点交换位置，这样可能会引起相等元素的位置变化，所以它是不稳定的。
• 内存消耗
  代码可知，没有而外申请与数据相当的空间，所以空间复杂度O(1)。

归并排序

归并排序是建立在归并操作上的一种有效，稳定的排序算法。是使用分治法的一个典型应用。

逻辑分析

主要逻辑在理解归并操作上。可以简单的分为3个点。

• 将需要排序的数组一分为二。
• 继续用归并操作处理分割后的两份数组，处理完成后，两份数组都是有序的。
• 再合并两个已经有序的数组。

理解的困难点在中间，怎么将分割后的数组变成有序的？
那我们就只能继续分割，直到被分割后，左右两边最多只有一个元素时。你就能确定顺序了。
然后两两合并，第一次合并，你可以获得两个元素的有序排列。
第二次合并你可以获得四个元素的有序排列。
直到合并完全部元素，归并排序结束。

代码实现

我们先用伪代码理解，怎么还原上述说的逻辑呢？

// 归并排序
// 传入数组，开始下标，结束下标
function sort(arr,s,e){
  // 数组分割，取其中间
  let mid = Math.floor((s + e) / 2)
  // 左右分割，获得左右都是已排好序的数组
  let left = sort()
  let right = sort()
  // 合并左右数组返回
  return merge(left,right)
}
function merge(l,r){
  // 合并两个有序数组
}

首先理解伪代码，这样下次我们使用归并算法时，可以先想起伪代码的逻辑框架，接着我们完善一下边界情况就可以了。先直接看完整代码?。看完就知道要注意完善的点拉。

function sort (arr, s, e) {
  // 边界情况
  if (s > e) return []
  if (s === e) return [arr[s]]
  let mid = Math.floor((s + e) / 2)
  let left = sort(arr, s, mid)
  let right = sort(arr, mid + 1, e)
  return merge(left, right)
}
function merge (l, r) {
  // 合并两个有序数组
  let arr = []
  while (l.length !== 0 && r.length !== 0) {
    if (l[0] <= r[0]) arr.push(l.shift())
    else arr.push(r.shift())
  }
  if (l.length === 0 || r.length === 0) arr = [...arr, ...l.length === 0 ? r : l]
  return arr
}

时间复杂度、稳定性、内存消耗

• 时间复杂度
  假设归并n数组长度所需要的时间为T(n)，分割一个元素的时间为C
  则T(n)为分割数组操作假设合并操作组成（分割操作有左右数组时间相加）：T(n) = 2*T(n/2) + n； n>1
  

T(n) = 2*T(n/2) + n
     = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n
     = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n
     = 8*(2*T(n/16) + n/8) + 3*n = 16*T(n/16) + 4*n
     ......
     = 2^k * T(n/2^k) + k * n
     ......

当T(n/2^k)为1时，我们不再继续分割。这时k=log2n。将k带入上面公式。T(n)=Cn+nlog2n
所以它的时间复杂度是O(nlogn)
它在最好最坏的时间操作逻辑是一样的，没有省略的空间。

• 稳定性
  在合并左右数组时，如果遇到相同的元素，我们确保左数组的元素先插入即可，所以它是稳定排序。
• 内存消耗
  很明显，在看代码时我们发现，在合并左右数组时，我们多申请了一个数组用来保存合并结果，所以它是有多的内存消耗的。如果我们操作的是链表，这个内存消耗还能避免，直接原地归并两个链表。so，O(n)

快速排序

快速排序，我们简单称为，快排。它与归并排序有类似的地方，都是用分治、递归的思想去解决整天排序的问题。

逻辑分析

怎么实现呢？它通过找到一个区分点，将序列的元素依次与区分点对比，小的放置在区分点左边，大的放置在右边。
接着对左右两边，再次用它们新的区分点操作。直到左右子集都只剩一个元素的时候。所有元素就是有序的。关键在于区分点的选择，对比时的交换操作。它是可以实现原地排序的一种算法。区分点的选择也影响了排序的效率，如果区分点能把当前序列划分为元素长度差不多的左右两个子集。它的效率是最高的。
简单点，可以之间取任意一个元素作为区分点。或者也可以取三、四个元素的中间元素作为区分点。
快速排序的实现分为2大点。

• 在两个下标之间找到区分点、pivot
• 依据这个区分点，将两个下标之间的元素划分为左右两个子集

反复如此，直到左右子集只剩一个元素。

代码实现

我们还是先写伪代码，找找框架

// 传入数组，开始下标，结束下标	
function sort(arr,s,e){
	if(s>=e)return 
  // 找到区分点，并分割好数组，返回区分点最终下标
  let p = partition(arr,s,e)
  sort(arr,s,p-1)
  sort(arr,p+1,e)
}
function partition(arr,s,e){
  // 找到区分点我们可以，先任意取一个
  let pivot = arr[e]
  // 接着就是关键的原地交换，怎么把s到e间的元素放置成左右两边
}

伪代码的思路我们已经有了，接下来就是补充整个代码，完善边界情况即可。

// 传入数组，开始下标，结束下标	
function sort (arr, s, e) {
  if (s >= e) return
  // 找到区分点，并分割好数组，返回区分点最终下标
  let p = partition(arr, s, e)
  sort(arr, s, p - 1)
  sort(arr, p + 1, e)
}
function partition (arr, s, e) {
  // 找到区分点我们可以，先任意取一个
  let pivot = arr[e]
  // 接着就是关键的原地交换，怎么把s到e间的元素放置成左右两边
  // 定义j，作为左边小于区分点的起始下标
  let j = s
  for (let i = s; i <= e; i++) {
    if (arr[i] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
      j++
    }
  }
  // 区分点元素与最后的j置换
  [arr[j], arr[e]] = [arr[e], arr[j]]
  return j
}

时间复杂度、稳定性、内存消耗

• 时间复杂度
  快排也是利用递归的思路解决的，时间复杂度也可以参考递归公式。其实和归并排序一样。在区分点能将序列划分成左右长度相等的子集情况下是O(nlogn)。
  当然最坏情况下，比如我们的区分点恰好是当前序列的最大值时，时间复杂度就会退化成O(n)。
• 稳定性
  在操作过程中，我们的交换操作是可能影响到相对稳定性的，**比如[1,4,3,6,4,2]。我们选择3作为区分点时，4和2这两个元素是会发生交换的，这就影响了相对稳定性。
• 内存消耗

堆排序

什么堆？

在理解堆排序前，我们先了解一下什么是堆。

堆可以理解是一种特殊的树结构，满足以下两点的树，就可以称为堆。

1. 是一个完全二叉树。
2. 堆中每个节点的值需要大于等于（或小于等于）其子节点的值。

什么是完全二叉树？
除了最后一层，其他的层的节点都是满的。而且最后一层，节点从左到右排列。?图就是一个完全二叉树。
红色数字表示堆节点的顺序。

知道堆了，那我们如果存储这个堆呢？
完全二叉树，比较适合用数组来存储，所以我们这里的堆就用数组来存储。
[0,10,9,8,7,6,5,4,3]
为什么数组第一个元素是0呢？其实是为了配合我们堆的节点顺序来的。第一个节点10，就是数组下标1的元素。第二个节点9，就是数组下标2的元素。

而且通过二叉树和数组我们可以得到以下结论：
父节点的序号是i
子节点的序号是i2和i2+1⚠️⚠️
这个结论特别关键，它是我们建立堆，和堆排序的重点。

如果实现一个堆？

有了原始数组的数据，我们就可以建立一个堆。

• 那肯定得有堆的插入操作
• 堆顶的删除操作

1、堆的插入操作

在每一个元素插入的过程中，我们肯定要维护好堆的两个特性，完全二叉树，节点要大于等于（或小于等于）两个子节点。
所以每插入一个节点元素，我们要根据它的下标判断它与父节点的大小关系，符合的话就不用处理。不符合则需要交换位置。
假设我们要维护一个大顶堆。

我们每插入一个数据都要，维护好堆的关系，其实就是不断的判断它与父节点的大小。
?代码的操作，我们称为至下而上的维护（判断它与父节点的关系）。

class Heap {
  constructor(num) {
    // 堆最大元素数量
    this.max = num
    // 数组存储堆数据
    this.arr = [0]
    this.count = 0
  }
  insert (el) {
    if (this.max <= this.count) return this.arr
    this.count++
    this.arr[this.count] = el
    let i = this.count
    while (true) {
      // 判断当前节点与父节点的大小关系，不符合就交换，然后继续判断
      if (i / 2 >= 1) {
        if (i % 2 === 0 && this.arr[i] > this.arr[i / 2]) {
          [this.arr[i], this.arr[i / 2]] = [this.arr[i / 2], this.arr[i]]
          i = i / 2
        } else if (i % 2 === 1 && this.arr[i] > this.arr[(i - 1) / 2]) {
          [this.arr[i], this.arr[(i - 1) / 2]] = [this.arr[(i - 1) / 2], this.arr[i]]
          i = (i - 1) / 2
        } else break
      } else break
    }
    return this.arr
  }
}

2、堆顶的删除操作

堆顶元素肯定是最大或者，最小的。假设我们现在维护的是大顶堆。则堆顶元素肯定是最大的。
当我们删除堆顶元素时，就需要将第二大的元素移动到堆顶，而第二大的元素肯定是子节点的元素。以此类推。从上到下，我们就又可以维护好一个堆。
这里我们可以有一个小技巧，当删除堆顶元素时，我们可以拿堆最后的元素插入到堆顶，然后再开始维护父子节点关系。这样就不会造成堆的空洞。
?可以看一下代码，我们称为至上而下的维护（判断它与子节点的关系）。

function removeTop (arr) {
  // 删除堆顶，用尾部数据替换，从堆顶开始维护
  arr[1] = arr.pop()
  heapify(arr)
  console.log(arr)
}
function heapify (arr) {
  let len = arr.length - 1
  let i = 1
  while (true) {
    let change = i
    if (i * 2 <= len && arr[i] < arr[i * 2]) change = i * 2
    if (i * 2 + 1 <= len && arr[change] < arr[i * 2 + 1]) change = i * 2 + 1
    // 父节点满足两个子节点的关系
    if (change === i) break
    [arr[i], arr[change]] = [arr[change], arr[i]]
    i = change
  }
}

其实这两种操作都是一个堆化，维护堆的过程，只不过上下顺序不同而已。

3、建立堆

（想象成一个金字塔，从塔尖开始一层一层的维护好，保证维护过的层满足堆。或者从底部一层一层的向上维护，保证维护过的层满足堆）
要么从堆顶元素开始向后遍历，对于每个节点至下而上去维护建立。
要么从最后一个父节点开始向前遍历，对于每个节点至上而下的维护建立。

从原始数据获取数组，我们可以原地堆化它，这里有个技巧。

如图，假设从原始数据那获取8个节点。其实我们要堆化的节点只有红色的部分。比如我们采用从底层开始堆化，对于每个节点至上而下的维护（判断它与子节点的关系）。这种操作，叶子节点是不需要判断的，因为它没有子节点。
所以我们可以从n/2或(n-1)/2开始一个个向前遍历去堆化。
看?代码～～

function build (arr) {
  let len = arr.length - 1
  let start = len % 2 === 0 ? len / 2 : (len - 1) / 2
  for (let i = start; i >= 1; i--) {
    heapify(arr, i, len)
  }
}
function heapify (arr, index, end) {
  // 堆化，至上而下
  let len = end
  let i = index
  while (true) {
    let change = i
    if (i * 2 <= len && arr[i] < arr[i * 2]) change = i * 2
    if (i * 2 + 1 <= len && arr[change] < arr[i * 2 + 1]) change = i * 2 + 1
    // 父节点满足两个子节点的关系
    if (change === i) break
    [arr[i], arr[change]] = [arr[change], arr[i]]
    i = change
  }
}

好了，这里已经大概理解了一下堆的建立和维护。我们怎么利用堆来排序呢？

排序

其实维护一个堆，我们能确保的肯定是，堆顶元素最大或者最小。
利用这个点，我们可以反复用堆顶元素与尾部元素交换这样最大值的下标就是n，再重新堆化，又一次取堆顶元素与n-1元素交换，反复如此，从最后一个元素到第一个元素。这样就能获得增序的排列了。

结合堆顶删除操作的逻辑，我们完善一下整个排序代码。

// 堆顶元素的删除
const heap = [0, 6, 4, 2, 5, 3, 1, 15, 8]
function removeTop (arr, end) {
  // 删除堆顶，用尾部数据替换，从堆顶开始维护
  [arr[1], arr[end]] = [arr[end], arr[1]]
  heapify(arr, 1, end - 1)
}
function heapify (arr, index, end) {
  // 堆化，至上而下
  let len = end
  let i = index
  while (true) {
    let change = i
    if (i * 2 <= len && arr[i] < arr[i * 2]) change = i * 2
    if (i * 2 + 1 <= len && arr[change] < arr[i * 2 + 1]) change = i * 2 + 1
    // 父节点满足两个子节点的关系
    if (change === i) break
    [arr[i], arr[change]] = [arr[change], arr[i]]
    i = change
  }
}
// 堆排序
function heapSort (arr) {
  // 建立堆，从最后一个父节点开始，至上而下，一层一层向上堆化
  let len = arr.length - 1
  let start = len % 2 === 0 ? len / 2 : (len - 1) / 2
  for (let i = start; i >= 1; i--) {
    heapify(arr, i, len)
  }
  // 置换堆顶元素、再次堆化
  for (let i = arr.length - 1; i >= 1; i--) {
    removeTop(arr, i)
  }
  return arr
}
heapSort(heap)

分析分析

时间复杂度

堆排序的过程可以分为两步，这两个过程都包含了节点堆化的过程。我们主要考量每个过程节点堆化的次数。就大概知道时间复杂度了。

• 建堆
• 排序

每个节点堆化的时间复杂度大概是O(logn)
建堆需要堆化n/2-1个节点，所以建堆的时间复杂度应该是两个的乘积。但是其实，每个节点的堆化时间是与节点高度成正比的。这里的计算稍微有点多，我偷懒先略过。
结论是建堆的时间复杂度是O(n)
排序的时间复杂度，我们理一理。排序是需要遍历整个数组，利用删除堆顶操作。堆顶的堆化时间复杂度自然是O(logn)。
所以排序的时间复杂度是
O(n*logn)
堆排序的时间复杂度为O((nlogn)+n)~~~~~~~~O(nlogn)

内存消耗

依据代码可以看出来，整天的操作基本都是在数组原地操作的。所以空间复杂度是O(1)

稳定性

堆化和排序堆过程中已经破坏了相对顺序。所以它是不稳定的。

桶排序

桶排序它的意义在于，在适当的情况下，排序的时间复杂度是可以优化到O(n)的。
怎么说？

逻辑分析

主要是将数据分割到几个【有序】的桶中。桶与桶之间有天然的顺序关系，在桶中的数据，我们可以才有快排、归并、堆排序等将桶内数据有序化。接着我们依次按桶取出数据，就形成完成的有序数据了。
它是怎么将时间复杂度优化到O(n)？
假设有n个数据，有m个桶。情况好的时候将数据平均分配到每个桶中，每个桶有k=n/m个元素。每个桶的排序时间复杂度为O(k*logk)，m个桶则整体的时间复杂度是O(mklogk)~~~~~O(n*logk)
当我们的桶数量很接近总数n时，k就会越来越小，接近1，这时logk就是一个很小的常量。我们可以理解为优化到了O(n)的。

当然它表现的是不错的，但是它的前提条件也很重要，影响了它整天的效率。

• 能将数据天然的分割在几个有序的桶中。
• 分配在桶中的数据越平均越好。

还有一种桶排序的应用场景，外部排序。
比如数据存储在外部磁盘中，数据量很大，内存有限，无法一次性加载到内存中进行排序。

计数排序

它有点类似与桶排序，而且它的桶是能划分的更清晰明了的。
比如高考分数排序。分数肯定分布在0分到750分之间（部分区域的分数）。这样我们可以之间分成751个桶（二维数组，长度为751），直接遍历考生的分数插入相应的桶中，最后展开所有桶就得到排序结果了。
当然还有很多计数排序的计算技巧。当我理解更多的是一种解决思路，理解理解会更好。
当然它也是有些局限性的

• 分割桶的数量最好是一个可见的常量，肯定不能比总数据量大，这样就失去意义了。
• 排序的元素要合适的插入到数组指定的下标中，比如分数，1分就插入数组下标1的数组里。

基数排序

我们基于一个问题来看待基数排序。比如有1万个手机号，我们需要按大小排序。
快排和归并排序直接上可以做到O(nlogn)。桶排序计数排序呢？手机号有11位，是一个很大的数字，桶和计数都不好划分。这里可以考虑换种思路，基数排序。可以优化到O(n)。
手机号可以分为11位。我们可以按位排序，比如a手机号的第二位是3，b手机号的第二位是8。其实后续的数字我们就不需要考虑了。
整体排序逻辑，我们可以利用稳定排序算法，对手机号每一位排序，这样经历过11次排序就得到全部有序的结果了。
比如第一位排序，我们可以利用桶排序，分10个桶，0～9。所有手机号只按第一位来归并排序。依次类推排序11次。
桶排序情况号是可以去到O(n),排序11次，时间复杂度O(11*n)。所以结果还是不错的。

这里注意三点

• 数据适合按位去排序，位有天然的递进关系
• 当对每位排序时，要适合采用桶排序或者计数排序，这样每位排序的时间复杂度才能去到O(n)
• 按位排序，位的数量是常数

下一趴～～～！

下一篇会汇总一些遇到的leetcode真题，进入排序的实战操作！！！