JavaScript 中的插入排序
簡介
在本文中，我們將解釋插入排序背後的思想是什麼，並在 JavaScript 中實現它。
插入排序是比較簡單的排序算法之一。它非常直觀、穩定、就地 和比較類型 .
一個穩定 排序算法是一種算法，其中具有相同鍵的兩個對像在排序輸出中出現的順序與它們在要排序的輸入數組中出現的順序相同。
換句話說，如果一個排序算法是穩定的，那麼等價元素在排序算法完成後會保持它們的相對位置。
就地 算法是一種不使用額外內存或數據結構的算法，重寫輸入數組或列表中元素的原始內存位置。
最後，一個比較算法 是在其執行期間僅通過單個抽像比較操作讀取列表元素的一種。根據您的數據類型和目標，可以通過關係運算符或自定義比較函數進行比較。
儘管對於排序算法而言它具有非常大的時間複雜度，但插入排序可能非常有用，有時甚至能夠勝過一些最有效的排序算法，例如 Quicksort 或合併排序 ，關於小型收藏。
它很少用作獨立算法 - 您通常會使用快速排序算法（如 Quicksort）並使用插入排序完成最後的“鬆散端”，因為它對於該任務非常有效。
插入排序
插入排序背後的想法經常被比作人們在玩拉米紙牌時對一手牌進行排序的方式。
在這種紙牌遊戲中，莊家向每位玩家發牌。然後，玩家一張一張地拿給他們的卡片，將它們按升序排列在手中。
在這整個過程中，玩家手中拿著一摞排序好的牌，而他們從中抽出新牌的未排序的那摞就在他們面前。
插入排序的一個非常有用的特性是它不需要提前知道整個數組就可以對其進行排序——它只是將給定的元素一個一個地插入。
當我們想在已經排序的數組中添加更多元素時，這真的很方便，因為插入排序會將新元素添加到適當的位置，而不需要使用整個集合。
這是插入排序如何工作的直觀表示：
插入排序實現
現在我們了解了插入排序背後的想法，我們可以繼續實現：
function insertionSort(inputArr) {
let n = inputArr.length;
for (let i = 1; i < n; i++) {
// Choosing the first element in our unsorted subarray
let current = inputArr[i];
// The last element of our sorted subarray
let j = i-1;
while ((j > -1) && (current < inputArr[j])) {
inputArr[j+1] = inputArr[j];
j--;
}
inputArr[j+1] = current;
}
return inputArr;
}
迭代從第二個元素開始。我們認為第一個元素默認排序。對於每次迭代，我們都會跟踪 current 元素。每個current element 將是未排序數組的第一個元素 - 並且它之前的每個元素都將屬於已排序數組。
通過 while 循環，我們遍歷排序後的數組並將元素向右移動，為 current 開闢一個空間 要插入的元素。
一旦我們找到合適的位置，current 元素被插入到新打開的插槽中。每次迭代都會重複這個過程，直到數組排序完畢。
現在，讓我們填充一個數組並調用我們的排序算法：
let inputArr = [5, 2, 4, 6, 1, 3];
insertionSort(inputArr);
console.log(inputArr);
該數組的輸出將是：
(6) [1, 2, 3, 4, 5, 6]
免費電子書：Git Essentials
查看我們的 Git 學習實踐指南，其中包含最佳實踐、行業認可的標準以及隨附的備忘單。停止谷歌搜索 Git 命令並真正學習 它！
讓我們一步一步地看這個例子：
第一次迭代：
- 未排序數組中的第一個元素是 2。
- 2 <5，因此我們將 5 向右移動一位。
- 2 放置在正確的位置。
第二次迭代：
- 未排序數組中的第一個元素是 4。
- 4 <5，因此我們將 5 向右移動一位。
- 4 !<2，所以我們不移動 2。
- 4 放置在正確的位置。
第三次迭代：
- 未排序數組中的第一個元素是 6。
- 6 !<5，所以我們不移動 5。
- 6 放置在正確的位置。
重複此過程，直到我們看到一個排序數組：1, 2, 3, 4, 5, 6 .
我們可以注意到每次迭代都有一個不變量。對於 k-th 我們循環的迭代，[0,k]的區間 保證排序。
時間比較
插入排序的最佳運行時間是線性的，如果我們的輸入數組已經排序，我們就會得到它。這意味著插入排序在檢查數組是否已排序時會產生奇蹟。
然而，最壞的平均時間複雜度是 O(n 2 )，這對於排序算法來說是非常糟糕的，尤其是當它應用於更大尺寸的數組或列表時。在這種情況下，複雜度為 O(nlogn) 的 Quicksort 或 Merge Sort 會是更好的選擇。
另一方面，作為最快的二次排序算法之一，插入排序通常優於冒泡排序、侏儒排序和選擇排序。除此之外，當我們的輸入數組非常小（10-20 個元素）時，插入排序甚至可以勝過快速排序和合併排序。
這就是為什麼 JavaScript 儘管使用 Quicksort（在 Chrome 中）或 Merge Sort（在 Mozilla 中）作為主要的排序算法，但也在小型集合上使用 Insertion Sort - 並且在 Quicksort/Merge Sort 完成了大部分工作之後。
結論
插入排序是一種簡單、穩定、就地的比較排序算法。
儘管二次復雜度相當耗時，但當輸入數組較小時，它非常有用。在這種情況下，它甚至優於最常用的分治算法，這就是為什麼 JavaScript 在使用內置排序函數時會使用插入排序和合併排序或快速排序的組合。
當涉及到更大的數組時，它優於大多數其他二次排序算法，包括冒泡排序、Gnome 排序以及選擇排序。
