「数据结构与算法Javascript描述」十大排序算法

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。

本文将为大家介绍十大经典的排序算法。

1. 冒泡排序

我们先来了解一下「冒泡排序」算法，它是最慢的排序算法之一，但也是一种最容易实现的排序算法。

之所以叫冒泡排序是因为使用这种排序算法排序时，数据值会像气泡一样从数组的一端漂 浮到另一端。假设正在将一组数字按照升序排列，较大的值会浮动到数组的右侧，而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动，比较相邻的数据，当左侧值大于右侧值时将它们进行互换。

这里有一个简单的冒泡排序的例子。我们从下面的列表开始：

「E A D B H」

经过第一次排序后，这个列表变成：

「A E D B H」

前两个元素进行了互换。接下来再次排序又会变成：

「A D E B H」

第二个和第三个元素进行了互换。继续进行排序：

「A D B E H」

第三个和第四个元素进行了互换。最后，第二个和第三个元素还会再次互换，得到最终顺序：

「A B D E H」

下图演示了如何对一个大的数字数据集合进行冒泡排序。在图中，我们分析了插入数组中的两个特定值：2 和 72。这两个数字都被圈了起来。你可以看到 72 是如何从数组的开头移动到中间的，还有 2 是如何从数组的后半部分移动到开头的。

image-20220209151259705

下面我们给出冒泡排序算法的实现：

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

首先，声明一个名为length的变量，用来存储数组的长度。这一步可选，它能帮助我们直接使用数组的长度。接着，外循环会从数组的第一位迭代至最后一位，它控制了在数组中经过多少轮排序（应该是数组中每项都经过一轮，轮数和数组长度一致）。然后，内循环将从第一位迭代至倒数第二位，内循环实际上进行当前项和下一项的比较。如果这两项顺序不对（当前项比下一项大），则交换它们，意思是位置为j+1的值将会被换置到位置j处，反之亦然。

交换时，我们用一个中间值来存储某一交换项的值。其他排序法也会用到这个方法，因此我们声明一个方法swap放置这段交换代码以便重用。

有时候我们在循环的中间迭代时已经完成了排序。尽管如此，在后续比较中，它们还一直在进行着比较，即使这是不必要的。因此，我们可以稍稍改进一下冒泡排序算法。

「改进后的冒泡排序」

如果从内循环减去外循环中已跑过的轮数，就可以避免内循环中所有不必要的比较

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

2. 选择排序

我们接下来要看的是「选择排序」算法。选择排序从数组的开头开始，将第一个元素和其他元素进行比较。检查完所有元素后，最小的元素会被放到数组的第一个位置，然后算法会从第二个位置继续。这个过程一直进行，当进行到数组的倒数第二个位置时，所有的数据便完成了排序。

选择排序会用到嵌套循环。外循环从数组的第一个元素移动到倒数第二个元素；内循环从第二个数组元素移动到最后一个元素，查找比当前外循环所指向的元素小的元素。每次内循环迭代后，数组中最小的值都会被赋值到合适的位置。

以下是一个对只有五个元素的列表进行选择排序的简单例子。初始列表为：

「E A D H B」

第一次排序会找到最小值，并将它和列表的第一个元素进行互换。

「A E D H B」

接下来查找第一个元素后面的最小值（第一个元素此时已经就位），并对它们进行互换：

「A B D H E」

D 也已经就位，因此下一步会对 E 和 H 进行互换，列表已按顺序排好：

「A B D E H」

下图展示了如何对更大的数据集合进行选择排序。

image-20220209180555336

下面我们给出选择排序算法的实现：

function selectionSort(dataList) {
  function swap(i, j) {
    const temp = dataList[i];
    dataList[i] = dataList[j];
    dataList[j] = temp;
  }
  const length = dataList.length;
  for(let i = 0; i < length; i++) {
    let minIndex = i;
    for (let j = i; j < length; j++) {
      if (dataList[minIndex] > dataList[j]) {
        minIndex = j;
      }
    }
    if (i !== minIndex) {
      swap(i, minIndex);
    }
  } 
}

首先声明一些将在算法内使用的变量。接着，外循环迭代数组，并控制迭代轮次（数组的第n个值——下一个最小值）。我们假设本迭代轮次的第一个值为数组最小值。然后，从当前i的值开始至数组结束，我们比较是否位置j的值比当前最小值小；如果是，则改变最小值至新最小值。当内循环结束，将得出数组第n小的值。最后，如果该最小值和原最小值不同，则交换其值。

选择排序同样也是一个复杂度为O(n2)的算法。和冒泡排序一样，它包含有嵌套的两个循环，这导致了二次方的复杂度。然而，接下来要学的插入排序比选择排序性能要好。

3. 插入排序

「插入排序」类似于人类按数字或字母顺序对数据进行排序。例如，让班里的每个学生上交一张写有他的名字、学生证号以及个人简介的索引卡片。学生交上来的卡片是没有顺序的， 但是我想让这些卡片按字母顺序排好，这样就可以很容易地与班级花名册进行对照了。

我将卡片带回办公室，清理好书桌，然后拿起第一张卡片。卡片上的姓氏是 Smith。我把它放到桌子的左上角，然后再拿起第二张卡片。这张卡片上的姓氏是 Brown。我把 Smith 移右，把 Brown 放到 Smith 的前面。下一张卡片是 Williams，可以把它放到桌面最右边， 而不用移动其他任何卡片。下一张卡片是 Acklin。这张卡片必须放在这些卡片的最前面，因此其他所有卡片必须向右移动一个位置来为 Acklin 这张卡片腾出位置。这就是插入排序的排序原理。

插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置，就像之前介绍的姓氏卡片一样。

下面我们给出选择插入算法的实现：

function insertionSort(dataList) {
  const length = dataList.length;
  for (let i = 1; i < length; i++) {
    let j = i, temp = dataList[i];
    while(j > 0 && dataList[j - 1] > temp) {
      dataList[j] = dataList[j - 1];
      j--;
    }
    dataList[j] = temp;
  }
}

照例，算法的第一行用来声明代码中使用的变量。接着，迭代数组来给第i项找到正确的位置。注意，算法是从第二个位置（索引1）而不是0位置开始的（我们认为第一项已排序了）。然后，用i的值来初始化一个辅助变量并将其值亦存储于一临时变量中，便于之后将其插入到正确的位置上。下一步是要找到正确的位置来插入项目。只要变量j比0大（因为数组的第一个索引是0——没有负值的索引）并且数组中前面的值比待比较的值大（行{5}），我们就把这个值移到当前位置上（行{6}）并减小j。最终，该项目能插入到正确的位置上。

4. 归并排序

「归并排序」的命名来自它的实现原理：归并排序是一种分治算法。把一系列排好序的子序列合并成一个大的完整有序序列。从理论上讲，这个算法很容易实现。我们需要两个排好序的子数组，然后通过比较数据大小，先从最小的数据开始插入，最后合并得到第三个数组。然而，在实际情况中，归并排序还有一些问题，当我们用这个算法对一个很大的数据集进行排序时，我们需要相当

大的空间来合并存储两个子数组。就现在来讲，内存不那么昂贵，空间不是问题，因此值得我们去实现一下归并排序，比较它和其他排序算法的执行效率。

的前三个排序算法性能不好，但归并排序性能不错，其复杂度为O(nlogn)。

下面我们给出选择归并算法的实现：

function mergeSort(dataList) {
  const length = dataList.length;
  if (length === 1) {
    return dataList;
  }
  const mid = Math.floor(length / 2);
  const left = dataList.slice(0, mid);
  const right = dataList.slice(mid, length);
  return merge(mergeSort(left), mergeSort(right));
}

归并排序将一个大数组转化为多个小数组直到只有一个项。由于算法是递归的，我们需要一个停止条件，在这里此条件是判断数组的长度是否为1。如果是，则直接返回这个长度为1的数组，因为它已排序了。

如果数组长度比1大，那么我们得将其分成小数组。为此，首先得找到数组的中间位，找到后我们将数组分成两个小数组，分别叫作left和right。left数组由索引0至中间索引的元素组成，而right数组由中间索引至原始数组最后一个位置的元素组成。

下面的步骤是调用merge函数，它负责合并和排序小数组来产生大数组，直到回到原始数组并已排序完成。为了不断将原始数组分成小数组，我们得再次对left数组和right数组递归调用mergeSort，并同时作为参数传递给merge函数。

function merge(left, right) {
  const result = [];
  let leftIndex = 0, rightIndex = 0;
  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[leftIndex]) {
      result.push(left[leftIndex++]);
    } else {
      result.push(right[rightIndex++]);
    }
  }
  while(leftIndex < left.length) {
    result.push(left[leftIndex++]);
  }
  while(rightIndex < right.length) {
    result.push(right[rightIndex++]);
  }
  return result;
}

merge函数接受两个数组作为参数，并将它们归并至一个大数组。排序发生在归并过程中。首先，需要声明归并过程要创建的新数组以及用来迭代两个数组（left和right数组）所需的两个变量。迭代两个数组的过程中，我们比较来自left数组的项是否比来自right数组的项小。如果是，将该项从left数组添加至归并结果数组，并递增迭代数组的控制变量；否则，从right数组添加项并递增相应的迭代数组的控制变量。接下来，将left数组或者right数组所有剩余的项添加到归并数组中。最后，将归并数组作为结果返回。

下图是具体的执行过程：

image-20220209184826624

通常来讲（也不一定），归并排序会使用递归的算法来实现。然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。所以，我们将使用一种非递归的方式来实现这个算法，这种策略称为自底向上的归并排序。

采用非递归或者迭代版本的归并排序是一个自底向上的过程。这个算法首先将数据集分解为一组只有一个元素的数组。然后通过创建一组左右子数组将它们慢慢合并起来，每次合并都保存一部分排好序的数据，直到最后剩下的这个数组所有的数据都已完美排序。下图演示了自底向上的归并排序算法是如何运行的。

image-20220209185009178

Infinity 这个值用于标记左子序列或右子序列的结尾。

一开始每个元素都在左子序列或右子序列中。然后将左右子序列合并，首先每次合并成两个元素的子序列，然后合并成四个元素的子序列，3 和 5 除外，它们会一直保留到最后一次迭代，那时会把它们合并成右子序列，然后再与最后的左子序列合并成最终的有序数组。

现在我们知道了自底向上的归并排序的工作原理，下面就是输出上述结果的代码。

function mergeSort(dataList) {
  if (dataList.length < 2) {
    return;
  }
  let step = 1;
  while(step < dataList.length) {
    let left = 0, right = step;
    while(right + step <= dataList.length) {
      mergeArrays(dataList, left, left + step, right, right + step);
      left = right + step;
      right = left + step;
    }
    if (right < dataList.length) {
      mergeArrays(dataList, left, left + step, right, dataList.length);
    }
    step *= 2;
  }
}

function mergeArrays(dataList, startLeft, stopLeft, startRight, stopRight) {
  const rightList = new Array(stopRight - startRight + 1);
  const leftList = new Array(stopLeft - startLeft + 1);
  let k = startRight;
  for (let i = 0; i < rightList.length - 1; i++) {
    rightList[i] = dataList[k];
    k++;
  }
  k = startLeft;
  for (let i = 0; i < leftList.length - 1; i++) {
    leftList[i] = dataList[k];
    k++;
  }
  rightList[rightList.length - 1] = Infinity; // 哨兵值
  leftList[leftList.length - 1] = Infinity; // 哨兵值
  let m = 0, n = 0;
  for (let k = startLeft; k < stopRight; k++) {
    if (leftList[m] <= rightList[n]) {
      dataList[k] = leftList[m];
      m++;
    } else {
      dataList[k] = rightList[n];
      n++;
    }
  }
}

mergeSort() 函数中的关键点就是 step 这个变量，它用来控制 mergeArrays() 函数生成的leftList 和 rightList 这两个子序列的大小。通过控制子序列的大小，处理排序是比较高效的，因为它在对小数组进行排序时不需要花费太多时间。合并之所以高效，还有一个原因，由于未合并的数据已经是排好序的，将它们合并到一个有序数组的过程非常容易。

5. 快速排序

「快速排序」是处理大数据集最快的排序算法之一。它的复杂度为O(nlogn)，且它的性能通常比其他的复杂度为O(nlogn)的排序算法要好。它也是一种分而治之的算法，通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。该算法不断重复这个步骤直到所有数据都是有序的。

快速排序比到目前为止你学过的其他排序算法要复杂一些。让我们一步步地来学习。

1. 首先，从数组中选择中间一项作为「主元」。
2. 创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫作「划分操作」。
3. 接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已完全排序。

function quickSort(dataList, left, right) {
  if (dataList.length > 1) {
    const index = partition(dataList, left, right);
    if (left < index - 1) {
      quickSort(dataList, left, index - 1);
    }
    if (index < right) {
      quickSort(dataList, index, right);
    }
  }
}

首先声明index，该变量能帮助我们将子数组分离为较小值数组和较大值数组，这样，我们就能再次递归的调用quickSort函数了。partition函数返回值将赋值给index。

如果数组的长度比1大（因为只有一个元素的数组必然是已排序了的，我们将对给定子数组执行partition操作（第一次调用是针对整个数组）以得到index。如果子数组存在较小值的元素，则对该数组重复这个过程。同理，对存在较大值得子数组也是如此，如果存在子数组存在较大值，我们也将重复快速排序过程。

现在，让我们看看「划分过程」

function partition(dataList, left, right) {
  let i = left, j = right;
  const pivot = dataList[Math.floor((right + left) / 2)];
  while (i <= j) {
    while (dataList[i] < pivot) {
      i++;
    }
    while(dataList[j] > pivot) {
      j--;
    }
    if (i <= j) {
      swap(dataList, i, j);
      i++; 
      j--;
    }
  }
  return i;
}

function swap(dataList, i, j) {
  const temp = dataList[i];
  dataList[i] = dataList[j];
  dataList[j] = temp;
}

第一件要做的事情是选择「主元（pivot）」，有好几种方式。最简单的一种是选择数组的第一项（最左项）。然而，研究表明对于几乎已排序的数组，这不是一个好的选择，它将导致该算法的最差表现。另外一种方式是随机选择一个数组项或是选择中间项。在本实现中，我们选择中间项作为主元。我们初始化两个指针：left，初始化为数组第一个元素；right，初始化为数组最后一个元素。

只要left和right指针没有相互交错，就执行划分操作。首先，移动left指针直到找到一个元素比主元大。对right指针，我们做同样的事情，移动right指针直到我们找到一个元素比主元小。

当左指针指向的元素比主元大且右指针指向的元素比主元小，并且此时左指针索引没有右指针索引大，意思是左项比右项大（值比较）。我们交换它们，然后移动两个指针，并重复此过程。

在划分操作结束后，返回左指针的索引，用来处创建子数组。

让我来一步步地看一个快速排序的实际例子：

image-20220209200009889

给定数组[3, 5, 1, 6, 4, 7, 2]，前面的示意图展示了划分操作的第一次执行。

下面的示意图展示了对有较小值的子数组执行的划分操作（注意7和6不包含在子数组之内）：

image-20220209200218389

接着，我们继续创建子数组，请看下图，但是这次操作是针对上图中有较大值的子数组（有1的那个较小子数组不用再划分了，因为它仅含有一个项）。

image-20220209200239868

子数组（[2, 3, 5, 4]）中的较小子数组（[2, 3]）继续进行划分：

image-20220209200312567

然后子数组（[2, 3, 5, 4]）中的较大子数组（[5, 4]）也继续进行划分，示意图如下：

image-20220209200345393

最终，较大子数组[6, 7]也会进行划分（partition）操作，快速排序算法的操作执行完成。

6. 希尔排序

「希尔排序」是以它的创造者（Donald Shell）命名的。这个算法在插入排序的基础上做了很大的改善。希尔排序的核心理念与插入排序不同，它会首先比较距离较远的元素，而非相邻的元素。和简单地比较相邻元素相比，使用这种方案可以使离正确位置很远的元素更快地回到合适的位置。当开始用这个算法遍历数据集时，所有元素之间的距离会不断减小，直到处理到数据集的末尾，这时算法比较的就是相邻元素了。

希尔排序的工作原理是，通过定义一个间隔序列来表示在排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列，不过对于大部分的实际应用场景，算法要用到的间隔序列可以提前定义好。有一些公开定义的间隔序列，使用它们会得到不同的结果。在这里我们用到了 Marcin Ciura 在他 2001 年发表的论文“Best Increments for the Average Case of Shell Sort”（http:bit.ly/1b04YFv,2001）中定义的间隔序列。这个间隔序列是：701, 301, 132, 57, 23,10, 4, 1。在用它进行日常编码之前，我们先通过一个小的数据集合来看看这个算法是怎么运行的。

接下来看下希尔排序算法的代码：

function shellSort(dataList, gaps = [5, 3, 1]) {
  for (let g = 0; g < gaps.length; g++) {
    for (let i = gaps[g]; i < dataList.length; i++) {
      let temp = dataList[i];
      let j = i;
      for (; j >= gaps[g] && dataList[j - gaps[g]] > temp; j -= gaps[g]) {
        dataList[j] = dataList[j - gaps[g]];
      }
      dataList[j] = temp;
    }
  }
}

7. 堆排序

「堆排序」（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

img

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

img

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

「大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]」

「小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]」

ok，了解了这些定义。接下来，我们来看看堆排序的基本思想及基本步骤：

「堆排序的基本思想是」：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

「步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。」

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

img

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

img

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

img

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

img

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

「步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。」

1. 将堆顶元素9和末尾元素4进行交换

img

1. 重新调整结构，使其继续满足堆定义

img

1. 再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.

img

后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

再简单总结下堆排序的基本思路：

1. 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆。
2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端。
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

接下来看下堆排序算法的代码：

function buildMaxHeap(dataList) { // 建立大顶堆
  for (let i = Math.floor(dataList.length / 2); i >= 0; i--) {
    heapify(dataList, i, dataList.length);
  }
}

function heapify(dataList, i, len) { // 堆调整
  let left = 2 * i + 1, right = 2 * i + 2, largest = i;
  if (left < len && dataList[left] > dataList[largest]) {
    largest = left;
  }
  if (right < len && dataList[right] > dataList[largest]) {
    largest = right;
  }
  if (largest != i) {
    swap(dataList, i, largest);
    heapify(dataList, largest, len);
  }
}

function swap(dataList, i, j) {
  const temp = dataList[i];
  dataList[i] = dataList[j];
  dataList[j] = temp;
}

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

8. 计数排序

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

「计数排序的特征」

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在「基数排序」中的算法来排序数据范围很大的数组。

通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。

算法的步骤如下：

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

下图演示了计数排序的过程

img

接下来看下计数排序算法的代码：

function countingSort(dataList, maxValue) {
  const bucket = new Array(maxValue + 1);
  let sortedIndex = 0;
  for (let i = 0; i < dataList.length; i++) {
    if (!bucket[dataList[i]]) {
      bucket[dataList[i]] = 0;
    }
    bucket[dataList[i]]++;
  }

  for (let j = 0; j < maxValue + 1; j++) {
    while (bucket[j] > 0) {
      dataList[sortedIndex++] = j;
      bucket[j]--;
    }
  }
}

9. 桶排序

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

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

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

什么时候最快？

当输入的数据可以均匀的分配到每一个桶中。

什么时候最慢？

当输入的数据被分配到了同一个桶中。

示意图

元素分布在桶中：

img

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

img

接下来我们来看看桶排序的代码：

function bucketSort(dataList, bucketSize = 5) { // 设置桶的默认数量为5
  if (dataList.length === 0) {
    return dataList;
  }
  let minValue = dataList[0], maxValue = dataList[0];
  for (let i = 1; i < dataList.length; i++) {
    if (dataList[i] < minValue) {
      minValue = dataList[i]; // 输入数据的最小值
    } else if (dataList[i] > maxValue) {
      maxValue = dataList[i]; // 输入数据的最大值
    }
  }

  //桶的初始化
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  const buckets = new Array(bucketCount);
  for (let i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }
  //利用映射函数将数据分配到各个桶中
  for (let i = 0; i < dataList.length; i++) {
    buckets[Math.floor((dataList[i] - minValue) / bucketSize)].push(dataList[i]);
  }
  dataList.length = 0;
  for (let i = 0; i < buckets.length; i++) {
    insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序
    for (let j = 0; j < buckets[i].length; j++) {
      dataList.push(buckets[i][j]);
    }
  }
  return dataList;
}

10. 基数排序

「基数排序」是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

「算法描述」

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）

「基数排序动图演示」

img

接下来我们来看看基数排序的代码：

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