JavaScript 中的計算機科學：選擇排序

不久前，我寫了一篇關於冒泡排序算法的文章，它通常是排序算法指令的起點。冒泡排序是一個非常低效的算法，O(n ² ) 複雜性及其算法要求將每個數組項與其鄰居進行比較，以便將最小值“冒泡”到數組的頂部（前面）。

選擇排序算法，也是 O(n ² ) 複雜性，略微增加了該算法。目標不是將每個數組項與其鄰居進行比較，而是找到最小的剩餘值並將其放入數組中的正確位置。基本算法是這樣的：

1. 假設第一項是最小值。
2. 將此項與第二項進行比較。
3. 如果第二項小於第一項，則將第二項設置為新的最小值。
4. 繼續直到到達數據集的末尾。
5. 如果最小值不是您開始使用的項目，請交換它們。

通過移動到第二個項目，然後是第三個項目，以此類推，重複此過程，直到整個數組已排序。為了更好地說明算法，考慮一個數組 ["b", "a", "d", "c", "e"] .

如果這個數組要按升序排序，第一步是將最小值設置為索引 0。接下來，比較“b”和“a”。由於“a”在“b”之前，因此最小值設置為索引 1。然後將字母“a”與數組中的每個項目進行比較，但由於它是最小值，因此最小索引保持為 1。一旦這個已通過，最小索引 1 與起始索引 0 進行比較，由於它們不同，這兩個位置的值被交換，結果為 ["a", "b", "d", "c", "e"] .

接下來，算法從第二個位置“b”開始，並將最小索引設置為 1。將該值與其他值進行比較，並且沒有進行任何更改，因為“b”已經在正確的位置。由於起始索引和最小索引均為 1，因此不進行交換。第三遍從“d”開始並與“c”進行比較，將最小值更改為 3。在該遍結束時，交換 2 和 3，得到 ["a", "b", "c", "d", "e"] .最後兩遍沒有交換，因為一切都在正確的位置。為了更清楚起見，請觀看此視頻，了解使用撲克牌的示例。

選擇排序使用相同的 swap() 冒泡排序：

function swap(items, firstIndex, secondIndex){
    var temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

選擇排序的實現非常簡單。類似於冒泡排序，它使用兩個循環來完成任務（最終導致 O(n ² ) 複雜性）：

function selectionSort(items){

    var len = items.length,
        min;

    for (i=0; i < len; i++){

        //set minimum to this position
        min = i;

        //check the rest of the array to see if anything is smaller
        for (j=i+1; j < len; j++){
            if (items[j] < items[min]){
                min = j;
            }
        }

        //if the minimum isn't in the position, swap it
        if (i != min){
            swap(items, i, min);
        }
    }

    return items;
}

外部循環控制每次遍歷的起點，從數組中的第一項開始，一直到最後一項。內部循環控制正在比較哪些項目。每次通過後，數組開頭的項目已經在正確的位置，因此無需重新評估它們。

您可以從我的 GitHub 項目“JavaScript 中的計算機科學”下載源代碼。

與冒泡排序一樣，選擇排序不太可能在現實環境中使用。這篇文章只是出於教學目的對算法的討論。很少有內置的 Array.prototype.sort() 方法不合適，所以總是先用那個。