JavaScript 常见的三种数组排序方式

发布网友 发布时间：2024-09-29 23:31

我来回答

共1个回答

热心网友 时间：2024-10-04 01:52

冒泡排序的英文名是 Bubble Sort，它是一种简单直观的排序算法。简单来说，它会重复走访过要排序的数列，一次比较两个数，如果他们的顺序错误就会将他们交换过来，直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。冒泡排序算法思路：首先我们需要做一个内层循环来比较每对相邻元素的大小，如果前面大于后面，就让他们交换位置，我们要让小的数在前面，大的数在后面。当内层循环结束时，在数组最后一位的元素，就一定是这个数组中最大的元素了。这时候除了最后一个元素不用再动以外（所以内层循环每循环一次就可以少循环一次），我们还要再来确定这个数组中第二大的元素，第三大的元素，以此类推。因此我们还需要一层外层循环。如果这个数组有 n 个元素我们就要确定 n - 1 个元素的位置，所以外层循环需要循环的次数就是 n - 1 次。实现方式可能有很多种，这只是我个人的想法。

选择排序英文叫法是 Selection sort，这也是一种简单直观的排序方法。这种排序首先会在未排序的数组中找到最小或者最大的元素，存放在排序数组的起始位置。然后再从未排序的数列中去找到这个数组中第二大或这第二小的数放在已排序的数之后，以此类推，不断重复直到所有元素排列完毕。算法思路（以按递增顺序排列为例）：我们需要内层循环找出未排序数列中的最小值，循环后找到未排序数列中的最小元素时记录最小的那个元素在数组中的索引值。用索引获得最小值的位置后把它放在数组的第一位。每经过一次内层循环，我们就能确定一个未排序数组中最小值的位置。在确定倒数第二个数的位置时，最后一个数的位置也自然而然地被确定了。因此数组中有 n 个元素我们就需要进行 n - 1 次内层循环，我们就用用外层循环来保持内层循环的重复进行。

插入排序英文称为 Insertion sort，插入排序也被叫做直接插入排序。它的基本思想是将一个未排序的元素插入到已经排序好的数组中，从而使得已排序的数组增加一个元素，通过插入不断完善已排序数组的过程，就是排序整个数组的过程。算法思路（以按递增顺序排列为例）：因为数组中第一个元素前面没有元素可以进行比较，所以我们从第二个元素开始比较，用 current 变量来进行存储当前要和别人比较的元素，用 preIndex变量 来方便我们去找当前准备插入元素之前的元素。内层循环就是按顺序比较插入元素和之前元素的大小，来确定插入元素的位置。 preIndex 每比较一次就自减1 ，让准备插入元素和它之前的所有已排序元素都比较一遍。每当待插入元素比前一个数小了，前面的元素就往右挪一个位置，直到前一个数小于待插入数，跳出判断，待插入元素放在前一次判断挪动元素留出的空位上。由于我们提前用 current 保存了要插入的元素，所以要插入的元素不会因为前面的元素覆盖而丢失。每循环一次内层循环，我们就可以确定一个元素的插入位置。但由于我们内层循环是从第二个元素开始的（也就是索引为 1 的元素），因此如果有 n 个元素，我们就需要 n - 1 次内层循环。内存循环我们用外层循环来实现，外层循环就这么被定义完成了。

总结：

选择排序（一种不稳定的排序方法）优点：移动数据的次数已知（n-1次）；缺点：比较次数多。

冒泡排序优点：稳定；缺点：慢，每次只能移动相邻两个数据。

插入排序优点：稳定，快；缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

目录：