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

目錄

1. 簡介
2. 什麼是選擇排序演算法？
3. 選擇排序如何運(yùn)作？
   • 時(shí)間複雜度
   • 空間複雜度
4. JavaScript 實(shí)作
5. 解決 LeetCode 問題
6. 結(jié)論

介紹

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

什麼是選擇排序演算法？

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

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

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

選擇排序如何運(yùn)作？

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

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è)元素，它會自動位於正確的位置
   • 最終結(jié)果：[11,12,22,25,64]

陣列現(xiàn)已完全排序。

時(shí)間複雜度

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

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

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

由於這種二次時(shí)間複雜度，選擇排序?qū)洞笮唾Y料集效率不高。然而，它的簡單性以及它使交換次數(shù)盡可能少的事實(shí)使其在某些情況下很有用，特別是當(dāng)輔助記憶體有限時(shí)。

空間複雜度

選擇排序的空間複雜度為 O(1)，因?yàn)樗鼘﹃嚵羞M(jìn)行就地排序。無論輸入大小如何，它只需要恆定量的額外記憶體空間。這使得它具有記憶體效率，這在記憶體受限的環(huán)境中非常有利。

JavaScript 中的實(shí)作

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

讓我們分解一下程式碼：

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

解決 LeetCode 問題

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

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

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

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

解：

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í)作的選擇排序演算法。雖然它正確地解決了問題，但值得注意的是，由於選擇排序的 O(n^2) 時(shí)間複雜度，該解決方案可能會超出 LeetCode 上大量輸入的時(shí)間限制。下圖顯示該解決方案是正確的，但效率不高。

結(jié)論

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

---

---

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

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

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

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

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