資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 JavaScript 實現插入排序以按升序對數字陣列進行排序
在程式設計領域，陣列排序的技巧至關重要，因為它允許高效地組織和操作資料。在實現可靠的排序演算法時，插入排序成為了一種用途廣泛且有效的選擇。本文深入探討了 JavaScript 的複雜世界，探索了實現插入排序以按升序排列數字陣列的過程。透過理解該演算法的底層機制並利用 JavaScript 強大的功能，開發人員可以釋放高效排序和組織數值資料的能力，從而提高應用程式的效能和可用性。
問題陳述
手頭的挑戰涉及使用 JavaScript 實現插入排序演算法的任務，目的是按升序排列數字陣列。主要目標是設計一個程式，智慧地重新排列給定陣列的元素，確保每個後續元素根據其數值相對於先前元素放置在正確的位置。例如，假設我們提供了一個數組
[9, 2, 7, 4, 1]
執行插入排序演算法後，預期結果將是一個符合升序排列的陣列，例如
[1, 2, 4, 7, 9]
方法
在本文中，我們將瞭解多種使用 JavaScript 解決上述問題陳述的方法：
基本插入排序
二分插入排序
遞迴插入排序
方法 1：基本插入排序
基本插入排序演算法在陣列中維護一個已排序的子陣列。從第二個元素開始，每個元素都與子陣列中的前一個元素進行比較，如果較小則向右移動。此過程持續進行，直到找到正確的位置並將元素插入。此過程對所有元素重複，從而得到一個完全排序的陣列。
示例
insertionSort 函式以陣列 arr 作為輸入，並使用插入排序演算法返回已排序的陣列。它從第二個元素開始迭代，將其儲存在 current 變數中。一個 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 ]
方法 2：二分插入排序
二分插入排序演算法透過在已排序的子陣列中利用二分查詢來確定每個元素的正確位置，從而提高了基本插入排序的效率。它不是線性搜尋，而是透過將當前元素與子陣列的中間元素進行比較並相應地調整搜尋邊界來執行二分查詢。一旦確定了插入點，則將右側的元素向右移動以騰出空間，並將當前元素插入。此過程對所有元素重複，從而得到一個完全排序的陣列。
示例
binaryInsertionSort 函式以陣列 arr 作為輸入，並使用二分插入排序演算法返回已排序的陣列。它從第二個元素開始迭代，假設第一個元素已排序。當前元素儲存在 current 變數中。該演算法在已排序的子陣列中執行二分查詢，以透過將其與中間元素進行比較並調整搜尋邊界來找到當前元素的正確位置。找到位置後，該演算法將元素向右移動，並將當前元素插入到正確的位置。此過程對所有元素重複，從而得到一個已排序的陣列。
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 ]
方法 3：遞迴插入排序
遞迴插入排序演算法是插入排序的遞迴版本，使用遞迴來排序陣列。對於大小為 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 中利用插入排序演算法的力量對於那些在陣列排序工作中尋求精確和優雅的人來說是一個奇幻的努力。
1K+ 閱讀量
