C++冒泡排序

圖 11-4   利用元素交換操作模擬冒泡

圖 11-4   利用元素交換操作模擬冒泡

「冒泡排序 bubble sort」通過連續(xù)地比較與交換相鄰元素實(shí)現(xiàn)排序。這個過程就像氣泡從底部升到頂部一樣，因此得名冒泡排序。

如圖 11-4 所示，冒泡過程可以利用元素交換操作來模擬：從數(shù)組最左端開始向右遍歷，依次比較相鄰元素大小，如果“左元素 > 右元素”就交換它倆。遍歷完成后，最大的元素會被移動到數(shù)組的最右端。

圖 11-4   利用元素交換操作模擬冒泡

算法流程

設(shè)數(shù)組的長度為 n ，冒泡排序的步驟如圖 11-5 所示。

1. 首先，對 n 個元素執(zhí)行“冒泡”，將數(shù)組的最大元素交換至正確位置，
2. 接下來，對剩余 n?1 個元素執(zhí)行“冒泡”，將第二大元素交換至正確位置。
3. 以此類推，經(jīng)過 n?1 輪“冒泡”后，前 n?1 大的元素都被交換至正確位置。
4. 僅剩的一個元素必定是最小元素，無須排序，因此數(shù)組排序完成。

圖 11-5   冒泡排序流程

bubble_sort.cpp

/* 冒泡排序 */
void bubbleSort(vector<int> &nums) {
    // 外循環(huán)：未排序區(qū)間為 [0, i]
    for (int i = nums.size() - 1; i > 0; i--) {
        // 內(nèi)循環(huán)：將未排序區(qū)間 [0, i] 中的最大元素交換至該區(qū)間的最右端
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交換 nums[j] 與 nums[j + 1]
                // 這里使用了 std::swap() 函數(shù)
                swap(nums[j], nums[j + 1]);
            }
        }
    }
}

效率優(yōu)化

我們發(fā)現(xiàn)，如果某輪“冒泡”中沒有執(zhí)行任何交換操作，說明數(shù)組已經(jīng)完成排序，可直接返回結(jié)果。因此，可以增加一個標(biāo)志位 flag 來監(jiān)測這種情況，一旦出現(xiàn)就立即返回。

經(jīng)過優(yōu)化，冒泡排序的最差和平均時間復(fù)雜度仍為 O(n2) ；但當(dāng)輸入數(shù)組完全有序時，可達(dá)到最佳時間復(fù)雜度 O(n) 。

bubble_sort.cpp

/* 冒泡排序（標(biāo)志優(yōu)化）*/
void bubbleSortWithFlag(vector<int> &nums) {
    // 外循環(huán)：未排序區(qū)間為 [0, i]
    for (int i = nums.size() - 1; i > 0; i--) {
        bool flag = false; // 初始化標(biāo)志位
        // 內(nèi)循環(huán)：將未排序區(qū)間 [0, i] 中的最大元素交換至該區(qū)間的最右端
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // 交換 nums[j] 與 nums[j + 1]
                // 這里使用了 std::swap() 函數(shù)
                swap(nums[j], nums[j + 1]);
                flag = true; // 記錄交換元素
            }
        }
        if (!flag)
            break; // 此輪冒泡未交換任何元素，直接跳出
    }
}

算法特性

• 時間復(fù)雜度為 O(n2)、自適應(yīng)排序：各輪“冒泡”遍歷的數(shù)組長度依次為 n?1、n?2、…、2、1 ，總和為 (n?1)n/2 。在引入 flag 優(yōu)化后，最佳時間復(fù)雜度可達(dá)到 O(n) 。
• 空間復(fù)雜度為 O(1)、原地排序：指針 i 和 j 使用常數(shù)大小的額外空間。
• 穩(wěn)定排序：由于在“冒泡”中遇到相等元素不交換。