解法一、模擬

🔹 氣泡排序

遍歷 nums[]
如果 nums[i] > nums[i+1] 表示順序反了
所以 swap(nums[i], nums[i+1]) 以確保小的數字在左邊

遍歷一次就可以確定 nums[nums.size()-1] 是最大的數字
遍歷 n 次就可以確定 nums[] 的最後 n 個數是最大的數字

這樣的遍歷總共需要進行 nums.size()-1 次
(確定了 nums[] 的最後 nums.size()-1 個數後，就不需要檢查 nums[0] 了)

題目求 nums[] 使用 氣泡排序法 排序總共需要交換幾次
以 範例測資 舉例，總共交換 6 次

0. 4 3 2 1
1. 3 4 2 1
2. 3 2 4 1
3. 3 2 1 4
4. 2 3 1 4
5. 2 1 3 4
6. 1 2 3 4

✅ 完整代碼

評分結果(參考) ： AC (3ms, 348KB)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, cnt = 0;
    cin >> n;

    vector<int> nums(n);
    for(int& num : nums) cin >> num;

    for(int i=0; i<n-1; i++){
        for(int j=0; j<n-1; j++){
            if(nums[j] > nums[j+1]){
                swap(nums[j], nums[j+1]);
                cnt++;
            }
        }
    }
    cout << cnt;
    
    return 0;
}

解法二、解法一優化版

因為遍歷 n 次就可以確定 nums[] 的最後 n 個數
所以每次的遍歷可以不檢查 nums[] 的最後 n 個數

將迴圈 for(int j=0; j<n-1; j++){} 的終止條件改為 j<n-i-1

✅ 完整代碼

評分結果(參考) ： AC (3ms, 336KB)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, cnt = 0;
    cin >> n;

    vector<int> nums(n);
    for(int& num : nums) cin >> num;

    for(int i=0; i<n-1; i++){
        for(int j=0; j<n-i-1; j++){
            if(nums[j] > nums[j+1]){
                swap(nums[j], nums[j+1]);
                cnt++;
            }
        }
    }
    cout << cnt;
    
    return 0;
}