7.1 冒泡排序基础

“小朋友们，”我微笑着说，”想象一下，你有一堆大小不同的气泡在水中，小气泡会慢慢上升，大气泡也会上升到顶部。冒泡排序就是这样工作的！我们通过不断比较相邻的两个数，让大的数慢慢’冒’到后面。”

7.1.1 数组元素的排序

题目描述： 对数组的元素按从小到大进行排序。

输入格式： 第一行有一个整数 n ( 5≤n≤100 )；第二行有 n 个整数，每个整数的值在 [0,10^9] 的范围内。

输出格式： 输出排序后的数组。

样例输入：

8
1 2 3 6 8 7 4 5

样例输出：

1 2 3 4 5 6 7 8

代码实现：

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

int main(){
    int a[110], n;  // 定义数组和长度变量
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        cin >> a[i];  // 输入数组元素
    }
    
    // 冒泡排序算法
    for(int i = 1; i < n; i++){  // 外层循环控制排序轮数
        for(int j = 1; j <= n-i; j++){  // 内层循环进行比较交换
            if(a[j] > a[j+1]){  // 如果前面的数大于后面的数
                swap(a[j], a[j+1]);  // 交换两个数的位置
            }
        }
    }
    
    for(int i = 1; i <= n; i++) 
        cout << a[i] << " ";  // 输出排序后的数组
    return 0;
}

算法解析：

1. 外层循环控制排序的轮数，需要进行n-1轮
2. 内层循环在每轮中比较相邻的元素
3. 如果前面的元素大于后面的元素，就交换它们的位置
4. 每轮结束后，最大的元素会”冒泡”到正确的位置