JavaScript - 插入排序算法

插入排序是一种排序算法，其工作原理与我们玩扑克牌时对扑克牌进行排序的方式非常相似。插入排序是通过插入排序将元素按顺序排列起来的。

在该算法中，数组将被虚拟地分成两部分:已排序部分和未排序部分。未排序部分中的值将被拾取并放置在满足排序顺序的正确位置。

插入排序是一种简单的算法，实现也很简单。通常，该算法对于智能数据值非常有效。这适用于已经部分排序的数据集。

插入排序的工作原理?

考虑一个数组，其中包含一些未排序的随机元素。我们可以通过执行插入排序来对元素进行排序。那么，让我们检查一下下面的场景。

输入:[24, 22, 26, 10, 12];
输出:[10, 12, 22, 24, 26];

为了了解插入排序的工作原理，假设数组 arr=[24, 22, 26, 10, 12]。

第一遍

• 在插入排序中，首先比较数组中的初始两个元素。
• 此处 22 小于 24，因此它们不是按升序排列的，并且 24 的位置不正确。因此，将 22 和 24 交换。现在，24 存储在一个子数组中。

第二遍

• 现在，比较数组中的下两个元素。

• 这里，元素 24 和 26 都按升序排列，因为 26 大于 24。因此不会发生交换。
• 24 也存储在子数组与 22 一起。

第三遍

• 假设子数组中有两个元素 22 和 24。
• 现在比较接下来的两个元素 10 和 26。

• 由于 10 小于 26，因此交换这两个值。

• 即使交换后，10 和 24 仍然处于排序状态，因此再次交换。

• 10 和 22 仍然处于排序状态，因此再次交换。

• 现在，10 位于正确的位置。

第四遍

• 目前，已排序的子数组分别为 10、22 和 24。
• 比较接下来的两个元素 26 和 12。

• 由于它们未排序，因此交换两个值。

• 现在，12 小于 24。因此交换它们。

• 这里 12 小于 22，它们未排序，因此交换它们的位置。

• 现在，12 位于正确的位置，数组已完美排序。

算法

使用插入排序算法对大小为 n 的数组按升序排序。

• 如果它是第一个元素，则它已经排序。返回 1;
• 选择下一个元素
• 与已排序子列表中的所有元素进行比较
• 移动已排序子列表中所有大于待排序值的元素
• 插入值
• 重复操作，直到列表排序完成

插入排序的实现

以下是插入排序的一个例子

<!DOCTYPE html>
<html>
   <head>
      <title>Insertion Sort Algorithm</title>
   </head>
   <body>
   <p id = "demo"></p>
      <script>
         function insertionSort(arr){
            let n = arr.length;
            for(let i = 1; i < n; i++){
               let current = arr[i];
               let j = i-1; 
               while ((j > -1) && (current < arr[j])) {
                  arr[j+1] = arr[j];
                  j--;
               }
               arr[j+1] = current;
            }
            return arr;
         }
         let arr = [24, 22, 26, 10, 12];
         document.getElementById("demo").innerHTML = insertionSort(arr);
      </script>
   </body>

输出

让我们看看上面代码片段的输出。

[10, 12, 22, 24, 26]