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

目錄

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

介紹

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

什么是選擇排序算法？

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

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

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

選擇排序如何工作？

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

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

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

1. 第一遍：

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

1. 第二遍：

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

1. 第三遍：

• 在未排序部分中找到最小值：22
• 將 22 與第一個(gè)未排序元素 (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. 最終通過：
   • 只剩下一個(gè)元素，它會(huì)自動(dòng)位于正確的位置
   • 最終結(jié)果：[11,12,22,25,64]

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

時(shí)間復(fù)雜度

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

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

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

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

空間復(fù)雜度

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

JavaScript 中的實(shí)現(xiàn)

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

解決 LeetCode 問題

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

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

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

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

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

結(jié)論

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

---

---

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

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

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

敬請(qǐng)期待并祝您編碼愉快?????

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