信息学奥赛一本通——冒泡算法——1310:【例2.2】车厢重组
【题目描述】
在一个旧式的火车站旁边有一座桥,其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢,如果将桥旋转180度,则可以把相邻两节车厢的位置交换,用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后,火车站决定将这一工作自动化,其中一项重要的工作是编一个程序,输入初始的车厢顺序,计算最少用多少步就能将车厢排序。
【输入】
有两行数据,第一行是车厢总数N(不大于10000),第二行是N个不同的数表示初始的车厢顺序。
【输出】
一个数据,是最少的旋转次数。
【输入样例】
4
4 3 2 1
【输出样例】
6
今天我们来看一下一道基础算法题,冒泡排序。
首先分析一下题目。有一座可以转动的桥,一次只能将相邻的两个车厢交换,问我们最少多少次将车厢号按从小到大排序。
而我们所用的算法就是:冒泡排序
冒泡算法:
比较相邻的前后两个数据,如果前面数据大于后面的数据,就将两个数据交换。
对数组的第1个数据到n个数据进行一次遍历后,最大的一个数据就“冒”到数组第n个位置
然后进行第二轮,第三轮,。。。
首先我们先来模拟一下样例。
我们从头进行判断,比较第一个数和第二个数,发现前面的数大于后面的数,我们将它们的位置进行交换,
接着再把交换好的第二个数和第三个数比较,发现第二个数比第三个数大,所以我们把它们交换。
直到最后,我们将数字4依次和后面的所有数进行比较,如果4大于后面的数,我们把它们进行交换,
如果小于或等于则把4固定到这个位置,并从下一个位置的数开始比较。
这样每一次的排序,总能把当前数中的最大值给拍到最后。
这就要求我们在写代码的时候注意:
第一次循环,进行n-1次操作(最多进行n-1次排序,就可以把最大的数放到后面排好序了)
第二次循环,进行n-2次操作,(最多进行n-2次排序,就可以把第二大的数放到倒第二的位置了)
然后一次减小操作次数
因此,我们需要两重循环,第一重控制每一次的比较次数,第二重控制当前数和下一个数比较,并一直比较到结尾。
下面话不多说,把代码奉上:
#include <iostream>
using namespace std;
const int N = 10010;
int n;
int a[N];//全局变量,默认a数组里的所有数的值都是0
int main(){
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];//读入数据
int cnt = 0;//计数
for (int i = n - 1; i >= 1; i -- ){//控制每次循环的次数
for (int j = 1; j <= i; j ++ ){//每次循环i次
if (a[j] > a[j + 1]){//判断
int temp = a[j];//交换两个数
a[j] = a[j + 1];
a[j + 1] = temp;
cnt ++;
}
}
}
cout << cnt << endl;//输出结果
return 0;
}
上一篇: 一本通1329细胞(使用广度优先搜索)