使用 JavaScript 實作插入排序以升序對數字數組進行排序

陣列排序的藝術在程式設計領域至關重要，因為它可以有效地組織和操作資料。當談到實現可靠的排序演算法時，插入排序成為一種通用且有效的選擇。在本文中，我們深入研究 JavaScript 的複雜世界，探索實現插入排序以按升序排列數字數組的過程。透過理解演算法的基本機制並利用 JavaScript 的強大功能，開發人員可以釋放有效排序和組織數值資料的潛力，從而提高應用程式的效能和可用性。

問題陳述

目前的挑戰涉及利用 JavaScript 實作插入排序演算法的任務，以便按升序排列數字數組。主要目標是設計一個程序，可以智慧地重新排列給定數組的元素，確保每個後續元素根據其數值放置在相對於前面元素的正確位置。舉個例子，假設我們提供了一個陣列

[9, 2, 7, 4, 1]

執行插入排序演算法後，預期結果將是一個遵循遞增順序的數組，例如

[1, 2, 4, 7, 9]

方法

在本文中，我們將看到多種不同的方法來解決 JavaScript 中的上述問題 -

• 基本插入排序

• #二進位插入排序

• #遞迴插入排序

#方法一：基本插入排序

基本插入排序演算法在陣列中維護一個已排序的子陣列。從第二個元素開始，每個元素與子數組中的前一個元素進行比較，如果較小則向右移動。此過程將持續進行，直到找到正確的位置並插入該元素。對所有元素重複此過程，從而產生完全排序的陣列。

範例

insertionSort 函數將陣列 arr 作為輸入，並傳回使用插入排序演算法排序的陣列。它從第二個元素開始迭代，並將其儲存在當前變數中。 while 迴圈將目前元素與已排序子數組中的先前元素進行比較，將較大的元素向右移動。循環繼續，直到到達數組的開頭或找到更小的元素。然後將目前元素插入到已排序子數組中的正確位置。對所有元素重複此過程，從而產生排序數組。

function insertionSort(arr) {
   for (let i = 1; i < arr.length; i++) {
      let current = arr[i];
      let j = i - 1;
      while (j >= 0 && arr[j] > current) {
         arr[j + 1] = arr[j];
         j--;
      }
      arr[j + 1] = current;
   }
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(insertionSort(arr));

輸出

以下是控制台輸出 -

[ 1, 2, 4, 7, 9 ]

方法二：二分插入排序

二分插入排序演算法透過在已排序的子數組中利用二分搜尋來確定每個元素的正確位置，從而提高了基本插入排序的效率。不是線性搜索，而是透過將當前元素與子數組的中間元素進行比較來執行二分搜索，並相應地調整搜索邊界。確定插入點後，將向右移動元素以騰出空間，然後插入目前元素。對所有元素重複此過程，從而產生完全排序的陣列。

範例

binaryInsertionSort 函數採用陣列 arr 並傳回使用二進位插入排序演算法排序的陣列。它從第二個元素開始迭代，假設第一個元素已排序。當前元素儲存在目前變數中。該演算法在已排序的子數組中執行二分搜索，透過將當前元素與中間元素進行比較並調整搜尋邊界來找到當前元素的正確位置。一旦找到位置，演算法就會將元素向右移動並將當前元素插入到正確的位置。對所有元素重複此過程，從而產生排序數組。

function binaryInsertionSort(arr) {
   for (let i = 1; i < arr.length; i++) {
      let current = arr[i];
      let left = 0;
      let right = i - 1;
      while (left <= right) {
         let mid = Math.floor((left + right) / 2);
         if (current < arr[mid]) {
            right = mid - 1;
         } else {
            left = mid + 1;
         }
      }
      for (let j = i - 1; j >= left; j--) {
         arr[j + 1] = arr[j];
      }
      arr[left] = current;
   }
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(binaryInsertionSort(arr));

輸出

以下是控制台輸出 -

[ 1, 2, 4, 7, 9 ]

方法三：遞歸插入排序

遞歸插入排序演算法是插入排序的遞歸版本，使用遞歸對陣列進行排序。對於大小為 1 或更小的子數組，它認為它們已經排序。對於較大的子數組，它會遞歸呼叫本身來對沒有最後一個元素的子數組進行排序。遞歸呼叫傳回並對子數組進行排序後，演算法將最後一個元素放置在已排序子數組中的正確位置。這是透過將最後一個元素與已排序子數組中的元素進行比較並在必要時將它們向右移動來實現的。重複此過程，直到所有元素都插入到正確的位置，從而形成完全排序的陣列。

範例

recursiveInsertionSort 函數遞歸地將插入排序演算法套用到輸入陣列。它檢查數組是否已經排序，如果是則返回。否則，它會在大小為 n - 1 的子數組上遞歸呼叫自身。遞歸呼叫後，函數使用 while 迴圈將最後一個元素與已排序子數組中的元素進行比較。如果某個元素較大，則會向右移動。此過程持續進行，直到循環到達數組的開頭或找到更小的元素。最後，最後一個元素被插入到正確的位置。對所有元素重複此過程，從而產生排序數組。

function recursiveInsertionSort(arr, n = arr.length) {
   if (n <= 1) return arr;
 
   recursiveInsertionSort(arr, n - 1);
 
   let last = arr[n - 1];
   let j = n - 2;
 
   while (j >= 0 && arr[j] > last) {
      arr[j + 1] = arr[j];
      j--;
   }
 
   arr[j + 1] = last;
 
   return arr;
}
 
const arr = [9, 2, 7, 4, 1];
console.log(recursiveInsertionSort(arr));

輸出

以下是控制台輸出 -

[ 1, 2, 4, 7, 9 ]

结论

最终，使用 JavaScript 实现插入排序算法以升序排列数字数组，对于寻求熟练排序方法的开发人员来说是一个精明的选择。通过迭代地将元素放置在适当的位置，该算法展示了一种组织数值数据的敏锐方法。虽然插入排序可能不像其他排序技术那样广受好评，但它的效率和简单性使其在某些情况下成为非常宝贵的工具。在 JavaScript 中使用此算法使开发人员能够在其编码库中使用鲜为人知但功能强大的工具，从而生成精简且有序的数组。总之，利用 JavaScript 中插入排序算法的强大功能，对于那些在数组排序中寻求精确性和优雅性的人来说，是一种不切实际的努力。

以上是使用 JavaScript 實作插入排序以升序對數字數組進行排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！