JavaScript中的初学者排序算法：冒泡、选择和插入排序

随意安排数据集只会增加更多时间和资源来管理和搜索。您的数据是否已排序将直接影响您可以使用哪些搜索方法，并且可能意味着搜索需要一百万次操作还是需要 10 次操作之间的差异，例如 Binary Search。

为简单起见，我们只关注从最小到最大对数字数组进行排序，但这些算法很容易修改以用于其他排序目标。请记住，这些是更通用的概念和模式，而不是排序数据的“操作方法”，因为您的特定实现可能有很大不同，但最终它可能在概念上类似于这些模式。

这是 50 个随机数的练习数组。

const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];

先决条件

我将通过 Big O Notation 的镜头来看待一切，因此了解复杂性如何随着时间的推移而增长将非常有帮助。

冒泡排序

这是排序方法的“Hello World”，没什么疯狂的，但它完成了工作。

对于数组中的每个项目，我们要检查下一个项目是否更大，如果是则交换它们在数组中的索引。为了避免重新比较排序后的数字，我们将从数组的后面开始，而另一个 for loop 获取前面的数字。通过这种方式，所有最大值最终都会累积或“冒泡”。

图形/动画感谢 VisuAlgo.net

我们的版本与动画相反，但已经足够接近了。

const bubble = arr => {
  const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];

  for (let i = arr.length; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) swap(arr, j, j + 1);
    };
  };

  return arr;
};

console.log(bubble(unsortedArr));

选择排序

选择排序的工作原理与冒泡排序相反，而冒泡排序将所有最大值推到末尾，现在我们将最小值推到开头。

每次遍历数组时，它都会选择最小值，如果它找到一个较低的值，则该值将成为新的最小值。循环完成后，它将取最小值并将其放在数组的前面，然后再次开始循环。这样，每次迭代的最低值被堆叠到前面，直到整个数组被排序。

图形/动画感谢 VisuAlgo.net

const selection = arr => {
  const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]];

  arr.forEach((item, i) => {
    let min = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) min = j;
    };
    swap(arr, i, min);
  });

  return arr;
};

console.log(selection(unsortedArr));

插入排序

我个人最喜欢和性能最好的三个，insertion sort，更类似于手动排序的方式。

我们将数组视为两部分，已排序的和未排序的，每次我们找到一个新值时，我们都会循环返回以在已排序的一半中找到它的位置。随着每次添加，我们的排序组都会增长，直到它成为整个数组。

图形/动画感谢 VisuAlgo.net

const insertion = arr => {
  arr.forEach((item, i) => {
    let num = arr[i];
    let j;

    for (j = i - 1; j >= 0 && arr[j] > num; j--) {
      arr[j + 1] = arr[j];
    };
    arr[j + 1] = num;
  });

  return arr;
};

console.log(insertion(unsortedArr));

比较

使用大 O 表示法比较算法的一个问题是它基于最坏的情况，这可能在算法中是相同的，给人一种错误的错觉，即它们是相等的。虽然冒泡、选择和插入排序都是 O(n^2)，但这并不能告诉我们很多关于平均或最佳情况的情况，或者它们如何随数据结构而变化。

插入排序每次都获胜。它还具有在开始之前不需要拥有整个数组的好处，这使您可以在数据进入时实时对事物进行排序。

请记住这一点，因为在考虑数据的组织方式之前，您不应该决定哪种算法是“最好的”。

结论

这三种方法远非有效分类大量数据的最佳解决方案，但它们是最直观的方法之一，可以让您将脚趾伸入浩瀚的海洋。 🌊