英文 | https://blog.bitsrc.io/a-guide-to-sorting-algorithms-in-javascript-5b32da4eae1e
翻译 | 杨小爱
排序被认为是许多编程语言中的一个重要概念，因为它可以帮助我们以更快、更轻松的方式定位元素。
在这篇文章中，我们将使用排序算法对数组进行排序。JavaScript 中至少有 8 种不同的排序算法。为了使这篇文章简短但仍然充满有用的知识，我将重点介绍以下4种算法：
- 冒泡排序
- 插入排序
- 归并排序
- 快速排序
1、冒泡排序
冒泡排序算法是一种非常常见的算法，通常是计算机科学课程中最先教授的内容之一。这是因为冒泡排序的工作方式与我们人类对项目进行排序的方式非常相似。
让我们从创建一个名为 bubbleSort 的函数开始。该函数将接受一个数组作为参数，它将对其进行操作以进行排序，然后将该数组返回给我们。
在这个算法中，我们将创建一个循环，将一个项目与数组中的下一个项目进行比较。如果当前项大于下一项，则它们将被交换。这个循环将不断重复，直到我们遇到当前项目都不大于它旁边的项目的场景。这就是为什么我们将使用 do while 循环而不是常规的 while 循环。
do while 循环需要一个参数，它将在运行前检查。让我们将此参数命名为 swap 并将其初始值设置为 false。
在循环内部，我们将检查当前项是否大于数组中的下一项。如果是，那么我们将首先将其存储在一个临时变量中，然后执行交换。为了指示交换已执行，我们将交换的值设置为 true。
要测试此算法，只需创建一个数字数组并将其传递给 bubbleSort 函数，如下所示：
const nums = [5, 10, 1, 9, 2, 8, 3, 7, 4, 6]
bubbleSort(nums)
在您的输出中，您会注意到算法在终止之前多次打印出最终结果。这是因为该算法对数组的所有元素进行最后一次运行，以确保它们正确排序。
2、插入排序算法
在插入排序算法中，我们让代码相信数组中的一项是排序列表。然后比较它之前的数组中的所有项目，并决定需要在数组中插入“排序列表”的位置。
这对您来说可能听起来有点混乱。这是有道理的，因为我们需要两个循环，一个在另一个循环中，以执行此算法。
首先，我们将创建一个名为 insertSort 的函数，它将数组作为参数。我们将使用嵌套循环来执行排序。
以下是循环的工作方式。
首先，我们将从数组中取出一个元素并检查它是否大于或小于它旁边的元素。外部 for 循环将从数组的第二个元素开始，并将运行整个数组长度。
内循环将从数组的开头开始，一直运行到外循环的当前元素。每次外循环的迭代变量的值增加时，内循环也会重置。
至于实际的排序，我们将比较外循环元素和内循环元素。如果外循环的元素较小，那么我们将其移动到内循环元素的位置，反之亦然。为此，我们将使用数组的 slice 方法。
让我们使用我们之前使用的相同数组来测试这个算法。
const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
insertionSort(numbers)
这应该有效！如果考虑 8 的移动，您会注意到 8 开始在同一位置停留一段时间，并且每次迭代的持续时间变长。那是因为，算法遍历数组的所有项，然后递增外循环迭代器的值，然后当它遇到元素 8 时，它将在移动到数组中的下一个元素之前对其进行处理。
3、归并排序算法
分而治之！这就是归并排序算法的工作原理。该算法将数组分解为更小的数组。然后它将对这些较小的数组进行排序，因为它们的大小较小，因此速度更快。最后，将较小的数组组合在一起为我们提供最终的排序数组。
冒泡和插入排序算法使用迭代，而归并排序使用递归。递归是函数调用自身的地方。另一方面，迭代涉及我们的代码中多次运行代码块的其他内容。
在这里，我们将数组分成两部分，然后将其分成更小的部分，直到我们得到一组数组，其中每个数组只包含 2 个元素。然后我们将简单地通过比较哪个元素更大/更小来对这个小数组进行排序，然后再次连接这些数组。
让我们首先创建一个名为divide的函数，它将接收一个数组作为参数。然后该函数将检查数组的长度是否已经小于 2，因为如果是，则不需要除以任何内容，因为小于 2 是 1，并且数组中实际上没有其他任何内容来比较。在这种情况下，算法将简单地将相同的数组返回给我们。
如果数组长于 2，那么我们将把它分成两部分。首先我们需要找到数组的中间数。一旦我们得到它，我们将使用它 splice 方法来创建两个较小的数组。
我们将创建另一个执行实际排序的函数。我会叫它......种类。sort 函数将两个小数组作为参数，并分别对它们进行排序，然后将它们连接在一起。该函数将包含一个数组，其中将存储已排序的元素。
会有这样一种情况，我们已经对两个较小的数组进行了排序，但原始数组中仍有元素。在这种情况下，我们需要首先将两个小数组连接在一起，并将剩余的元素放入一个新数组中。
我们可以使用扩展运算符 ( ... ) 将元素“扩展”到这个新数组中。
如上所示，我们在除法函数中使用了排序函数。并且，我们将划分函数作为参数传递给排序函数。衔尾蛇的一个非常复杂的案例。
您可以通过将数字数组传递给除法函数来测试此算法。
const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
console.log(divide(numbers))
4、快速排序
这是遵循“分而治之”方法的另一种算法。该算法首先创建两个较小的数组，并从数组中选取一个索引。数组的所有元素都与该元素进行比较，并根据比较被推入两个数组之一。然后对两个数组之一进行排序。
与本文中的所有其他算法一样，我们将创建一个将数字数组作为输入参数的函数。如果数组只有一个元素，可以忽略排序并返回相同的数组。
然后我们将选择数组的元素将它存储在一个单独的变量中。然后，我们将创建两个数组，其中的元素将在与数组的最后一个元素进行比较后被推送。为此，我们将使用 for 循环遍历数组中的每个元素。
与 mergeSort 类似，我们将使用扩展运算符 ( ... ) 将两个数组中的元素和所选元素插入到新的最终数组中。
用一组数字测试这个算法应该会给我们以下输出：
const numbers = [8, 5, 6, 9, 3, 1, 4, 2, 7, 10]
quickSort(numbers)
// Output
5 6
3 4 5 6
1 2 3 4 5 6
8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10 // Final Answer
结论
在这篇文章中，我们研究了 JavaScript 中一些众所周知的排序算法。这些算法中的每一个都有自己的优点和缺点。
冒泡排序算法可能更容易理解，但它是本文四种算法中效率最低的。如果我们给它一个包含 10 个元素的数组，那么更糟糕的是它会将每个元素与列表中的每个其他元素进行比较，导致最多 100 (10*10) 个循环。
插入排序使用两个循环。并且由于这些循环被放置在另一个循环中，时间复杂度将为 0(n^2) 形式，其中 n 是数组中的元素数。一线希望，如果数组元素需要较少的排序，该算法将比冒泡排序执行得更好。
归并排序使用递归，极大地提高了排序过程的效率。归并排序要求算法至少遍历数组的每个元素一次。但是对于每次递归调用，我们只操作一半的元素。所以即使元素数量增加到原来大小的两倍，算法也只需要我们再调用一次递归。
快速排序是本文四种算法中最有效的算法。与归并排序类似，该算法也需要至少一次遍历整个数组。但是数组大小的任何增加都不会导致任何类型的操作增加。将数组大小加倍只会导致算法的一个额外操作级别。
最后，感谢您阅读到此！我希望它能帮助你更好地理解 JavaScript 算法。如果你喜欢这篇文章，那么请记得给我点赞。同时，也欢迎您发表评论，提出任何问题！
