正如我們一直在討論不同的排序算法一樣，今天我們將學習選擇排序算法。一種排序算法，允許在內(nèi)存受限的環(huán)境中實現(xiàn)盡可能少的交換。

目錄

1. 簡介
2. 什么是選擇排序算法？
3. 選擇排序如何工作？
   • 時間復雜度
   • 空間復雜度
4. JavaScript 實現(xiàn)
5. 解決 LeetCode 問題
6. 結(jié)論

介紹

選擇排序是一種簡單而有效的排序算法，它的工作原理是重復從列表的未排序部分中選擇最?。ɑ蜃畲螅┰兀⑵湟苿拥揭雅判虿糠值拈_頭（或結(jié)尾）。重復這個過程，直到整個列表排序完畢。在本文中，我們將深入研究選擇排序算法的細節(jié)、它在 JavaScript 中的實現(xiàn)，以及它在解決實際問題中的應(yīng)用。

什么是選擇排序算法？

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

1. 左端排序后的部分
2. 右端未排序的部分

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

選擇排序如何工作？

讓我們看一下使用數(shù)組 [64, 25, 12, 22, 11] 的示例：

1. 初始數(shù)組：[64,25,12,22,11]

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

1. 第一遍：

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

1. 第二遍：

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

1. 第三遍：

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

1. 第四遍：

• 在未排序部分中找到最小值：25
• 25 已經(jīng)在正確的位置
• 結(jié)果：[11,12,22,25,64]
• 排序部分：[11,12,22,25]
• 未分類部分：[64]

1. 最終通過：
   • 只剩下一個元素，它會自動位于正確的位置
   • 最終結(jié)果：[11,12,22,25,64]

數(shù)組現(xiàn)已完全排序。

時間復雜度

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

• 外循環(huán)運行n-1次
• 對于外循環(huán)的每次迭代，內(nèi)循環(huán)運行 n-i-1 次（其中 i 是外循環(huán)的當前迭代）

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

由于這種二次時間復雜度，選擇排序?qū)τ诖笮蛿?shù)據(jù)集效率不高。然而，它的簡單性以及它使交換次數(shù)盡可能少的事實使其在某些情況下很有用，特別是當輔助內(nèi)存有限時。

空間復雜度

選擇排序的空間復雜度為 O(1)，因為它對數(shù)組進行就地排序。無論輸入大小如何，它只需要恒定量的額外內(nèi)存空間。這使得它具有內(nèi)存效率，這在內(nèi)存受限的環(huán)境中非常有利。

JavaScript 中的實現(xiàn)

這是選擇排序算法的 JavaScript 實現(xià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));

讓我們分解一下代碼：

1. 我們定義一個函數(shù)選擇排序，它以數(shù)組作為輸入。
2. 我們使用外循環(huán) (i) 迭代數(shù)組，它表示已排序部分和未排序部分之間的邊界。
3. 對于每次迭代，我們假設(shè)第一個未排序元素是最小值并存儲其索引。
4. 然后我們使用內(nèi)循環(huán) (j) 來查找未排序部分中實際的最小元素。
5. 如果我們找到更小的元素，我們會更新 minIndex。
6. 找到最小值后，如有必要，我們將其與第一個未排序元素交換。
7. 我們重復這個過程，直到整個數(shù)組排序完畢。

解決 LeetCode 問題

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

問題：對數(shù)組進行排序 [中]

問題：給定一個整數(shù)數(shù)組 nums，按升序?qū)?shù)組進行排序并返回它。您必須在不使用任何內(nèi)置函數(shù)的情況下以 O(nlog(n)) 時間復雜度和盡可能最小的空間復雜度解決問題。

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

解決方案：

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));

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

結(jié)論

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

---

---

保持更新和聯(lián)系

確保您不會錯過本系列的任何部分，并與我聯(lián)系以進行更深入的了解
關(guān)于軟件開發(fā)（Web、服務(wù)器、移動或抓取/自動化）、數(shù)據(jù)的討論
結(jié)構(gòu)和算法，以及其他令人興奮的技術(shù)主題，請關(guān)注我：

• GitHub
• 領(lǐng)英
• X（推特）

敬請期待并祝您編碼愉快?????

以上是像專業(yè)人士一樣掌握排序算法的詳細內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！