JavaScript实现十大排序算法「图文详解」

前言

排序是计算机科学中的一个重要概念，是将一组数据按照特定的规则进行排列的过程。排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据太大，不能同时存放在内存中，必须借助外部存储器进行排序。

JavaScript作为一种脚本语言，在基础排序算法的实现上与其他语言有着相似之处。在本文中，我们将介绍JavaScript中实现的十大排序算法。

一. 冒泡排序（Bubble Sort）

冒泡排序是一种基础的排序算法，它的工作原理是相邻元素两两比较， 根据大小交换位置，重复进行直到所有元素有序排列。

算法步骤：

① 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

② 对每一对相邻元素做同样的工作，从开始的第一对到结尾的最后一对。这时，最后的元素应该会是最大的数。

③ 针对所有未排序元素，重复以上步骤，直至排序完成。

代码：

function bubbleSort(arr) {

  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {        // 相邻元素对比
        var temp = arr[j];              // 交换元素
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

1. 对于冒泡排序的时间和空间复杂度：平均时间复杂度O(n^2)，空间复杂度O(1)。

2. 冒泡排序是一种稳定排序，它可以同时排列相同数据。

二. 选择排序（Selection Sort）

选择排序也是一种基础的排序算法，它的工作原理是将数据分为已排序和未排序两个部分，将未排序部分的最小值选出来插入到已排序部分的最后面。

算法步骤：

① 在未排序序列中，找到最小元素，存放到排序序列的起始位置。

② 重复步骤①，直到所有元素均排序完毕。

代码：

function selectionSort(arr) {

  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    var minIndex = i;                           // 默认当前位置为最小值
    for (var j = i + 1; j < len; j++) {          // 遍历未排序序列
      if (arr[j] < arr[minIndex]) {             // 判断未排序序列元素是否小于当前最小值
        minIndex = j;                           // 未排序序列元素最小值更新为当前元素
      }
    }
    var temp = arr[i];                          // 将当前位置元素与最小值交换位置
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

1. 对于选择排序的时间和空间复杂度：平均时间复杂度O(n^2)，空间复杂度O(1)。

2. 选择排序是一种不稳定排序，相同数据交换位置后可能导致其顺序改变。

三. 插入排序（Insertion Sort）

插入排序是一种基础的排序算法，它的工作原理是将数据分为已排序和未排序两个部分，在未排序部分选择一个元素，在已排序部分找到它的插入位置并插入。

算法步骤：

① 从第一个元素开始，该元素可以认为已经被排序。

② 取出下一个元素，在已经排序的元素序列中从后向前扫描。

③ 如果该元素（已排序）大于新元素，将该元素移到下一位置。

④ 重复步骤③，直到找到已排序元素小于或者等于新元素的位置。

⑤ 将新元素插入到该位置后。

⑥ 重复步骤②~⑤。

代码：

function insertionSort(arr) {

  var len = arr.length;
  for (var i = 1; i < len; i++) {
    var temp = arr[i];
    var j = i - 1;
    while (j >= 0 && arr[j] > temp) {     // 在已排序序列中寻找插入位置
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;                    // 插入位置
  }
  return arr;
}

1. 对于插入排序的时间和空间复杂度：平均时间复杂度O(n^2)，空间复杂度O(1)。

2. 插入排序是一种稳定排序，相同数据不会交换位置。

四. 希尔排序（Shell Sort）

希尔排序是插入排序的一种高效改进，它的工作原理是将待排序的数据元素分成多个子序列，对各个子序列分别进行直接插入排序。由于插入排序在对几乎已经排好序的数据操作时，效率较高，因此希尔排序在时间复杂度和效率上有很大的改进。

算法步骤：

① 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；

② 按增量序列个数k，对序列进行k趟排序；

③ 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅将当前子序列的第一个元素看做有序序列，其余元素为待插入元素；

④ 增量因子每次减半重复步骤②和③，直到增量为1，完成排序。

代码：

function shellSort(arr) {

  var len = arr.length;
  for (var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (var i = gap; i < len; i++) {
      var temp = arr[i];
      var j = i - gap;
      while (j >= 0 && arr[j] > temp) {  // 对每个增量序列子序列进行插入排序
        arr[j + gap] = arr[j];
        j -= gap;
      }
      arr[j + gap] = temp;               // 插入位置
    }
  }
  return arr;
}

1. 对于希尔排序的时间和空间复杂度：平均时间复杂度O(nlogn)~O(n^2)，空间复杂度O(1)。

2. 希尔排序是一种不稳定排序。

五. 归并排序（Merge Sort）

归并排序算法是一种稳定的排序算法，它采用分治思想。归并排序将输入的数据分成两个部分，在各自的部分内排序后再进行合并。分治思想是将问题划分成一些小问题递归求解，然后将结果合并起来。

算法步骤：

① 分解：将待排序的n个元素分成两个含n/2个元素的子序列，每个子序列都是有序的。

② 治理：将两个子序列合并成一个子序列，其中每个元素至多比较一次。

③ 合并：对左右两个子序列进行两两排序合并，最终合并成一个完整的序列

代码：

function mergeSort(arr) {

  if (arr.length < 2) {
    return arr;
  }
  var mid = Math.floor(arr.length / 2);
  var left = arr.slice(0, mid);
  var right = arr.slice(mid, arr.length);
  return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
  var result = [];
  while (left.length && right.length) {        // 对两个已排好序的子序列进行合并
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());                // 如果left有剩余元素，直接加到result后面
  }
  while (right.length) {
    result.push(right.shift());               // 如果right有剩余元素，直接加到result后面
  }
  return result;
}

1. 对于归并排序的时间和空间复杂度：平均时间复杂度O(nlogn)，空间复杂度O(n)。

2. 归并排序是一种稳定排序。

六. 快速排序（Quick Sort）

快速排序是一种常用的排序算法，它基于分治思想，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后按此方法对两部分记录分别进行递归快排，直到整个序列有序。

算法步骤：

① 在待排序的n个记录中，任取一个记录（通常取第一个记录）作为关键字，以此关键字将其余n-1个记录分成两组，一组是key小的记录所有记录都比目前所选的记录key大，另一组是key大的记录，所有记录都比目前所选的记录key小。

② 然后对这两组数据记录分别进行快速排序。

③ 递归进行步骤①和②，直到最后达到整个序列有序的状态。

代码：

function quickSort(arr) {

  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];         // 取出于待排序列中间的元素
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++) {            // 根据该元素进行比较和分组
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
}

1. 对于快速排序的时间和空间复杂度：平均时间复杂度O(nlogn)，最坏情况O(n^2)，空间复杂度O(logn)。

2. 快速排序是一种不稳定排序。

七. 堆排序（Heap Sort）

堆排序是一种利用堆的数据结构来排序的选择排序算法，它的工作原理是通过构造初始堆来得到最大/小值，并将其与末尾元素交换，然后对其进行堆调整。

算法步骤：

① 将初始待排序序列构造成一个最大/小堆，从最后一个非叶子节点开始向上构造。

② 将堆顶元素与末尾元素进行交换，使末尾元素最大/小。

③ 重新对剩余元素进行堆调整，得到所有序列升序/降序。

代码：

function heapSort(arr) {

  var len = arr.length;
  buildMaxHeap(arr);                             // 构造最大堆
  for (var i = len - 1; i > 0; i--) {            // 交换堆顶元素和末尾元素
    swap(arr, 0, i);
    len--;
    heapify(arr, 0, len);                        // 对堆顶元素进行堆调整
  }
  return arr;
}
function buildMaxHeap(arr) {
  var len = arr.length;
  for (var i = Math.floor(len / 2); i >= 0; i--) {   // 从最后一个非叶子节点开始向上构造
    heapify(arr, i, len);
  }
}
function heapify(arr, i, len) {
  var left = 2 * i + 1;
  var right = 2 * i + 2;
  var largest = i;
  if (left < len && arr[left] > arr[largest]) {      // 判断左节点是否大于父节点
    largest = left;
  }
  if (right < len && arr[right] > arr[largest]) {    // 判断右节点是否大于父节点和左节点
    largest = right;
  }
  if (largest !== i) {                                // 如果子节点有一个比i节点大则交换
    swap(arr, i, largest);
    heapify(arr, largest, len);
  }
}
function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

1. 对于堆排序的时间和空间复杂度：平均时间复杂度O(nlogn)，空间复杂度O(1)。

2. 堆排序是一种不稳定排序。

八. 计数排序（Counting Sort）

计数排序是一种非比较性排序，它通过确定每个元素的大小在有序序列中的位置，来确定它在输出序列中的位置。计数排序是稳定的线性时间排序。

算法步骤：

① 找出待排序的数组中最大和最小的元素；

② 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；

③