C2. 08 数组排序的专项练习(一)

课堂内容：冒泡排序与选择排序的应用

• 冒泡排序_基本原理

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

• 冒泡排序_参考代码

#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
    // 定义一个大小为 105 的整数数组a 和一个整数 n  
    int a[105],n;  
  
    // 输入一个整数 n  
    cin>>n;  
  
    // 循环读取 n 个整数，并存储到数组a 中  
    for(int i=0;i<=n-1;i++) cin>>a[i];
  
    // 冒泡排序算法   
    for(int i=1;i<=n-1;i++)// 外层循环控制排序的轮数  
    {  
        // 内层循环控制每一轮的比较和交换  
        for(int j=0;j<=n-2;j++)  
        {  
            // 如果当前元素a[j]大于下一个元素a[j+1]，则交换它们的位置  
            if(a[j] > a[j+1])  
            {  
                swap(a[j],a[j+1]);  
            }  
        }  
    }  
  
    // 输出排序后的数组  
    for(int i=0;i<=n-1;i++) cout<<a[i]<<" ";  

    return 0;  
}

• 冒泡排序_代码解析

• 从数列的第一个元素开始，比较相邻的两个元素。如果前一个元素比后一个元素大（如果是降序排序，则是前一个元素比后一个元素小），则交换它们的位置。
• 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数（如果是降序排序，则是最小的数）。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较