冒泡排序算法

1.首先先介绍一下冒泡算法。

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端或者是”坠”到谷底（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

2.冒泡排序原理。

首先，我们要定义一个数组，例如a[100]啥的，如果我们需要把数组元素从小到大进行排列（冒泡排序啦），那就要比较相邻的两个元素，如果前一个元素比后一个元素大就交换它们，交换后，最后一个元素就会变成最大的，接着就一直重复这个步骤（因为最后一个元素是最大的，就不用参与步骤）直到全部比较完，所有的数组元素就都从小到大排好了。

3.实践（例题）。

AcWing 3375. 成绩排序
给定学生的成绩单，成绩单中包含每个学生的姓名和分数，请按照要求将成绩单按成绩从高到低或从低到高的顺序进行重新排列。

对于成绩相同的学生，无论以哪种顺序排列，都要按照原始成绩单中靠前的学生排列在前的规则处理。

输入格式
第一行包含整数 N，表示学生个数。

第二行包含一个整数 0 或 1，表示排序规则，0 表示从高到低，1 表示从低到高。

接下来 N 行，每行描述一个学生的信息，包含一个长度不超过 10 的小写字母构成的字符串表示姓名以及一个范围在 0∼100 的整数表示分数。

输出格式
输出重新排序后的成绩单。

每行输出一个学生的姓名和成绩，用单个空格隔开。

数据范围
1≤N≤1000
代码如下：

#include<bits/stdc++.h>
using namespace std;
struct student
{
    string name;
    int total;
};
student a[100000];
int main()
{
    int n,b;
    cin>>n>>b;

    for(int c=0;c<n;c++)
        {
            cin>>a[c].name;
            cin>>a[c].total;
        }
        if(b==0)//冒泡排序
        {
          for(int d=n-1;d>0;d--)
          for(int e=0;e<d;e++)
          if(a[e].total<a[e+1].total)
          swap(a[e],a[e+1]);
        }
        if(b==1)//冒泡排序
        {
          for(int d=n-1;d>0;d--)
          for(int e=0;e<d;e++)
          if(a[e].total>a[e+1].total)
          swap(a[e],a[e+1]);  
        }
        for(int f=0;f<n;f++)
        {
            cout<<a[f].name<<' '<<a[f].total<<endl;
        }
}

这些程序中的以下部分就用到了冒泡排序：

        if(b==0)
        {
          for(int d=n-1;d>0;d--)
          for(int e=0;e<d;e++)
          if(a[e].total<a[e+1].total)
          swap(a[e],a[e+1]);
        }
        if(b==1)
        {
          for(int d=n-1;d>0;d--)
          for(int e=0;e<d;e++)
          if(a[e].total>a[e+1].total)
          swap(a[e],a[e+1]);  
        }

4.时间复杂度。

冒泡排序在排序算法中比较简单，但是冒泡排序运行的时间比较长，他的时间复杂度是O(n2)。

你学会了吗？