使用 Javascript 進行演算法之旅 - 插入排序

什麼是插入排序？

插入排序是電腦科學中的另一個基本排序演算法。它一次建立一個最終的排序數組。這很像對一手撲克牌進行排序 - 您一張一張地拿起紙牌，並將每張紙牌插入您已排序的紙牌中的正確位置。

插入排序如何運作

插入排序迭代數組，每次迭代都會增加已排序的部分。對於每個元素，它將與已排序的元素進行比較，向上移動它們，直到找到插入當前元素的正確位置。

以下是逐步說明：

1. 從第二個元素（索引 1）開始作為「目前」元素。
2. 將目前元素與先前的元素進行比較。
3. 如果當前元素較小，則與先前的元素進行比較。將較大的元素向上移動，為交換的元素騰出空間。
4. 重複步驟2-3，直到整個陣列排序完畢。

插入排序的視覺化：

錄製的 gif 來自 https://visualgo.net/en/sorting

在 JavaScript 中實作插入排序

讓我們來看看JavaScript中插入排序的實現，每個部分都有詳細的註釋解釋：

function insertionSort(arr) {
  // Start from the second element (index 1)
  // We assume the first element is already sorted
  for (let i = 1; i < arr.length; i++) {
    // Store the current element we're trying to insert into the sorted portion
    let currentElement = arr[i];
    // Define the starting index of lookup (this is the last index of sorted portion of array)
    let j = j - 1;
    // Move elements of arr[0..i-1] that are greater than currentElement
    // to one position ahead of their current position
    while (j >= 0 && arr[j] > currentElement) {
      // Shift element to the right
      arr[j + 1] = arr[j];
      j--;
    }
    // We've found the correct position for currentElement (at j + 1), insert it:
    arr[j + 1] = currentElement;
  }

  // The array is now sorted in-place:
  return arr;
}

要點：

1. 雙向過程：插入排序透過向前移動的外循環和向後查看的內循環進行操作，從而創建構成演算法核心的來回運動。
2. 前向掃描（外環）：

   for (let i = 1; i < arr.length; i++)

在陣列中向前移動，一次選擇一個未排序的元素 (currentElement = arr[i])。

1. 向後插入（內循環）：

   while (j >= 0 && arr[j] > currentElement)

向後查看已排序的部分，向右移動較大的元素 (arr[j 1] = arr[j]) 以為當前元素騰出空間。

1. 元素插入：

   arr[j + 1] = currentElement;

將目前元素插入到正確的位置，增加排序部分。

1. 就地穩定排序：直接修改原數組，保持相等元素的相對順序。

插入排序每次建立一個最終排序數組，模仿您對一手牌進行排序的方式。它重複地從未排序的部分中選擇一張卡片（元素）並將其插入到已排序的卡片中的正確位置，並根據需要移動較大的卡片。這種直觀的過程使得插入排序對於小型或接近排序的資料集非常有效率。

插入排序穩定嗎？

是的，插入排序是一種穩定的排序演算法。排序演算法的穩定性意味著相等元素的相對順序在排序後得以保留。插入排序因其操作方法而自然地實現了這一點：

1. 保留順序：將元素插入已排序部分時，插入排序僅移動嚴格大於當前元素的元素。這意味著如果有多個元素具有相同的值，它們的相對順序將被保持。
2. 沒有不必要的交換：與可能交換相等元素的其他排序演算法不同，插入排序僅在必要時移動元素。這個特性確保相等的元素保持在原來的相對位置。
3. 從左到右處理：透過從左到右處理數組，並將每個元素插入到已排序元素中的正確位置，插入排序自然會保持相等元素的原始順序。

在對複雜資料結構進行排序時，插入排序的穩定性特別有用，因為保持相等元素的原始順序非常重要。例如，當先按年級然後按姓名對學生列表進行排序時，穩定的排序將確保具有相同年級的學生仍按姓名的字母順序排列。

這種穩定性是基本插入排序演算法的固有屬性，不需要任何額外的修改或開銷即可實現，使其成為一種天然穩定的排序方法。

時間與空間複雜度分析

插入排序的效能特性如下：

• 時間複雜度：

  • 最佳情況：O(n) - 當陣列已排序時
  • 平均情況：O(n^2)
  • 最壞情況：O(n^2) - 當陣列反向排序時

• 空間複雜度：O(1) - 插入排序是一種就地排序演算法

與選擇排序不同，插入排序可以在近排序數組上表現良好，在這種情況下實現接近線性的時間複雜度。

插入排序的優點和缺點

優點：

• 易於實施與理解
• 對於中小型資料集非常有效
• 自適應 - 在近排序數組上表現良好
• 穩定 - 保持相等元素的相對順序
• 就地排序（O(1) 空間）
• 適合線上排序場景

缺點：

• 大型資料集效率低（平均和最壞情況下為 O(n^2)）
• 隨著輸入大小的增加，效能會迅速下降

何時使用插入排序

• 中小型資料集（通常最多幾百個元素）
• 接近排序的資料
• 線上排序場景，元素被增量接收並排序
• 作為更複雜演算法中的子程序（例如，小分區的快速排序）

實際應用和用例

1. 標準函式庫實作：通常用於小型陣列或作為混合排序演算法的一部分
2. 資料庫操作：對小組記錄進行排序
3. 嵌入式系統：由於其簡單性和低記憶體開銷，適合資源有限的系統
4. 即時資料處理：在接收資料時保持排序順序

結論

插入排序儘管對於大型資料集有局限性，但在特定場景中提供了寶貴的優勢。它的直觀性，類似於我們手動對卡片進行排序的方式，使其成為理解排序演算法的優秀教育工具。

重點：

• 幾乎排序資料的最佳情況時間複雜度為 O(n)
• 穩定、就地、自適應的排序演算法
• 對於小型資料集和線上排序非常有效
• 常納入混合排序策略

雖然不適合大規模排序任務，但插入排序的原理通常應用於更複雜的方法。它在某些場景下的簡單性和高效性使其成為程式設計師演算法工具包的寶貴補充。

排序演算法的選擇最終取決於您的特定用例、資料特徵和系統約束。了解插入排序可以深入了解演算法設計權衡，並為探索更高級的排序技術奠定基礎。

以上是使用 Javascript 進行演算法之旅 - 插入排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！