关于JavaScript简单排序算法

朱雀 2024-03-29 14:35 147阅读 0赞

转自：[微点阅读][Link 1] [https://www.weidianyuedu.com][Link 1]

排序是程序员处理数据处理时最常见的问题之一。在此文中，我们将介绍一些每个程序员都应该掌握的简单[排序算法][Link 2]。所有这些都被认为很简单，因为它们的时间复杂度均为O（n²）。

我还建议将TopTal的排序算法动画或Visualgo的排序部分加入书签，以便在阅读本文时可视化这些算法并在整个编程过程中提供帮助。记住，程序员最好的朋友是互联网！

## **交换助手方法** ##

所有这些算法都涉及交换数组中的元素。为了更好地理解算法的工作原理，我们将抽象出一个称为“交换”的可重用函数。“交换”接收一个数组，并交换该数组的两个索引。这是JS和[Ruby][]中的实现：

functionswap(arr, index1, index2){let temp = arr[index1];    arr[index1] = arr[index2];    arr[index2] = temp;}

## **冒泡排序** ##

这些简单的排序算法中的每一个都从定义要排序的部分开始，然后从该排序的部分向外移动。[冒泡排序][Link 3]是从找到数组中的最大值并将其移到最后一个元素（已排序的部分）开始的。然后重复执行，直到排序的部分封装了整个数组。

在上方，我们看到了冒泡排序的名称-通过不断比较两个元素并将它们交换来将最高元素冒到顶部。当数字在上面的GIF中变为橙色时，将被视为“已排序”，并且排序从头开始。然后，它将继续该过程，直到对整个数组进行排序为止。

在下面的实现中，我将跟踪两个变量-currentIndex（排序比较的对象）和endIndex（已排序的部分）。

## **选择排序** ##

选择排序基本上与冒泡排序相反。排序不是查找最大的元素并将其冒泡到顶部，而是查找数组中的最小元素并将其移动到数组的开头- 新的sorted section。然后重复执行，直到排序的部分包含整个数组。

选择排序之所以得到它的名称，是因为它遍历数组并选择最低的元素，只有在完成遍历整个数组后才交换它。

在下面的实现中，我这次将跟踪3个变量-最小的元素，要与之比较的当前元素以及已排序部分的开头。

## **插入排序** ##

最后，我们到达插入排序。插入排序与我们前面讨论的前两种排序略有不同，因为它不会首先找到最高或最低的数字-它将数组中的第一个数字视为已排序，然后将数字插入到排序中。

在上面的GIF中，我们发现交换在这种情况下有点不同-我们正在交换元素的下一个索引，以便为我们要比较的当前值腾出空间-以便找到正确的位置来插入它。

在实现中，我们要跟踪三个变量-我们正在排序的部分的beginIndex，我们要检查的currentIndex和我们要比较的currentVal。

请记住，这些排序算法在最坏的情况下都具有O（n²）的时间复杂度，因此如果处理大量未排序的数据，它们可能会非常慢。但是，这些算法充其量只能是O（n），因此，如果你拥有一组几乎可以排序的数据，则这些实现中的任何一种都应该可以快速运行。

[Link 1]: https://www.weidianyuedu.com/
[Link 2]: https://so.csdn.net/so/search?q=%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95&spm=1001.2101.3001.7020
[Ruby]: https://so.csdn.net/so/search?q=Ruby&spm=1001.2101.3001.7020
[Link 3]: https://so.csdn.net/so/search?q=%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F&spm=1001.2101.3001.7020