如何在 JavaScript 中实现插入排序？

插入排序

插入排序是一种排序算法，其工作方式非常类似于我们在玩牌时整理扑克牌的方式。以排序的方式排列元素。在此算法中，数组将被虚拟地分成两个部分，即已排序部分和未排序部分。未排序部分中的值将被选取并放置在其满足排序顺序的正确位置。

插入排序是一种简单易于实现的算法。通常，此算法对于少量数据值有效。它适用于已经部分排序的数据集。

让我们看看一些输入和输出场景

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

Input = [24, 22, 26, 10, 12]; 
Output = 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 并且它们未排序，因此交换它们。


  • 完成，数组已完全排序。

算法

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

  • 如果它是第一个元素，则它已经排序。返回 1；

  • 选择下一个元素

  • 与已排序子列表中的所有元素进行比较

  • 将已排序子列表中所有大于要排序的值的元素移位

  • 插入值

  • 重复此操作，直到列表排序

示例 1

以下是插入排序的示例：

<!DOCTYPE html> 
<html> 
   <title>Insertion Sort in JavaScript</title> 
<head> 
   <script> 
      function insertion_Sort(Array, arr_len) { 
         for (let x = 1; x < arr_len; x++) { 
            let item = Array[x]; 
            let y = x - 1; 
            while (y >= 0 && Array[y] > item) { 
               Array[y + 1] = Array[y]; 
               y = y - 1; 
            } 
            Array[y + 1] = item; 
         } 
      } 
      document.write("The sorted array will be: ");  
      function SortedArray(Array, arr_len) { 
         for (let x = 0; x < arr_len; x++) 
         document.write(Array[x] + " "); 
      }  
      let Array = [24, 22, 26, 10, 12]; 
      let arr_len = Array.length; 
      insertion_Sort(Array, arr_len); 
      SortedArray(Array, arr_len); 
   </script>   
</head> 
<body> 
</body> 
</html>

示例 2

使用 unshift() 方法

此方法用于在数组的起始位置添加一个或多个元素。它返回数组的当前长度。

<html> 
<head> 
   <script> 
      function iSort(array) { 
         for (var p = 1; p < array.length; p++) { 
            if (array[p] < array[0]){ 
               array.unshift(array.splice(p,1)[0]); 
            } 
            else if (array[p] > array[p-1]) { 
               continue; 
            } 
            else { 
               for (var q = 1; q < p; q++) { 
                  if (array[p] > array[q-1] && array[p] < array[q]){ 
                     array.splice(q,0,array.splice(p,1)[0]); 
                  } 
               } 
            } 
         } 
         return array; 
      } 
      document.write(iSort([0,-3,5,8,2,7,6])); 
   </script> 
</head> 
</html>

更新于：2022-09-23

1K+ 次查看

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告

© . All rights reserved.