像專業人士一樣掌握排序演算法-js教程-PHP中文網

正如我們一直在討論不同的排序演算法一樣，今天我們將學習選擇排序演算法。一種排序演算法，允許在記憶體受限的環境中實現盡可能少的交換。

介紹

選擇排序是一種簡單而有效的排序演算法，它的工作原理是重複從清單的未排序部分中選擇最小（或最大）元素，並將其移動到已排序部分的開頭（或結尾）。重複這個過程，直到整個清單都排序完畢。在本文中，我們將深入研究選擇排序演算法的細節、它在 JavaScript 中的實現，以及它在解決實際問題中的應用。

Mastering Sort Algorithm like a PRO

什麼是選擇排序演算法？

選擇排序演算法是一種就地比較排序演算法。它將輸入清單分為兩部分：

左端排序後的部分
右端未排序的部分

該演算法重複從未排序部分中選擇最小的元素，並將其與最左邊的未排序元素交換，從而將已排序部分和未排序部分之間的邊界向右移動一個元素。

選擇排序如何運作？

讓我們來看看使用陣列 [64, 25, 12, 22, 11] 的範例：

初始數組：[64,25,12,22,11]

排序部分：[]
未排序部分：[64,25,12,22,11]

第一遍：

在未排序部分找到最小值：11
將 11 與第一個未排序元素 (64) 交換
結果：[11,25,12,22,64]
排序部分：[11]
未排序部分：[25,12,22,64]

第二遍：

找出未排序部分的最小值：12
將 12 與第一個未排序元素 (25) 交換
結果：[11,12,25,22,64]
排序部分：[11, 12]
未排序部分：[25,22,64]

第三遍：

在未排序部分找到最小值：22
將 22 與第一個未排序元素 (25) 交換
結果：[11,12,22,25,64]
排序部分：[11,12,22]
未排序部分：[25, 64]

第四遍：

在未排序部分找到最小值：25
25 已經在正確的位置
結果：[11,12,22,25,64]
排序部分：[11,12,22,25]
未分類部分：[64]

最終通過：
- 只剩下一個元素，它會自動位於正確的位置
- 最終結果：[11,12,22,25,64]

陣列現已完全排序。

時間複雜度

選擇排序在所有情況下（最佳、平均和最差）的時間複雜度均為 O(n^2)，其中 n 是數組中元素的數量。這是因為：

外循環運作n-1次
對於外循環的每次迭代，內循環運行 n-i-1 次（其中 i 是外循環的當前迭代）

這會導致大約 (n^2)/2 次比較和 n 次交換，從而簡化為 O(n^2)。

由於這種二次時間複雜度，選擇排序對於大型資料集效率不高。然而，它的簡單性以及它使交換次數盡可能少的事實使其在某些情況下很有用，特別是當輔助記憶體有限時。

空間複雜度

選擇排序的空間複雜度為 O(1)，因為它對陣列進行就地排序。無論輸入大小如何，它只需要恆定量的額外記憶體空間。這使得它具有記憶體效率，這在記憶體受限的環境中非常有利。

JavaScript 中的實作

這是選擇排序演算法的 JavaScript 實作：

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Find the minimum element in the unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));

登入後複製

讓我們分解一下程式碼：

我們定義一個函數選擇排序，它以陣列作為輸入。
我們使用外部循環 (i) 迭代數組，它表示已排序部分和未排序部分之間的邊界。
對於每次迭代，我們假設第一個未排序元素是最小值並儲存其索引。
然後我們使用內循環 (j) 來找出未排序部分中實際的最小元素。
如果我們找到更小的元素，我們會更新 minIndex。
找到最小值後，如有必要，我們將其與第一個未排序元素交換。
我們重複這個過程，直到整個陣列排序完畢。

解決 LeetCode 問題

讓我們使用選擇排序演算法來解決一個 Leetcode 演算法問題。我們可以嗎？

問題：對數組進行排序 [中]

問題：給定一個整數數組 nums，按升序對數組進行排序並傳回它。您必須在不使用任何內建函數的情況下以 O(nlog(n)) 時間複雜度和盡可能最小的空間複雜度解決問題。

方法：：為了解決這個問題，我們可以直接應用選擇排序演算法。這涉及迭代數組，找到未排序部分中的最小元素，並將其與第一個未排序元素交換。我們重複這個過程，直到整個陣列排序完畢。

解：

function selectionSort(arr) {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;

    // Find the minimum element in the unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    // Swap the found minimum element with the first unsorted element
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }

  return arr;
}

// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));

登入後複製

這個解決方案直接應用了我們先前實作的選擇排序演算法。雖然它正確地解決了問題，但值得注意的是，由於選擇排序的 O(n^2) 時間複雜度，該解決方案可能會超出 LeetCode 上大量輸入的時間限制。下圖顯示該解決方案是正確的，但效率不高。

Mastering Sort Algorithm like a PRO

結論

總之，選擇排序是一種簡單直覺的排序演算法，可以很好地介紹排序技術的世界。它的簡單性使其易於理解和實施，使其成為初學者有價值的學習工具。然而，由於其二次時間複雜度 O(n^2)，它對於大型資料集效率不高。對於較大的資料集或效能關鍵的應用程序，首選更有效率的演算法，如 QuickSort、MergeSort 或內建排序函數。