概览

1. 插入排序

算法实现

描述
插入排序，一般也被称为直接插入排序。对于少量元素的排序，它是一个有效的算法 。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。
图例


思路
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。
代码**

// 插入排序1
function insertSort(nums) {
  const len = nums.length;
  for (let i = 1; i < len; i++) {
    let current = nums[i];
    let preindex = i-1;
    while (preindex >= 0 && nums[preindex] > current) {
      nums[preindex+1] = nums[preindex];
      preindex -= 1
    }
    nums[preindex+1] = current;
  }
  return nums;
}
// 插入排序2
function insertSort2(arr) {
  for (var i = 1; i < arr.length; i++) {
    var temp = arr[i];
    for (var j = i - 1; j >= 0 && arr[j] > temp; j--) {
      arr[j+1] = arr[j];
    }
    arr[j+1] = temp;
  }
  return arr;
}

算法性能

| Name | Best | Average | Worst | Memory | Stable | Comments | | Insertion sort | n | n | n | 1 | Yes | | | —- | —- | —- | —- | —- | —- | —- |

在插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较N- 1次，时间复杂度为O(N)。
最坏的情况是待排序数组是逆序的，此时需要比较次数最多，总次数记为：1+2+3+…+N-1，所以，插入排序最坏情况下的时间复杂度为O(N^2)。
平均来说，A[1..j-1]中的一半元素小于A[j]，一半元素大于A[j]。插入排序在平均情况运行时间与最坏情况运行时间一样，是输入规模的二次函数。
插入排序最坏情况运行时间和平均情况运行时间都为O(n2)。
通常，插入排序呈现出二次排序算法中的最佳性能。
对于具有较少元素（如n<=15）的列表来说，二次算法十分有效。
在列表已被排序时，插入排序是线性算法O(n)。
在列表“近似排序”时，插入排序仍然是线性算法。
在列表的许多元素已位于正确的位置上时，就会出现“近似排序”的条件。
通过使用O(nlog2n)效率的算法（如快速排序）对数组进行部分排序，
然后再进行选择排序，某些高级的排序算法就是这样实现的。
从上述分析中可以看出，直接插入排序适合记录数比较少、给定序列基本有序的情况。
稳定性分析
如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，即它们的位置保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的；如果排序后，数据的相对次序发生了变化，则该算法是不稳定的。关键词相同的数据元素将保持原有位置不变，所以该算法是稳定的。

2. 冒泡排序

算法实现

思路
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

算法原理

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法描述

// 冒泡排序1
function bubbleSort(arr){
  const length = arr.length;
  // 注意这里i > 0
  for (let i = length; i > 0; i--) {
    // j是0 ... i - 1，比较的是j 和 j + 1相邻元素
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j+1], arr[j]] = [arr[j], arr[j+1]];
      }
    }
  }
  return arr;
}
// 带标记位的冒泡排序
function bubbleSort2(arr) {
  const length = arr.length;
  for (let i = length; i > 0; i--) {
    let flag = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j+1]] = [arr[j + 1], arr[j]];
        flag = false;
      }
      if (flag) break;
    }
  }
  return arr;
}

算法性能

| Name | Best | Average | Worst | Memory | Stable | Comments | | Bubble sort | n | n | n | 1 | Yes | | | —- | —- | —- | —- | —- | —- | —- |

时间复杂度
若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数和记录移动次数均达到最小值：，。
所以，冒泡排序最好的时间复杂度为 O(n)。
若初始文件是反序的，需要进行 n-1 趟排序。每趟排序要进行 n-i 次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

冒泡排序的最坏时间复杂度为 O(n)
综上，因此冒泡排序总的平均时间复杂度为O(n) 。
稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

3. 选择排序

算法实现

描述
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。
原理

原理**

• 初始状态：无序区为R[0..n-1]（共n个元素），有序区为空。
• 第1趟排序，设置一个变量i，让i从0至n-2循环的同时，在对比数组中元素i跟元素i+1的大小，如果R[i+1]比R[i]小，则用一个变量k来记住他的位置（即k=i+1）。等到循环结束的时候，我们应该找到了R中最小的那个数的位置了。然后进行判断，如果这个最小元素的不是R的第一个元素，就让第一个元素跟他交换一下值，使R[0..0]和R[1..n-1]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
• 第i趟排序，第i趟排序开始时，当前有序区和无序区分别为R[0..i-1]和R[i..n-1]。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[0..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

代码

function selectSort(arr){
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
    }
  }
  return arr;
}

算法性能

| Name | Best | Average | Worst | Memory | Stable | Comments | | Selection sort | n | n | n | 1 | No | | | —- | —- | —- | —- | —- | —- | —- |

时间复杂度
选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+…+1=n(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。
稳定性
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个*不稳定的排序算法。

4. 归并排序

算法实现

描述
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并操作
归并操作，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
如　设有数列{6，202，100，301，38，8，1}
初始状态：6,202,100,301,38,8,1
第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；
第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；
第三次归并后：{1,6,8,38,100,202,301},比较次数：4；
总的比较次数为：3+4+4=11；
原理


归并操作的工作原理如下：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
代码**

• 递归版

  function　merge(left, right){
    var　result=[];
    while(left.length>0 && right.length>0){
        if(left[0]<right[0]){
        /*shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值。*/
            result.push(left.shift());
        }else{
            result.push(right.shift());
        }
    }
    return　result.concat(left).concat(right);
  }
  function　mergeSort(items){
    if(items.length == 1){
        return　items;
  }
  var　middle = Math.floor(items.length/2),
    left = items.slice(0, middle),
    right = items.slice(middle);
    return　merge(mergeSort(left), mergeSort(right));
  }
  

• 非递归版

  // 归并排序非递归版
  function mergeSort3(arr) {
  for (let gap = 1; gap < arr.length; gap = gap * 2) {
  
    //归并gap长度的两个相邻子表
    let i = 0;
    for (i = 0; i + 2*gap - 1 < arr.length; i = i + 2*gap) {
      merge3(arr, i, (i + gap - 1), i + 2 * gap - 1);
    }
    //余下两个子表，后者长度小于gap
    if (i + gap - 1 < arr.length) {
      merge3(arr, i, (i + gap - 1), arr.length - 1);
      // console.log(i, (i + gap - 1), arr.length - 1)
    }
  }
  }
  function merge3(arr, low, mid, high) {
  let i = low;
  let j = mid + 1;
  let k = 0;
  let arr2 = new Array();
  // 扫描第一段和第二段序列，直到有一个扫描结束
  while (i <= mid && j <= high) {
    // 判断第一段和第二段取出的数哪个更小，将其存入合并序列，并继续向下扫描
    if (arr[i] < arr[j]) {
      arr2[k++] = arr[i++];
    } else {
      arr2[k++] = arr[j++];
    }
  }
  // 若第一段序列还没扫描完，将其全部复制到合并序列
    while (i <= mid) {
    arr2[k++] = arr[i++];
  }
  // 若第二段序列还没扫描完，将其全部复制到合并序列
  while (j <= high) {
    arr2[k++] = arr[j++];
  }
  // 将合并序列复制到原始序列中
    for (k = 0, i = low; i <= high; i++ , k++) {
    arr[i] = arr2[k];
  }
  }
  

  算法性能

  | Name | Best | Average | Worst | Memory | Stable | Comments | | Merge sort | n log(n) | n log(n) | n log(n) | n | Yes | | | —- | —- | —- | —- | —- | —- | —- |

归并排序比较占用内存，但却是一种效率高且稳定的算法。
改进归并排序在归并时先判断前段序列的最大值与后段序列最小值的关系再确定是否进行复制比较。如果前段序列的最大值小于等于后段序列最小值，则说明序列可以直接形成一段有序序列不需要再归并，反之则需要。所以在序列本身有序的情况下时间复杂度可以降至O(n)。
TimSort可以说是归并排序的终极优化版本，主要思想就是检测序列中的天然有序子段（若检测到严格降序子段则翻转序列为升序子段）。在最好情况下无论升序还是降序都可以使时间复杂度降至为O(n)，具有很强的自适应性。

5. 快速排序

算法实现

描述
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
原理
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选

用数组的第一个数作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j—)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
优化

• 用插入排序去处理小的子数组更好。插入排序可以用于这种小数组的调用（例如：长度小于门限t的时候使用插入排序）
• 通常采用“三者值取中”方法，即比较H->r[low].key、H->r[high].key与H->r[(low+high)/2].key，取三者中关键字为中值的元素为中间数。
• 三路快排

先说说二路快排，也就是普通的快速排序。
排序的原理就是在待排序的数组中随机选择一个数key，把小于key的数统统放着key的左边，那么大于等于key的数都丢在右边了，得到一个新的数列：[……] < key <= [……]
这样一来key实际上已经排到了正确的位置上了，我们只需要对左右两边剩下的数进行相同的操作，最后就能得到一个排序好的数列。
三路快排是为了应对数列中有大量的重复数据，为了避免对重复数据进行反复排序，将每次排列的数列分成三部分：[……] < [key,key,…,key] < [……]
原理就是小的丢左边，大的数丢右边，剩下在中间的数就是与key相等的数了。这样处理后，再对key两边的数列进行排列，可以大大加快排列速度。

代码

• 递归原地修改-标准版

  function quickSort(arr, low, high) {
  if (low < high) {
    let pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex-1);
    quickSort(arr, pivotIndex+1, high);
    return arr;
  }
  function partition(arr, low, high) {
    // let pivot = arr[low];
    // let randomIndex = Math.floor(Math.random()*(high - low + 1) + low);
    // [arr[low], arr[randomIndex]] = [arr[randomIndex], arr[low]];
    let pivot = arr[low];
    while (low < high) {
      while (low < high && arr[high] >= pivot) {
        high--;
      }
      arr[low] = arr[high];
      while (low < high && arr[low] <= pivot) {
        low++;
      }
      arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
  }
  }
  

• 修改原数组，相等元素居中-优化版

  function quickSort3(originalArray) {
  const array = [...originalArray];
  if (array.length < 1) {
    return array;
  }
  const leftArray = [];
  const rightArray = [];
  
  const pivotElement = array.shift();
  const centerArray = [pivotElement];
  
  while (array.length) {
    const currentElement = array.shift();
    if (currentElement === pivotElement) {
      centerArray.push(currentElement);
    } else if (currentElement < pivotElement) {
      leftArray.push(currentElement);
    } else {
      rightArray.push(currentElement);
    }
  }
  const leftArraySorted = quickSort3(leftArray);
  const rightArraySorted = quickSort3(rightArray);
  return leftArraySorted.concat(centerArray, rightArraySorted);
  }
  

• 原地修改第二版-partition不一样 ```javascript function quickSort(array) { function partition(array, left, right) { let index = left; let pivot = array[right]; for (let i = left; i <= right; i++) {

  if (array[i] < pivot) {
    [array[i], array[index]] = [array[index], array[i]];
    index++;
  }
  

  } [array[right], array[index]] = [array[index], array[right]]; return index; } function sort(array, left, right) { if (left > right) return; const pivotIndex = partition(array, left, right); sort(array, left, pivotIndex - 1); sort(array, pivotIndex + 1, right); } sort(array, 0, array.length - 1); return array; }

const arr = [5, 7, 11, 56, 12, 1, 9]; console.log(quickSort(arr)); console.log(arr);

- 迭代版-使用栈
```javascript
// 快速排序迭代版
function quickSort6(array, left, right) {
  function partition(arr, low, high) {
    let pivot = arr[low];
    while (low < high) {
      while (low < high && arr[high] >= pivot) {
        high--;
      }
      arr[low] = arr[high];
      while (low < high && arr[low] <= pivot) {
        low++;
      }
      arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
  }
  let sta = [];
  sta.push([left, right]);
  let low, high;
  while (sta.length) {
    [low, high] = sta.pop();
    console.log(low, high);
    if (low < high) {
      let pivotIndex = partition(array, low, high);
      sta.push([low, pivotIndex - 1]);
      sta.push([pivotIndex + 1, high]);
    }
  }
  return array;
}

const arr6 = [5, 7, 11, 56, 12, 1, 9];
console.log("迭代版：", quickSort6(arr6, 0, arr6.length-1));

• 一行版-优秀版

  function quickSort4(arr) {
  return arr.length <=1 ? arr : quickSort(arr.slice(1).filter(v=> v<arr[0])).concat(arr[0],quickSort(arr.slice(1).filter(v=>v>=arr[0])))
  }
  

• 三路快排-加强版

  function quickSort(array, start, end) {
  if (start > end) {
    return;
  }
  let pivot = array[start];
  let i = j = start;
  let k = end;
  while (i <= k) {
    if (array[i] < pivot) {
      [array[i], array[j]] = [array[j], array[i]];
      j++;
      i++;
    } else if(array[i] > pivot) {
      [array[i], array[k]] = [array[k], array[i]];
      k--;
    } else {
      i++;
    }
  }
  quickSort(array, start, j-1);
  quickSort(array, k+1, end);
  return array;
  }
  

  Python代码： ```python n = int(input()) list1 = list(map(int, input().split()))

def quick_sort(list1, low, high): sta = []; sta.append((low, high)) while sta: low, high = sta.pop() if low < high: mid = partition(list1, low, high) sta.append((low, mid-1)) sta.append((mid+1, high)) return list1 def partition(list1, low, high): i = low pivot = list1[low] for j in range(low+1, high+1): if list1[j] < pivot: i += 1 list1[i], list1[j] = list1[j], list1[i] list1[i], list1[low] = list1[low], list1[i] return i

if name==”main“: low = 0 high = len(list1) - 1 quick_sort(list1, low, high) print(“ “.join(list(map(str, list1))))

Python三路快排：
```python
n = int(input())
list1 = list(map(int, input().split()))

def quick_sort(list1, low, high):
    if low >= high:
       return 
    pivot = list1[low]
    i, j = low, low
    k = high
    while i <= k:
        if list1[i] < pivot:
           list1[i], list1[j] = list1[j], list1[i]
           i += 1
           j += 1

        elif list1[i] > pivot:
            list1[i], list1[k] = list1[k], list1[i]
            k -= 1
        else:
            i += 1
    quick_sort(list1, low, j - 1)
    quick_sort(list1, k + 1, high)



if __name__=="__main__":
    low = 0
    high = len(list1) - 1
    quick_sort(list1, low, high)
    print(" ".join(list(map(str, list1))))

算法性能

快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。
理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过logn趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlogn)。
最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n)。
为改善最坏情况下的时间性能，可采用其他方法选取中间数。通常采用“三者值取中”方法，即比较H->r[low].key、H->r[high].key与H->r[(low+high)/2].key，取三者中关键字为中值的元素为中间数。
可以证明，快速排序的平均时间复杂度也是O(nlogn)。因此，该排序方法被认为是目前最好的一种内部排序方法。
从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(logn))。

6. 堆排序

算法实现

描述
堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：

• 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
  
• 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
  
• 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

算法原理

1. 创建一个堆 H[0..n-1]；
   
2. 把堆首（最大值）和堆尾互换；
   
3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
   
4. 重复步骤 2，直到堆的尺寸为 1。

代码

var len;

function buildMaxHeap(arr) {
  len = arr.length;
  for (let i = Math.floor(len / 2); i >= 0; i--) {
    heapify(arr, i);
  }
}

function heapify(arr, i) {
  let left = 2 * i + 1;
  let right = 2 * i + 2;
  let largest = i;

  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest != i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, largest);
  }
}

function heapSort(arr) {
  buildMaxHeap(arr);
  for (let i = arr.length - 1; i >= 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    len--;
    heapify(arr, 0);
  }
  return arr;
}

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

算法性能

初始化建堆的时间复杂度为O(n)，排序重建堆的时间复杂度为nlog(n)，所以总的时间复杂度为O(n+nlogn)=O(nlogn)。另外堆排序的比较次数和序列的初始状态有关，但只是在序列初始状态为堆的情况下比较次数显著减少，在序列有序或逆序的情况下比较次数不会发生明显变化。

7. 希尔排序

算法实现

描述
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
• 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位

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


原理
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 =1(
该方法实质上是一种分组插入方法
比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。
假设待排序文件有10个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为：5，2，1

步骤**

1. 选择一个增量序列t1，t2，…，tk，其中 ti > tj，tk=1；
   
2. 按增量序列个数 k，对序列进行 k 趟排序；
   
3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
   

代码

function shellSort(arr) {
  let len = arr.length;
  let temp, gap = 1;
  while (gap < len / 3) {
    gap = gap * 3 + 1;
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (var i = gap; i < len; i++) {
      temp = arr[i];
      for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }
  }
  return arr;
}

算法性能

| Name | Best | Average | Worst | Memory | Stable | Comments | | Shell sort | n log(n) | depends on gap sequence | n (log(n)) | 1 | No | | | —- | —- | —- | —- | —- | —- | —- |

本质上讲，希尔排序算法是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当n值很大时数据项每一趟排序需要移动的个数很少，但数据项的距离很长。当n值减小时每一趟需要移动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。Shell算法的性能与所选取的分组长度序列有很大关系。只对特定的待排序记录序列，可以准确地估算关键词的比较次数和对象移动次数。想要弄清关键词比较次数和记录移动次数与增量选择之间的关系，并给出完整的数学分析，今仍然是数学难题。
1．增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了较好的结果：当n较大时，比较和移动的次数约在n^1.25到(1.6n)^1.25之间。
2．Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和 的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插入排序有较大的改进

8. 桶排序

算法实现

描述
桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量
2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
1. 什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
2. 什么时候最慢
当输入的数据被分配到了同一个桶中。
图例
元素分布在桶中：

然后，元素在每个桶中排序：

代码

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];                // 输入数据的最小值
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];                // 输入数据的最大值
      }
    }

    //桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    //利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                      
        }
    }

    return arr;
}

算法分析

总结：桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。当然桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。

9. 计数排序

算法实现

描述
计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
图例


算法步骤
假设输入的线性表L的长度为n，L=L1,L2,..,Ln；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；则计数排序可以描述如下：
1、扫描整个集合S，对每一个Si∈S，找到在线性表L中小于等于Si的元素的个数T(Si)；
2、扫描整个线性表L，对L中的每一个元素Li，将Li放在输出线性表的第T(Li)个位置上，并将T(Li)减1。
代码

function countingSort(arr, maxValue) {
  let bucketLen = maxValue + 1;
  let bucket = new Array(bucketLen);
  let sortedIndex = 0;

  for (let i = 0; i < arr.length; i++) {
    if (!bucket[arr[i]]) {
      bucket[arr[i]] = 1;
    } else {
      bucket[arr[i]]++;
    }
  }
  for (let j = 0; j < bucketLen; j++) {
    while (bucket[j] > 0) {
      arr[sortedIndex++] = j;
      bucket[j]--;
    }
  }
  return arr;
}

算法性能

我们看到，计数排序算法没有用到元素间的比较，它利用元素的实际值来确定它们在输出数组中的位置。因此，计数排序算法不是一个基于比较的排序算法，从而它的计算时间下界不再是O(nlogn)。另一方面，计数排序算法之所以能取得线性计算时间的上界是因为对元素的取值范围作了一定限制，即k=O(n)。如果k=n^2,n^3,..，就得不到线性时间的上界。此外，经计数排序，输出序列中值相同的元素之间的相对次序与他们在输入序列中的相对次序相同，换句话说，计数排序算法是一个稳定的排序算法。

10. 基数排序

算法实现

描述
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
基数排序有两种方法：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值；

图例

步骤
第一步
以LSD为例，假设原来有一串数值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
第二步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
第三步
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
代码**

//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

算法性能

设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。

参考资料

百度百科
《算法导论》
https://www.runoob.com/w3cnote 菜鸟教程
https://github.com/trekhleb/javascript-algorithms js算法
https://www.ctolib.com/docs-JS-Sorting-Algorithm-c-index.html CTOLib码库
https://www.jianshu.com/p/34209c493a79?from=timeline&isappinstalled=0 由浅入深快速排序算法（JS实现）
https://zhuanlan.zhihu.com/p/97075667 递归转迭代之快速排序
https://blog.csdn.net/jjwwwww/article/details/81057881 快速排序进阶之三路快排