不确定这种插入排序的实现是否正确？

Question

我发现这种插入排序的实现避免了使用我在大多数视频解释中看到的典型 while 循环。我不确定这是否有效。这不会与冒泡排序几乎相同吗？使用它真的会有什么特别的好处吗？以下是我对插入排序和冒泡排序的实现：

let arr = [1, 4, 6, 7, 8, 6, 3, 4, 5, 6, 6, 7];

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

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

Answer 1

您的冒泡排序实现并不是真正的冒泡排序 - 相反，正如您注意到的那样，它与插入排序实现基本相同。

使用冒泡排序，您遍历列表并交换相邻元素，每次更改比较的索引 - 当您到达末尾时，您从数组的开头重新开始并再次执行，并且以此类推，直到它被排序。 (Nice visualization.)那不是你在做的。

使用插入排序，你有一个完全排序的数组部分，和一个未修改的数组部分，从未修改的部分中取出元素并将它们放在排序部分的正确位置，然后再继续下一个未排序的部分物品。 (Nice visualization.)这就是您在此处的两个实现中所做的。

Would there really be any specific benefit of using this?

没有。这两种排序算法都远不如归并排序（及其变体）。如果您需要对数组进行排序，目前最好的方法是使用 built-in .sort 函数，它在后台实现了合并排序，并且比您可以编写的任何排序算法都快得多你自己在 JavaScript.

不确定这种插入排序的实现是否正确？

Unsure if this implementation of insertion sort is correct?

javascript

sorting

algorithm

bubble-sort

insertion-sort