用 JS 实现各种经典排序算法

　　最近在复习算法相关的知识点，总结了一下以供参考，也是对自己知识的一种复习。排序算法的几个主要指标是，时间复杂度（平均、最好、最差）、空间复杂度和稳定性。本文主要描述八种常见算法：简单选择排序、冒泡排序、简单插入排序、希尔排序、归并排序、快速排序、堆排序和基数排序，还有它们的指标统计。算法的实现都基于JS实现的。

　　

算法名称	平均时间复杂度	最好时间复杂度	最差时间复杂度	空间复杂度	稳定性
冒泡排序	O(n)	O(n)	O(n)	O(1)	稳定
选择排序	O(n)	O(n)	O(n)	O(1)	不稳定
插入排序	O(n)	O(n)	O(n)	O(1)	稳定
希尔排序	O(n)  (不确定)	O(n)	O(n)	O(1)	不稳定
归并排序
快速排序
堆排序
基数排序

一、冒泡排序

　　冒泡排序的思路是：假设正在将一组数字按照升序排列，从第0个元素到第n-1个元素遍历，若前面一个元素大于后面一个元素，则交换两个元素，这样可将整个序列中最大的元素冒泡到最后，然后再从第0个到第n-2遍历，如此往复，直到完成。

　　1、初级版：冒泡排序无论如何都要执行完两重循环，故最好、最坏和平均时间复杂度均为O(n)，不需要额外空间。冒泡排序是稳定的。

function bubbleSort(array) {
  const n = array.length - 1
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i; j++) {
      if (array[j] > array[j + 1]) {
        const temp = array[j]
        array[j] = array[j + 1]
        array[j + 1] = temp
      }
    }
  }
  return array
}

　　2、改进版：在内层循环之前设置一个标志性变量pos，用于记录每趟排序中最后一次进行交换的位置，由于pos位置之后的记录均已交换到位，故在进行下一趟排序是只要扫描到pos位置。冒泡排序的最好时间复杂度可以提升到O(n)。

function bubbleSort(array) {
  let i = array.length - 1;
  while (i > 0) {
    let pos = 0;
    for (let j = 0; j < i; j++) {
      if (array[j] > array[j + 1]) {
        pos = j;
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
    i = pos;
  }
  return array;
}

二、选择排序

　　选择排序的思路是：从全部序列中选取最小的，与第0个元素交换，然后从下一个元素往后找出最小的，与该元素元素交换，以此类推，直到选取最后一个元素。因为无论如何都要完整地执行内外两重循环，故最好、最差和平均时间复杂度都是O(n)，唯一的好处就是不占用额外的内存空间。选择排序是不稳定的。

function selectionSort(array) {
  let length = array.length;
  for (let i = 0; i < length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < length; j++) {
      if (array[j] < array[min]) {
        min = j;
      }
    }
    let temp = array[i];
    array[i] = array[min];
    array[min] = temp;
  }
  return array;
}

三、简单插入排序

　　简单插入排序思路是类似扑克牌的排序，每次从未排序序列的第一个元素，插入到已排序序列中的合适位置。

　　1、初级版：通过两重循环，最差和平均时间复杂度为O(n)，最好情况是原序列已有序，则忽略内层循环，时间复杂度O(n)。插入排序是稳定的。

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let key = array[i];
    let j = i - 1;
    while (j >= 0 && array[j] > key) {
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = key;
  }
  return array;
}

　　2、改进版：二分查找改进的插入排序

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let key = array[i], left = 0, right = i - 1;
    while (left < right) {
      let middle = Math.floor((left + right) / 2);
      if (key < array[middle]) {
        right = middle - 1;
      } else {
        left = middle;
      }
    }
    for (let j = i - 1; j >= left; j--) {
      array[j + 1] = array[j];
    }
    array[left] = key;
  }
  return array;
}

四、希尔排序

　　希尔排序的思路是，先以一个较大的增量，将序列分成几个子序列，将这几个子序列分别排序后，合并，在缩小增量进行同样的操作，直到增量为1时，序列已经基本有序，再进行简单插入排序的效率就会较高。

　　希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态定义间隔序列。

　　1、动态间隔序列希尔排序（可以设置间隔区间）

function shellSort(array) {
  const N = array.length
  let gap = 1;
  while (gap < N / 5) {
    gap = gap * 5 + 1;
  }
  while (gap >= 1) {
    for (let i = gap; i < N; i++) {
      for (let j = i; j >= gap && array[j] > array[j - gap]; j -= gap) {
        let tmp = array[j]
        array[j] = array[j - gap]
        array[j - gap] = tmp
      }
    }
    gap = (gap - 1) / 5
  }
  return array
}

　　2、硬编码间隔序列的希尔排序（gaps 为 [10,4,1] 这样设定好间隔的数组）

function shellSort1(array, gaps) {
  for (let g = 0; g < gaps.length; g++) {
    const gap = gaps[g]
    for (let i = gap; i < array.length; i++) {
      for (j = i; j >= gap && array[j] > array[j - gap]; j -= gap) {
        let tmp = array[j]
        array[j] = array[j - gap]
        array[j - gap] = tmp
      }
    }
  }
}