从头实现冒泡排序

思路: 两两比较相邻元素，如果反序则交换，直到没有反序为止。

框架：

#include <algorithm>
#include <iostream>
#include <vector>

void BubbleSort(std::vector<int>& A) {

}

int main() {
    std::vector<int> A{9, 1, 5, 8, 3, 7, 4, 6, 2};
    std::ranges::for_each(A, [](int value) { std::cout << value << ' '; });
    return 0;
}

循环 n - 1 次。n 是待排序数组内元素的个数。每一轮循环都至少将一个元素移动到正确位置，在进行 n - 1 轮排序后，排序必然完成（可能提前完成）。

void BubbleSort(std::vector<int> &A) {
    for (int i = 0; i < A.size() - 1; ++i) {
            
    }
}

内层循环从数组的末尾开始，向前遍历未排序的部分，到已排序的部分停止。数组的开头是已排序的部分。每一次内层循环结束，数组的开头就会多一个已排序的元素。已经排序好的元素不再参与比较。

void BubbleSort(std::vector<int> &A) {
    for (int i = 0; i < A.size() - 1; ++i) {
        for (int j = A.size() - 1; j > i; --j) {

        }
    }
}

在每次内层循环中，比较相邻元素的大小，如果当前元素比前一个元素小，就交换它们。这样，较小的元素会逐渐“冒泡”到左边，较大的元素则被交换到右边。
（交换相邻元素的值时使用已定义的函数void Swap(int&, int&);）

void BubbleSort(std::vector<int> &A) {
    for (int i = 0; i < A.size() - 1; ++i) {
        for (int j = A.size() - 1; j > i; --j) {
            if (A[j] < A[j - 1]) {
                Swap(A[j], A[j - 1]);
            }
        }
    }
}

完整代码：

#include <algorithm>
#include <iostream>
#include <vector>

void Swap(int &i, int &j) {
    int temp = i;
    i = j;
    j = temp;
}

void BubbleSort(std::vector<int> &A) {
    for (int i = 0; i < A.size() - 1; ++i) {
        for (int j = A.size() - 1; j > i; --j) {
            if (A[j] < A[j - 1]) {
                Swap(A[j], A[j - 1]);
            }
        }
    }
}

int main() {
    std::vector<int> A{9, 1, 5, 8, 3, 7, 4, 6, 2};
    BubbleSort(A);
    std::ranges::for_each(A, [](int value) { std::cout << value << ' '; });
    return 0;
}