说来惭愧，到现在都还不能完全熟悉这十大排序算法，So It’s time to do it

上表

排序算法	平均时间复杂度	稳定性
冒泡排序	O(n^2)	稳定
选择排序	O(n^2)	不稳定
插入排序	O(n^2)	稳定
希尔排序	1.5*n	不稳定
归并排序	O(n*logn)	稳定
快速排序	O(n*logn)	不稳定
堆排序	O(n*logn)	不稳定
基数排序	O(d(n+r))	稳定
拓扑排序
计数排序

稳定性

稳定性指序列中有相同的元素，经过排序后，其相对位置不变

冒泡排序

基本思想：相邻两个数进行比较，较大的数下沉，较小的数冒泡,即逆序便交换

过程：从后往前依次比较相邻两个数，每轮选出第 i 小元素放到对应位置

优化：设置标志位flag，每轮开始比较前将标志值设为false，若比较过程中发生交换，更改标志值为true。如果这轮比较结束标志值依旧为false，说明没有发生交换行为，元素顺序已排好，因此可直接返回。

时间复杂度：(n-1)+(n-2)+…+1,为等差数列 Sn=n(a1+an)/2=(n^2-n)/2,得时间复杂度为 O(n^2)

稳定性：在比较交换条件时，相同元素默认没有进行交换，所以该排序算法是稳定的

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let flag = false;
    for (let j = arr.length - 1; j > i; j--) {
      if (arr[j - 1] > arr[j]) {
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
        flag = true;
      }
    }
    if (!flag) {
      break;
    }
  }
  console.log(arr);
}
let arr1 = [2, 4, 3, 2, 5, 6, 4, 7];
bubbleSort(arr1);

选择排序

基本思想：遍历序列，每次选出最小的元素与第 I 轮对应位进行交换

过程： 每轮遍历前建立最小值索引minIndex，通过比较更新索引值，第 i 轮遍历比较结束交换下标为 i 和minIndex的元素

时间复杂度：(n-1)+(n-2)+…+1,为等差数列 Sn=n(a1+an)/2=(n^2-n)/2,得时间复杂度为 O(n^2)

稳定性：序列[5(1),8,5(2),2,9]，5(1)会和 2 交换，最终排序结果 5(1)和 5(2)的相对位置会被破坏，因此该算法不稳定。

function selectSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  console.log(arr);
}
let arr = [2, 4, 5, 7, 8, 3, 1, 6];
selectSort(arr);

插入排序

基本思想：采用减(减一)治思想，在要排序的一组数中，假定前 n-1 个数已经排好序，现在将第 n 个数插到前面的有序数列中，使得这 n 个数也是排好顺序的。如此反复循环，直到全部排好顺序。

过程：建立临时变量cur存储当前元素,从有序数组后面开始比较，移步赋值占空出来的位，直到找到第一个<=当前元素的元素，插入到其后面

时间复杂度：(n-1)+(n-2)+…+1,为等差数列 Sn=n(a1+an)/2=(n^2-n)/2,得时间复杂度为 O(n^2)

稳定性：由于比较等于时，是插入到后面，所以相对位置没有改变，因此该排序算法稳定。

function straightInsertionSort(arr) {
  for (let i = 1; i < arr.length; ++i) {
    let cur = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > cur) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = cur;
  }
  console.log(arr);
  return arr;
}
let arr1 = [89, 45, 68, 90, 29, 34, 17];
straightInsertionSort(arr1);

希尔排序

基本思想：是插入排序的优化，将序列按增量划分为子序列分别进行插入排序，逐渐将增量减小,并重复上述过程。直至增量为 1,

过程：增量incr的初始值为序列的长度，每轮划分子序列前将增量/2

优化：在对子序列进行插入排序时，注意当前元素cur的最小值要大于本序列的起始元素的索引 i

稳定性：序列[28，17(1),17(2),49],排序后 17(1)和 17(2)的相对位置会改变，该算法不稳定

function shellSort(arr) {
  let incr = arr.length;
  while (incr > 0) {
    incr = Math.floor(incr / 2);
    for (let i = 0; i < incr; i++) {
      for (let j = i + incr; j < arr.length; j += incr) {
        let cur = j;
        while (cur > i && arr[cur] < arr[cur - incr]) {
          [arr[cur], arr[cur - incr]] = [arr[cur - incr], arr[cur]];
          cur -= incr;
        }
      }
    }
  }
  console.log(arr);
}
let arr = [2, 4, 1, 5, 6, 8, 9];
shellSort(arr);

归并排序

基本思路：基于分治思想，将序列不断分半拆分，知道序列元素个数为 1 即有序，然后递归排序两个子序列，再将排好序的两个子数组合并

过程：建立递归排序函数sort和合并函数merge，在合并过程中建立临时数组temp存放排序后的序列，再替换arr对应位置的元素

时间复杂度：设数列长为 N，将数列分开成小数列一共要 logN 步，每步都是一个合并有序数列的过程，时间复杂度可以记为 O(N)，故一共为 O(N*logN)。

稳定性：排序后没有破坏相同元素的相对位置，故该排序算法稳定

function mergeSort(arr) {
  sort(arr, 0, arr.length - 1);
  console.log(arr);
}

function sort(arr, left, right) {
  if (left < right) {
    let mid = Math.floor((left + right) / 2);
    sort(arr, left, mid);
    sort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }
}

function merge(arr, left, mid, right) {
  let lf = left,
    le = mid,
    rf = mid + 1,
    re = right;
  let temp = [];
  while (lf <= le && rf <= re) {
    if (arr[lf] <= arr[rf]) {
      temp.push(arr[lf]);
      lf++;
    } else {
      temp.push(arr[rf]);
      rf++;
    }
  }
  while (lf <= le) {
    temp.push(arr[lf]);
    lf++;
  }
  while (rf <= re) {
    temp.push(arr[rf]);
    rf++;
  }
  arr.splice(left, right - left + 1, ...temp);
}

let arr = [2, 5, 3, 1, 6, 8, 4, 9];
let arr1 = [23, 65, 1, 234, 8, 65, 4, 9, 0, 23];
mergeSort(arr);
mergeSort(arr1);

快速排序

基本思想：

• 先从数列中取出一个数作为 key 值，一般取第一位
• 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
• 对左右两个小数列重复第二步，直至各区间只有 1 个数。

过程：选取序列第一位元素为中轴，建立两个查找指针 i 和 j,i 从左往右扫描，j 从右往左扫描，i 遇到第一个>=中轴的元素便停下来，j 遇到第一个<=中轴的元素便停下来。当 i 和 j 都停下来时，交换 i 和 j 对应的元素，i 和 j 分别++，继续寻找，直到 j>i,便将 j 对应的元素和中轴进行交换，以交换后中轴的位置为界，继续递归划分子序列

时间复杂度：O(n*logn)

稳定性：序列[6,8,5(1),5(2),7]排序后 5(1)和 5(2)的相对位置会改变，该排序算法不稳定

function quickSort(arr) {
  sort(arr, 0, arr.length - 1);
  console.log(arr);
}
function sort(arr, l, r) {
  if (l > r) {
    return;
  }
  let key = arr[l];
  let i = l + 1,
    j = r;
  while (i < j) {
    while (i < j && arr[i] < key) {
      i++;
    }
    while (arr[j] > key) {
      j--;
    }
    if (i < j) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
      j--;
    } else {
      break;
    }
  }
  // j>i
  [arr[l], arr[j]] = [arr[j], arr[l]];
  sort(arr, l, j - 1);
  sort(arr, j + 1, r);
}
let arr1 = [2, 5, 3, 7, 6, 9, 1, 4];
let arr2 = [34, 2, 2, 2, 1, 4, 5, 7, 89, 0, 45, 66];
quickSort(arr1);
quickSort(arr2);

堆排序

基本思想: 基于变治思想，默认续写为完全二叉树，通过调整序列来达到大顶堆或小顶堆的效果

过程：从最后一个非叶子节点开始调整，直到根节点。调整时需要考虑到下层，因此需要循环

a.假设给定无序序列结构如下

2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的 6 结点），从左至右，从下至上进行调整。

4.找到第二个非叶节点 4，由于[4,9,8]中 9 元素最大，4 和 9 交换。

这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中 6 最大，交换 4 和 6。

此时，我们就将一个无需序列构造成了一个大顶堆。

时间复杂度: 每次重新恢复堆的时间复杂度为 O(logN)，共 N - 1 次重新恢复堆操作，再加上前面建立堆时 N / 2 次向下调整，每次调整时间复杂度也为 O(logN)。二次操作时间相加还是 O(N * logN)。

稳定性：比较过程中元素移动位置很错乱，该排序算法不稳定

function buildBigHeap(arr) {
  for (let i = arr.length / 2 - 1; i >= 0; i--) {
    adjustHeap(arr, i);
  }
}
function adjustHeap(arr, cur) {
  while (cur <= arr.length / 2 - 1) {
    let k = 2 * cur + 1;
    if (arr[k + 1] && arr[k + 1] > arr[k]) {
      k++;
    }
    if (arr[k] > arr[cur]) {
      [arr[k], arr[cur]] = [arr[cur], arr[k]];
    }
    cur = k;
  }
}

基数排序

稳定性：该算法是稳定的

拓扑排序

基本思想：有向无环图

计数排序

基本思想