刚刚开始学习的同学，往往纠结于学习哪一门语言（python 还是 JAVA？）。其实，在程序设计中，最核心的内容是算法和数据结构，这俩货是决定程序执行效率的根源。

最常见的算法–排序

在日常生活中，我们经常会遇到排序，比如，体育课上排队的时候，老师一般会让同学们按身高进行排队；在网上购物时，往往会按照价格或者销量进行排序；在超市结账时，按照到达结账区的时间先后排序；在期末考试结束后，按照考试成绩进行排序……总之，在我们身边，排序几乎无处不在。

排序的算法有很多，排序算法大体可分为两类：一类是 比较排序 ，主要包括冒泡排序、快速排序、选择排序、插入排序、归并排序、堆排序等；另一种是 非比较排序 ，主要包括计数排序 、基数排序 、桶排序 等。

今天先学习一个经典的排序算法–冒泡排序。

冒泡排序

算法介绍

从任一序列头部开始，每次比较两个相邻的元素，交换排列顺序错误的元素，反复进行上述操作，直至序列中所有元素按照一定的顺序进行排列。

例如，我们需要将$2、8、32、87、93$这五个数字，从大到小进行排列，也就是说，越小的数字越靠后。

  1. 比较第一个和第二个数字，现在第一个是$2$，第 二个是 $8$。通过比较发现， $2$比 $8$ 要小，所以，要交换这两个数字的位置。交换之后这五个数的顺序是$8、\underline{2}、32、87、93$。
  2. 根据上述方法，继续比较第二个和第三个数字的大小，第二个是$2$，第 三个是$ 32$。发现$2$比$32$要小，所以，要交换。交换之后这五个数的顺序是$8、32、\underline{2}、87、93$。
  3. 继续比较第 三位和第 四 位的大小，交换之后这 五 个数的顺序是 $8、32、87、\underline{2}、93$。
  4. 最后，经过四 次比较之后 ，这五个数的顺序是 $8、32、87、93、\underline{2}$。

经过四次比较以后，我们发现最小的数字$2$已经到最后（到了正确的位置或者说“归位”）。下面我们来回忆一下$2$这个数字移动的过程，每次都是比较相邻的两个数，当后面的数比前面的数大时，则交换这两个数的位置。依次比较完毕后，最小的数就位于最后了。如果把数列竖起来，就数字$2$如同是一个“气泡”，一点一点冒到“水面”，所以我们把这个排序的方法叫作“冒泡排序”。

image-20210910164319667

经过上面的比较，我们只将 五个数中最小的一个“归位”了。将其中一个数字“归位”，我们称其为“一趟”。我们还需要将其他四个数字进行“归位”，所以，还要按照上述步骤运行“三趟”，此处不在重复介绍。排序完成后，这五个数字的顺序是$93、87、32、8、2$。

image-20210910164352859

C++程序

下面是代码。建议先自己写一遍代码，再来和我的代码进行比较，看一看各自代码的优缺点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include<iostream>
using namespace std;

int main(){
    int a[100], n;
    cin >> n; //n--共有n个数需要排序
    for(int i = 0; i < n; ++i) //读取n个数到数组a
        cin >> a[i];
    for(int i = 0; i < n - 1; ++i){ //n个数排序，只需要n-1趟
        for(int j = 0; j < n - 1 - i; ++j){//从第1位开始比较直到最后一个尚未归位的数
            if (a[j]<a[j+1]) //比较大小并交换
                swap(a[j], a[j+1]);
        }
    }
    
    for(int i = 0; i < n; ++i){//输出结果
        cout << a[i] << " ";
    }
}

image