C++選擇排序

「選擇排序 selection sort」的工作原理非常直接：開啟一個循環(huán)，每輪從未排序區(qū)間選擇最小的元素，將其放到已排序區(qū)間的末尾。

設數(shù)組的長度為 n ，選擇排序的算法流程如圖 11-2 所示。

1. 初始狀態(tài)下，所有元素未排序，即未排序（索引）區(qū)間為 [0,n?1] 。
2. 選取區(qū)間 [0,n?1] 中的最小元素，將其與索引 0 處元素交換。完成后，數(shù)組前 1 個元素已排序。
3. 選取區(qū)間 [1,n?1] 中的最小元素，將其與索引 1 處元素交換。完成后，數(shù)組前 2 個元素已排序。
4. 以此類推。經(jīng)過 n?1 輪選擇與交換后，數(shù)組前 n?1 個元素已排序。
5. 僅剩的一個元素必定是最大元素，無須排序，因此數(shù)組排序完成。

圖 11-2   選擇排序步驟

在代碼中，我們用 $k$ 來記錄未排序區(qū)間內(nèi)的最小元素。

selection_sort.cpp

/* 選擇排序 */
void selectionSort(vector<int> &nums) {
    int n = nums.size();
    // 外循環(huán)：未排序區(qū)間為 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 內(nèi)循環(huán)：找到未排序區(qū)間內(nèi)的最小元素
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 記錄最小元素的索引
        }
        // 將該最小元素與未排序區(qū)間的首個元素交換
        swap(nums[i], nums[k]);
    }
}

算法特性

• 時間復雜度為 O(n2)、非自適應排序：外循環(huán)共 n?1 輪，第一輪的未排序區(qū)間長度為 n ，最后一輪的未排序區(qū)間長度為 2 ，即各輪外循環(huán)分別包含 n、n?1、…、3、2 輪內(nèi)循環(huán)，求和為 (n?1)(n+2)2 。
• 空間復雜度 O(1)、原地排序：指針 i 和 j 使用常數(shù)大小的額外空間。
• 非穩(wěn)定排序：如圖 11-3 所示，元素 nums[i] 有可能被交換至與其相等的元素的右邊，導致兩者相對順序發(fā)生改變。

圖 11-3   選擇排序非穩(wěn)定示例