JavaScript 中的計算機科學：插入排序
插入排序通常是計算機科學課程中教授的第三種排序算法，僅次於冒泡排序 1 和選擇排序 2 .插入排序的最佳情況復雜度為 O(n)，比冒泡排序和選擇排序複雜度為 O(n 2 ）。這也是第一個教授的穩定排序算法。
穩定排序算法是不改變列表中等價項順序的排序。在冒泡排序和選擇排序中，等效項可能以與原始列表中不同的順序結束。您可能想知道如果項目是等效的，為什麼這很重要。在對簡單值（如數字或字符串）進行排序時，它沒有任何意義。如果您按特定屬性對對象進行排序，例如排序 person age 上的對象 屬性，可能還有其他應按特定順序排列的關聯數據。
執行交換的排序算法本質上是不穩定的。物品總是在四處移動，因此您不能保證會保留之前的任何訂單。插入排序不執行交換。相反，它會挑選出單個項目並將它們插入到數組中的正確位置。
插入排序通過將數組分成兩個部分來工作，一個已排序的部分和一個未排序的部分。當然，最初，整個數組是未排序的。排序的部分然後被認為是空的。第一步是向排序部分添加一個值，因此使用數組中的第一項（一個項目的列表總是排序的）。然後在未排序部分中的每個項目：
- 如果項值在排序部分中的最後一項之後，則什麼也不做。
- 如果項目值在排序部分中的最後一項之前，則從數組中刪除項目值並將最後一個排序項移到現在的空位。
- 將項目值與排序部分中的前一個值（倒數第二個）進行比較。
- 如果項目值在前一個值之後和最後一個值之前，則將項目放在它們之間的空位中，否則，繼續此過程直到到達數組的開頭。
插入排序有點難以用語言來解釋。用一個例子來解釋會更容易一些。假設你有以下數組：
var items = [5, 2, 6, 1, 3, 9];
首先，將 5 放入已排序的部分。然後 2 成為要放置的值。由於 5 大於 2，因此 5 移動到右側一個位置，覆蓋 2。這會在已排序部分的開頭釋放一個新位置，可以將 2 放入其中。此過程的可視化請參見下圖（黃色框是已排序部分的一部分，白色框未排序）。
然後該過程以 6 繼續。未排序部分中的每個後續值都經過相同的過程，直到整個數組的順序正確。這個過程在 JavaScript 中可以相當簡潔地表示如下：
function insertionSort(items) {
var len = items.length, // number of items in the array
value, // the value currently being compared
i, // index into unsorted section
j; // index into sorted section
for (i=0; i < len; i++) {
// store the current value because it may shift later
value = items[i];
/*
* Whenever the value in the sorted section is greater than the value
* in the unsorted section, shift all items in the sorted section over
* by one. This creates space in which to insert the value.
*/
for (j=i-1; j > -1 && items[j] > value; j--) {
items[j+1] = items[j];
}
items[j+1] = value;
}
return items;
}
外層for 循環從數組的前面向後面移動，而內部循環從排序部分的後面向前面移動。內部循環還負責在比較發生時移動項目。您可以從我的 GitHub 項目“JavaScript 中的計算機科學”下載源代碼。
平均複雜度為 O(n
2
的插入排序效率並不高 ）。這使其在性能方面與選擇排序和冒泡排序相提並論。這三種排序算法通常會開始討論排序算法，即使您在現實生活中永遠不會使用它們。如果您需要在 JavaScript 中對項目進行排序，最好從內置的 Array.prototype.sort() 開始 嘗試其他算法之前的方法。 V8 是 Chrome 中的 JavaScript 引擎，實際上使用插入排序來使用 Array.prototype.sort() 對包含 10 個或更少項目的項目進行排序 .
參考
- JavaScript 中的計算機科學：冒泡排序
- JavaScript 中的計算機科學：選擇排序
