【乱杀图解算法】JavaScript版排序算法，没有人比我更细！

站长

2023年06月22日 22:13 · 阅读数 16

前言

昨天面快手，前期项目八股那些答得起飞，然后让写一个排序算法，随便写一个我自己擅长的就行，结果冒泡排序我TM都没写出来，直接烂尾，淦！！！！！

面试官说没事没事写不出来没关系，那我问问你数据结构或者计网相关的吧，数组和链表啥区别？我答了时间复杂度和内存空间上的区别，然后内存空间答反了……

面试官内心os：给你机会你不中用啊（老头看手机） 👻 👻

好吧，今天就来好好复盘总结一下。

什么是排序算法

本质上来说，排序算法是一种将数据组织成特定顺序的计算机程序，比如将字母或数字按升序或降序排列。

排序算法的用途是什么

排序算法主要用于以有效的方式重新排列大量数据，以便可以更轻松地对其进行搜索和操作。

它们还用于提高其他算法的效率（比如搜索和合并），这些算法依赖于排序后的数据进行操作。

为什么排序算法如此重要

base 应用

排序算法用于按特定顺序组织数据，从而让搜索、访问和分析数据变得更加容易。

在许多应用中，排序是数据处理过程的关键部分，排序算法的效率会对系统的整体性能产生重大影响。

base 数据库

这使得用户可以快速找到所需的数据，而不用手动搜索大量未排序的数据。

base 搜索引擎

还比如说，在搜索引擎中，按相关性程度对搜索结果进行排序，通过这种方式对结果进行排序，用户可以快速找到他们要查找的信息，而不必筛选不相关的结果。

在许多科学和工程应用中，研究人员可以运行数据分析和模拟，以深入了解复杂系统，并对未来行为做出更准确的预测。

数据结构中不同类型的排序

这里有各种各样的排序算法。

而排序算法的选择取决于各种因素，比如数据集的大小，要排序的数据类型以及所需要的时间和空间复杂度。

基于比较的排序算法

它们比较数据集的元素，并根据比较结果确定它们的顺序。基于比较的排序算法的示例包括冒泡排序、插入排序、快速排序、归并排序和堆排序。

基于非比较的排序算法

它们不直接比较元素，而是使用数据集的其他属性来确定它们的顺序。非基于比较的排序算法的示例包括计数排序、基数排序和桶排序。

就地排序算法

这些算法对数据集进行就地排序，这意味着它们不需要额外的内存来存储中间结果。就地排序算法的示例包括冒泡排序、插入排序、快速排序和外壳排序。

稳定的排序算法

它们保持数据集中相等元素的相对顺序。稳定排序算法的例子包括插入排序、归并排序和Timsort。

自适应排序算法

它们利用数据集中的任何现有顺序来提高效率。自适应排序算法的例子包括插入排序、冒泡排序和Timsort。

你需要知道的十大排序算法

现在让我们来看看十种最常用的排序算法，以便在选择一种算法时有所注意。

⭐ 冒泡排序

冒泡排序是一种简单的排序算法，它重复遍历给定的项目列表，比较每一对相邻的项目，如果它们的顺序错误，就交换它们。该算法一直持续到遍历整个列表而不交换任何项。冒泡排序有时也被称为“下沉排序”。

【乱杀图解算法】JavaScript版排序算法，没有人比我更细！

从列表的开头开始，比较每个相邻的对，如果它们的顺序不对，交换它们的位置(后一个比前一个小)。每次迭代之后，需要比较的元素(最后一个)会减少一个，直到没有其他元素需要比较为止。

冒泡排序的优缺点

冒泡排序被认为是一种相对低效的排序算法，因为它的平均复杂度和最坏情况复杂度都是O(n2)O(n^2)O(n2)。这使得它比大多数其他排序算法(如快速排序或归并排序)效率低得多。

例如，如果考虑对数字数组进行排序的算法，对包含10个数字的数组进行排序可能需要1秒，但对包含20个数字的数组进行排序可能需要4秒。

这是因为算法必须将数组中的每个元素与其他元素进行比较，因此对于较大的数组必须进行20次比较，而对于较小的数组只需进行10次比较。

然而，它非常容易理解和实现，并且经常被用作排序的入门和更复杂算法的构建块。但现在很少在实践中使用了。

冒泡排序的用例

冒泡排序是一种简单的算法，可用于对小列表或元素数组进行排序。它易于实现和理解，因此可以在简单性和清晰度比性能更重要的情况下使用。

教育的目的。它经常被用在计算机科学课程中作为一个简单排序算法的例子。通过学习冒泡排序，学生可以学习基本的排序技术，并了解算法的工作原理。

整理小数据集。它可以用于排序多达几百个元素的小数据集。在性能不是关键问题的情况下，冒泡排序是对小列表进行排序的一种快速简便的方法。

预先的数据。它可以用作更复杂排序算法的初步步骤。例如，如果数据已经部分排序，则可以使用冒泡排序在运行更复杂的算法之前对数据进行进一步排序。

用有限的资源排序数据。它在资源有限的情况下很有用，比如在嵌入式系统或微控制器中，因为它只需要很少的内存和处理能力。

构建更复杂算法的模块。它通常与归并排序或快速排序结合使用，并使用插入排序对小的子数组进行排序，因为这些其他算法可以在较大的数据集上获得更好的性能。

冒泡排序实现

使用嵌套循环遍历项。
比较列表中相邻的项。
如果项的顺序不对，就交换它们。
继续，直到列表排序完毕。

如下：

function bubbleSort(items) {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < items.length - 1; i++) {
      if (items[i] > items[i + 1]) {
        let temp = items[i];
        items[i] = items[i + 1];
        items[i + 1] = temp;
        swapped = true;
      }
    }
  } while (swapped);
  return items;
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(bubbleSort(items));

⭐ 插入排序

插入排序是另一种简单的算法，它一次构建一个最终排序的数组，它这样命名是因为较小的元素被插入到排序数组的正确位置。

【乱杀图解算法】JavaScript版排序算法，没有人比我更细！

部分排序列表最初只包含列表中的第一个元素。在每次迭代中，从“尚未检查顺序”的输入数据中删除一个元素，并将其插入已排序的列表中。

插入排序的优缺点

插入排序通常在实践中用于小数据集或作为更复杂算法的构建块。

就像冒泡排序一样，它的最坏情况和平均情况的时间复杂度是O(n2)O(n^2)O(n2)。但与冒泡排序不同，插入排序可用于对数据集进行就地排序，这意味着它不需要额外的内存来存储中间结果。

插入排序的用例

插入排序简单而高效，通常用于输入数据已经部分排序的情况，或者输入数据的大小相对较小的情况。它也用于对小数据集进行排序，以及为更复杂的算法构建模块，就像冒泡排序一样。

部分排序的数据。它非常适合数据已经部分排序的情况。在这种情况下，算法可以快速地将新元素插入到正确的位置，而不需要复杂的排序操作。

在线排序。它通常用于事先不知道输入数据的在线排序应用程序。在这些情况下，算法可以在接收到输入数据时对其进行增量排序。

自适应排序。插入排序是自适应排序的候选，因为它可以利用输入数据中的现有顺序。随着输入数据变得更加有序，算法的性能得到提高。

插入排序实现

取一个未排序的列表，选择第一项作为“枢轴”。
遍历列表，将枢轴插入已排序列表中的正确位置。
对列表中的下一项重复此过程。
继续，直到列表排序完毕。

比如：

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

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(insertionSort(items));

⭐ 快速排序

快速排序是一种流行的分治排序算法，它基于将数组划分为两个子数组的原则——一个包含比“枢轴”元素小的元素，另一个包含比枢轴元素大的元素。然后对这两个子数组进行递归排序。

快速排序的基本步骤包括:

从数组中选择一个枢轴元素。
将数组划分为两个子数组，一个包含比枢轴小的元素，另一个包含比枢轴大的元素。
使用快速排序对两个子数组进行递归排序。
组合两个已排序的子数组。

【乱杀图解算法】JavaScript版排序算法，没有人比我更细！

水平线是枢轴值。

快速排序的优点

它的平均时间复杂度是O(nlog⁡n)O(n \log n)O(nlogn)。

它只需要很少的额外内存，因为它对数组进行了排序。

它很容易实现并且被广泛理解。

它很容易被并行化。

快速排序的缺点

它的最坏情况下的时间复杂度是O(n2)O(n^2)O(n2)，当主节点选择不好时，使得它在某些情况下比其他算法(如归并排序或堆排序)效率更低。

Tips：我们不想选择一个太小或太大的枢轴，否则算法将在二次时间内运行。理想情况是选择中位数作为主点，但这并不总是可能的，除非我们对数据分布有先验知识。

快速排序的用例

快速排序作为一种高效的排序算法，有着广泛的应用。

大数据集。它的平均时间复杂度为O(nlog⁡n)O(n \log n)O(nlogn)，这意味着它可以快速排序大量数据。随机数据。它在随机排序的数据上表现良好，因为它依赖于pivot元素将数据划分为两个子数组，然后递归排序。当数据是随机的时，枢轴元素很可能接近中位数，从而获得良好的性能。

并行处理。它可以很容易地并行化，这使得它非常适合在多核处理器上对大型数据集进行排序。通过将数据分成更小的子数组，该算法可以同时在多个核上执行，从而提高性能。

外部排序。它通常被用作外部排序算法的一部分，用于对内存无法容纳的大数据进行排序。在这种情况下，数据被分成块，然后使用合并排序算法对其进行合并。

数据压缩。它被用在一些数据压缩算法中，比如bzip2压缩软件中使用的Burrows-Wheeler变换。该算法用于对Burrows-Wheeler矩阵中的数据进行排序，然后将其转换为压缩数据。

快速排序的实现

使用一个“支点”，最好是中位数，将列表分成两部分。快速将左部分和右部分进行排序。继续，直到列表排序完毕。

function quickSort(items) {
  if (items.length > 1) {
    let pivot = items[0];
    let left = [];
    let right = [];
    for (let i = 1; i < items.length; i++) {
      if (items[i] < pivot) {
        left.push(items[i]);
      } else {
        right.push(items[i]);
      }
    }
    return quickSort(left).concat(pivot, quickSort(right));
  } else {
    return items;
  }
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(quickSort(items));

桶排序

桶排序是一种对均匀分布的数据进行排序的有用算法，它可以很容易地并行化以提高性能。

桶排序的基本步骤包括:

创建一个空桶数组。
根据定义的函数将输入数据分散到桶中。
使用另一种算法或递归地使用桶排序对每个桶进行排序。
将每个桶中排序的元素收集到原始数组中。

【乱杀图解算法】JavaScript版排序算法，没有人比我更细！

桶排序的优点

它对于均匀分布的数据是有效的，平均情况的时间复杂度为O(n+k)O(n+k)O(n+k)，其中nnn是元素的数量，kkk是桶的数量。
它可以很容易地并行化，从而利用现代处理器中的多核。
它是稳定的，这意味着它保留了原始数组中相等元素的相对顺序。
它可以通过调整桶函数用于非均匀分布的数据。

Tips：

O(n+k)O(n+k)O(n+k) 的复杂度比O(n2)O(n^2)O(n2) 、O(n3/2)O(n^{3/2})O(n3/2)和O(n4/3)O(n^{4/3})O(n4/3) O(nlog⁡n)O(n \log n)O(nlogn) 更有效。这是因为它只需要执行线性数量的操作，而不管输入的大小。

例如，考虑一个对数字数组排序的算法。使用O(n2)O(n^2)O(n2)算法对十个数字的数组进行排序可能需要1秒，使用O(n3/2)O(n^{3/2})O(n3/2)算法对同一个数组进行排序可能需要0.5秒，使用O(nlog⁡n)O(n \log n)O(nlogn)算法对同一个数组进行排序可能需要0.1秒，但使用O(n+k)O(n+k)O(n+k)算法对同一个数组进行排序可能需要0.05秒。这是因为该算法不需要执行那么多比较。

桶式排序的缺点

对于非均匀分布的数据，桶排序比其他排序算法效率低，最坏情况下的性能为O(n2)O(n^2)O(n2)。此外，它需要额外的内存来存储桶，这对于非常大的数据集来说可能是一个问题。

桶排序的用例

就像快速排序一样，桶排序可以很容易地并行化并用于外部排序，但是桶排序在处理均匀分布的数据时特别有用。

对浮点数进行排序。在这种情况下，范围被划分为固定数量的桶，每个桶代表输入数据的一个子范围。然后将数字放入相应的桶中，并使用另一种算法(例如插入排序)进行排序。最后，将排序后的数据连接到单个数组中。
排序的字符串。字符串根据字符串的第一个字母分组到桶中。然后使用另一种算法或递归地使用桶排序对每个桶中的字符串进行排序。对字符串中的每个后续字母重复此过程，直到整个集合排序完毕。
直方图的一代。这可用于生成数据的直方图，直方图用于表示一组值的频率分布。在这种情况下，将数据范围划分为固定数量的桶，并计算每个桶中的值的数量。生成的直方图可用于可视化数据的分布。

桶排序实现

将项目列表分成“桶”。
每个桶使用不同的排序算法进行排序。
然后将桶合并回一个排序列表。

代码实现：

function bucketSort(items) {
  let buckets = new Array(items.length);
  for (let i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }
  for (let j = 0; j < items.length; j++) {
    let bucket = Math.floor(items[j] / items.length);
    buckets[bucket].push(items[j]);
  }
  for (let k = 0; k < buckets.length; k++) {
    buckets[k].sort();
  }
  return [].concat(...buckets);
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(bucketSort(items));

⭐ 归并排序

归并排序的基本思想是将输入列表分成两半，使用归并排序对每一半进行递归排序，然后将已排序的两半合并回一起。

合并步骤是通过重复比较每一半的第一个元素并将两个元素中较小的元素添加到排序列表中来执行的。这个过程不断重复，直到所有的元素都合并在一起。

【乱杀图解算法】JavaScript版排序算法，没有人比我更细！

首先，将列表划分为最小的单元(一个元素)，然后将每个元素与相邻列表进行比较，对两个相邻列表进行排序和合并。最后，对所有元素进行排序和合并。

归并排序的优点

在最坏的情况下，归并排序的时间复杂度为O(nlog⁡n)O(n \log n)O(nlogn)，这使得它比冒泡排序、插入排序或选择排序等其他流行的排序算法更有效。

归并排序也是一种算法，这意味着它保留相等元素的相对顺序。

归并排序的缺点

归并排序在内存使用方面也有一些缺点。

该算法在除法步骤中需要额外的内存来存储列表的两半，在合并步骤中需要额外的内存来存储最终排序的列表。在对非常大的列表进行排序时，这可能是一个问题。

归并排序的用例

归并排序是一种通用排序算法，可以并行化排序大型数据集和外部排序(如快速排序和桶排序)，它也通常用作更复杂算法(如冒泡排序和插入排序)的构建块。

稳定的排序。归并排序的稳定排序意味着它保留相等元素的相对顺序。这使得它在维护相等元素的顺序很重要的情况下非常有用，例如在金融应用程序中或为了可视化目的对数据进行排序时。
实现二分搜索。它用于有效地搜索排序列表中的特定元素，因为它依赖于排序的输入。归并排序可以用于有效地对二进制搜索和其他类似算法的输入进行排序。

归并排序实现

使用递归将列表拆分为更小的、排序的子列表
将子列表合并回一起，在合并时比较和排序项

代码实现：

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

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

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(mergeSort(items));

⭐ 选择排序

选择排序反复从列表的未排序部分中选择最小的元素，并将其与未排序部分的第一个元素交换。这个过程一直持续到整个列表排序完毕。

【乱杀图解算法】JavaScript版排序算法，没有人比我更细！

选择排序的优点

选择排序在某些应用程序中使用，在这些应用程序中，简单性和易于实现比效率更重要。

选择排序的缺点

尽管它很简单，但与其他排序算法(如归并排序或快速排序)相比，选择排序不是很有效。它最坏情况下的时间复杂度为0(n2)0 (n^2)0(n2)，而且对大列表进行排序可能需要很长时间。

选择排序也不是一种稳定的排序算法，这意味着它可能无法保持相等元素的顺序。

选择排序的用例

选择排序类似于冒泡排序和插入排序，因为它可以用来对小数据集进行排序，而且它的简单性也使它成为教授和学习排序算法的有用工具。其他用途包括:

用有限的内存排序数据。它只需要一定数量的额外内存来执行排序，这使得它在内存使用有限的情况下非常有用。
使用唯一值对数据进行排序。它不依赖于主要排序的输入，因此对于具有唯一值的数据集来说，它是一个很好的选择，而其他排序算法可能必须执行额外的检查或优化。

选择排序实现

遍历列表，选择最低的项
将最低的项目与当前位置的项目交换
对列表的其余部分重复此过程

function selectionSort(items) {
  let minIdx;

  for (let i = 0; i < items.length; i++) {
    minIdx = i;
    for (let j = i + 1; j < items.length; j++) {
      if (items[j] < items[minIdx]) {
        minIdx = j;
      }
    }
    let temp = items[i];
    items[i] = items[minIdx];
    items[minIdx] = temp;
  }
  return items;
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(selectionSort(items));

基数排序

基数排序背后的基本思想是通过按被排序的数字或字符中的每个数字分组来对数据进行排序，从右到左或从左到右。对每个数字重复这个过程，得到一个排序列表。

它的最坏情况性能是O(w⋅n){O(w\cdot n)}O(w⋅n)，其中nnn是键的个数，www是键的长度。

基数排序的优点

基数排序是一种线性时间排序算法，这意味着它的时间复杂度与输入数据的大小成正比。这使得它成为对大型数据集进行排序的有效算法，尽管对于较小的数据集，它可能不如其他排序算法那么有效。

它的线性时间复杂度和稳定性使它成为对大型数据集排序的有用工具，它的并行性(是的，这是一个实际的词)使它对分布式计算环境中的数据排序很有用。

基数排序也是一种稳定的排序算法，这意味着它保留相等元素的相对顺序。

基数排序的用例

基数排序可用于需要对大型数据集进行高效排序的各种应用程序。它对于排序字符串数据和固定长度的键特别有用，也可以用于并行和分布式计算环境。

并行处理。基数排序通常更适合于对大型数据集进行排序(优于归并排序、快速排序和桶排序)。像桶排序一样，基数可以有效地对字符串数据进行排序，这使得它适合于自然语言处理应用程序。
用固定长度的键排序数据。基数排序在对具有固定长度键的数据进行排序时特别有效，因为它可以通过每次检查每个键的一个数字来执行排序。

基数排序实现

比较列表中每一项的数字。
按数字分组。
按大小对组进行排序。
递归地对每个组进行排序，直到每个项都在正确的位置。

代码实现：

function radixSort(items) {
  let maxLength = false;
  let tmp = -1;
  let placement = 1;

  while (!maxLength) {
    maxLength = true;
    let buckets = Array.from({ length: 10 }, () => []);

    for (let i = 0; i < items.length; i++) {
      tmp = Math.floor(items[i] / placement);
      buckets[tmp % 10].push(items[i]);
      if (maxLength && tmp > 0) {
        maxLength = false;
      }
    }

    let a = 0;
    for (let b = 0; b < 10; b++) {
      let buck = buckets[b];
      for (let j = 0; j < buck.length; j++) {
        items[a] = buck[j];
        a++;
      }
    }

    placement *= 10;
  }
  return items;
}

let items = [6, 20, 8, 19, 56, 23, 87, 41, 49, 53];
console.log(radixSort(items));

结语

基本上我们比较常见的排序算法如上，其余的排序算法到了解程度就可以，前端人需要掌握的重点排序算法我也标注出来啦~duck放心食用 😘

本文转翻译自此，欢迎投稿优质技术文章