冒泡排序(Bubble Sort)，是一種簡單的交換排序算法。

原理：

1. 相鄰元素比較后，小的浮起來，大的沉下去。
2. 每次外循環(huán)都至少有一個元素完成排序。
3. 持續(xù)重復比較，未排序元素越來越少，直到?jīng)]有元素需要比較。

舉例：

輸入：nums = {2, 4, 7, 3, 1}

• 冒泡第一版：

void bubbleSort(vector<int>& nums){
    for(int i = 0; i < nums.size() - 1; ++i){
        for(int j = 0 ; j < nums.size() - 1 - i; ++j){// 每次外循環(huán)至少有一個元素完成排序
            if(nums[j] > nums[j + 1])
                swap(nums[j], nums[j + 1]);
        }
    }
}

這里我們可以思考一下，這個算法是否可以優(yōu)化呢？

答案是肯定的，上面的例子可能體現(xiàn)不出來，如果我們的輸入數(shù)組的數(shù)據(jù)情況是：nums = {1, 2, 3, 4, 7, 5, 6, 8}，這里其實只要外循環(huán)一次就能解決問題。如何優(yōu)化這個冗余重復比較的過程呢？引入一個變量來記錄是否發(fā)生交換，如果沒發(fā)生則可以退出循環(huán)了。

• 冒泡第二版：

void bubbleSort(vector<int>& nums){
    for(int i = 0; i < nums.size() - 1; ++i){
        // 記錄是否沒發(fā)生交換
        bool flag = true;
        for(int j = 0; j < nums.size() - 1 - i; ++j){
            if(nums[j] > nums[j + 1]){
                flag = false;
                swap(nums[j], nums[j + 1]);
            }
        }
        // 如果沒發(fā)生交換，則退出
        if(flag == true)
            return;
    }
}

在第二版后，我們再來思考一下，是否能繼續(xù)優(yōu)化呢？

如果想不出？我們可以舉個例子：nums = {2, 1, 4, 3, 5, 6, 7, 8, 9}，在這個例子中你會發(fā)現(xiàn)數(shù)組后半部分是有序，所以前面兩種算法前5次有冗余比較。

• 冒泡第三版：

void bubbleSort(vector<int>& nums){
    // 邊界，右邊有序
    int border = nums.size() - 1;
    for(int i = 0; i < nums.size() - 1; ++i){
        bool flag = true;
        // 記錄發(fā)生最后一次交換的下標
        int last = 0;
        for(int j = 0; j < border; ++j){
            if(nums[j] > nums[j + 1]){
                last = j;
                flag = false;
                swap(nums[j], nums[j + 1]);
            }
        }
        border = last;
        if(flag == true)
            return;
    }
}

最后

思考在兩次優(yōu)化后，冒泡算法是否還能優(yōu)化呢？