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

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

一、冒泡排序

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

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

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(n2)，唯一的好处就是不占用额外的内存空间。选择排序是不稳定的。

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(n2)，最好情况是原序列已有序，则忽略内层循环，时间复杂度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 / 3) {
    gap = gap * 3 + 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) / 3
  }
  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
      }
    }
  }
}

 五、快速排序

　　快速排序的思想是，选取第一个数为基准，通过一次遍历将小于它的元素放到它的左侧，将大于它的元素放到它的右侧，然后对它的左右两个子序列分别递归地执行同样的操作。

function quickSort (array) {
  if (array.length <= 1) {
    return []
  }
  const lesser = [];
  const greater = [];
  const pivot = array[0];
  for (let i = 1; i < array.length; i++) {
    if (array[i] < pivot) {
      lesser.push(array[i]);
    } else {
      greater.push(array[i]);
    }
  }
  return quickSort(lesser).concat(pivot, quickSort(greater));
}

六、归并排序

　　归并排序的思路是，利用二分的特性，将序列分成两个子序列进行排序，将排序后的两个子序列归并（合并），当序列的长度为2时，它的两个子序列长度为1，即视为有序，可直接合并，即达到归并排序的最小子状态。

　　1、初级版（效率低）

function mergeSort(array) {
  if (array.length < 2) {
    return array;
  }
  const middle = parseInt(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const newArray = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      newArray.push(left.shift());
    } else {
      newArray.push(right.shift());
    }
  }
  while (left.length) {
    newArray.push(left.shift());
  }
  while (right.length) {
    newArray.push(right.shift());
  }
  return newArray;
}

 　　2、改进版（效率较高）

function mergeSort(array = [], start = 0, length) {
  length = length || array.length;
  if (length - start < 2) {
    return;
  }
  const mid = Math.floor((start + length) / 2);
  mergeSort(array, start, mid);
  mergeSort(array, mid, length);
  merge(array, start, mid, length);
  return array;
}
function merge(array, start, mid, length) {
  const left = array.slice(start, mid);
  const right = array.slice(mid, length);
  left.push(Number.MAX_SAFE_INTEGER);
  right.push(Number.MAX_SAFE_INTEGER);
  for (let i = start, j = 0, k = 0; i < length; i++) {
    if (left[j] < right[k]) {
      array[i] = left[j];
      j++;
    } else {
      array[i] = right[k];
      k++;
    }
  }
}

　　3、高级版（效率高)

function mergeSort2(array = []) {
  if (array.length < 2) {
    return;
  }
  let step = 1;
  let left;
  while (step < array.length) {
    left = 0;while (left + step * 2 <= array.length) {
      merge2(array, left, left + step, left + step * 2);
      left = left + step * 2;
    }
    if (left + step < array.length) {
      merge2(array, left, left + step, array.length);
    }
    step *= 5;
  }
  return array
}
function merge2(array, start, mid, length) {
  const rightArr = new Array(length - mid + 1);
  const leftArr = new Array(mid - start + 1);
  let k = mid;
  for (let i = 0; i < length - mid; i++) {
    rightArr[i] = array[k];
    k++;
  }
  k = start;
  for (let i = 0; i < mid - start; i++) {
    leftArr[i] = array[k];
    k++;
  }
  rightArr[length - mid] = Infinity;
  leftArr[mid - start] = Infinity;
  let m = 0;
  let n = 0;
  for (k = startLeft; k < stopRight; ++k) {
    if (leftArr[m] <= rightArr[n]) {
      array[k] = leftArr[m];
      m++;
    } else {
      array[k] = rightArr[n];
      n++;
    }
  }
}

 　　归并高级版比改进版效率高的原因有两个：

　1、算法递归次数少；

　2、新建Array，对其赋值效率比Array.slice()高

对比1000万的数组排序所用的时间

希尔排序时间为：18295ms
快速排序时间为：9754ms
改进版归并算法时间为：3677ms
高级版归并算法2时间为：1252ms
 
 
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/zjp-zxy/p/11943766.html