正如我們一直在討論不同的排序演算法一樣，今天我們將學習選擇排序演算法。一種排序演算法，允許在記憶體受限的環境中實現盡可能少的交換。
選擇排序是一種簡單而有效的排序演算法，它的工作原理是重複從清單的未排序部分中選擇最小（或最大）元素，並將其移動到已排序部分的開頭（或結尾） 。重複這個過程，直到整個清單都排序完畢。在本文中，我們將深入研究選擇排序演算法的細節、它在 JavaScript 中的實現，以及它在解決實際問題中的應用。
選擇排序演算法是一種就地比較排序演算法。它將輸入清單分為兩部分：
該演算法重複從未排序部分中選擇最小的元素，並將其與最左邊的未排序元素交換，從而將已排序部分和未排序部分之間的邊界向右移動一個元素。
讓我們來看看使用陣列 [64, 25, 12, 22, 11] 的範例：
陣列現已完全排序。
選擇排序在所有情況下（最佳、平均和最差）的時間複雜度均為 O(n^2)，其中 n 是數組中元素的數量。這是因為：
這會導致大約 (n^2)/2 次比較和 n 次交換，從而簡化為 O(n^2)。
由於這種二次時間複雜度，選擇排序對於大型資料集效率不高。然而，它的簡單性以及它使交換次數盡可能少的事實使其在某些情況下很有用，特別是當輔助記憶體有限時。
選擇排序的空間複雜度為 O(1)，因為它對陣列進行就地排序。無論輸入大小如何，它只需要恆定量的額外記憶體空間。這使得它具有記憶體效率，這在記憶體受限的環境中非常有利。
這是選擇排序演算法的 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));
讓我們分解一下程式碼：
讓我們使用選擇排序演算法來解決一個 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 上大量輸入的時間限制。下圖顯示該解決方案是正確的，但效率不高。
總之，選擇排序是一種簡單直覺的排序演算法，可以很好地介紹排序技術的世界。它的簡單性使其易於理解和實施，使其成為初學者有價值的學習工具。然而，由於其二次時間複雜度 O(n^2)，它對於大型資料集效率不高。對於較大的資料集或效能關鍵的應用程序，首選更有效率的演算法，如 QuickSort、MergeSort 或內建排序函數。
確保您不會錯過本系列的任何部分，並與我聯繫以進行更深入的了解
關於軟體開發（Web、伺服器、行動或抓取/自動化）、資料的討論
結構和演算法，以及其他令人興奮的技術主題，請關注我：
敬請期待並祝您編碼愉快????
以上是像專業人士一樣掌握排序演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！
