NOIP-C++大神培养计划Step1.2.1——排序之冒泡排序

  1. 云栖社区>
  2. 博客>
  3. 正文

NOIP-C++大神培养计划Step1.2.1——排序之冒泡排序

小笨笨qaq 2018-11-26 21:18:56 浏览476
展开阅读全文

在我们解决一些问题时,我们需要将所给的数据排序。排序算法也是一门基础算法,排序有许多种:冒泡排序,插入排序,选择排序,桶排序,快速排序,归并排序,希尔排序,堆排序,拓扑排序等(最后两种以后学数据结构和图论再讲)。


今天,我们就来走进第一个排序——冒泡排序。


我们先来看一个图:


f63d585c0ac9843248b50b6876ec6594cad4faf1


这就是冒泡排序的基本原理。第一层循环从n~2,第二层循环枚举第j和第j+1个数(1<=j<i),若a[ij>a[j+1],就叫换他们俩。(这里是从小到大升序排列)


这样,每执行完一个外层循环就确定第i个数(2<=i<=n),最终方可之其结果。


让我们来看代码:


#include<iostream>
using namespace std;
int n,a[10001];
void swap(int &a,int &b)
{
	int t=a;
	a=b;
	b=t;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=n;i>1;i--)
		for(int j=1;j<i;j++)
			if(a[j]>a[j+1])
				swap(a[j],a[j+1]);
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}



这个算法的复杂度是O(n^2),两层循环,时间复杂度还比较高。我们想来看看大数据的效率。


直接在代码中加一些代码:



#include<iostream>
#include<ctime>
using namespace std;
int n,a[10001];
void swap(int &a,int &b)
{
	int t=a;
	a=b;
	b=t;
}
int main()
{
	int start=clock();//开始时间 
	freopen("num.txt","r",stdin);//用freopen增加程序输入效率 
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=n;i>1;i--)
		for(int j=1;j<i;j++)
			if(a[j]>a[j+1])
				swap(a[j],a[j+1]);
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	int end=clock();//结束时间
	cout<<"Run time in"<<end-start<<"ms"<<endl; 
	return 0;
}


由于我们的电脑不同,所以所测试间不同。其实,我们这个算法还是不够好的,我们可以进行优化。


比如说6个数:2,1,4,6,3,5  我们来排序。


冒泡第一轮:


1324562308008596dbd5b0f4e97473c1d5da62f9

第二轮:

        fc27a9eea9aa207ad38f3a82bc62d1209cd6a348

接下来,我们不难发现,序列已经排好,之后的循环都是不必要的!!!

既然是不必要,我们就把它删了呗!


优化流程:

用一个bool变量判断是否有交换。初始化为0,交换了,就变成1。这一层循环结束之后,若它还是0,也就是没有交换,直接退出。


代码如下:


#include<iostream>
using namespace std;
int n,a[10001];
bool v=0;
void swap(int &a,int &b)
{
	int t=a;
	a=b;
	b=t;
}
int main()
{ 
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=n;i>1;i--){
		v=0;
		for(int j=1;j<i;j++)
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
				v=1;
			}
		if(!v)//v=0
			break;//跳出循环 
	}
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	cout<<endl;
	return 0;
}

虽然不是每组数据都能优化,但是总有节约时间的地方。


我们还能将它写成函数形式:



void bubble_sort(int n,int a[]){
	for(int i=n;i>=1;i--){
		bool v=0;
		for(int j=1;j<i;j++)
			if(a[j]>a[j+1]){
				swap(a[j],a[j]+1);
				v=1;
			}
		if(!v){
			break;
		}
	}
	return;
}

到这里,冒泡排序的介绍就结束了。那么,大家会不会有疑问:这个冒泡排序效率不是最高的,也不是最方便的,学他干什么呢?不是浪费时间吗?


其实不是。任何一种算法都有他立足与信息学世界的理由。


冒泡排序的实质就是将相邻两个数交换,于是,我们可以利用这一点来求解特定的问题。


栗1.2.1-1 洛谷P1116 车厢重组

https://www.luogu.org/problemnew/show/P1116


题目描述

在一个旧式的火车站旁边有一座桥,其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢,如果将桥旋转180度,则可以把相邻两节车厢的位置交换,用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后,火车站决定将这一工作自动化,其中一项重要的工作是编一个程序,输入初始的车厢顺序,计算最少用多少步就能将车厢排序。

输入输出格式

输入格式:

共两行。

车厢总数N,N<=10000

第二行是N个不同的数表示初始的车厢顺序。

输出格式:

一个整数,最少的旋转次数。

输入输出样例

输入样例#1:
4
4 3 2 1 
输出样例#1:  
6




不难看出,这题要用冒泡排序来求解。

我们每交换一次,Ans++,表示旋转次数++。这题就迎刃而解了。

来看代码吧:


#include<iostream>
using namespace std;
int n,a[10001],Ans=0;
bool v=0;
void swap(int &a,int &b)
{
	int t=a;
	a=b;
	b=t;
}
int main()
{ 
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=n;i>1;i--){
		v=0;
		for(int j=1;j<i;j++)
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
				v=1;
				Ans++;
			}
		if(!v)
			break; 
	}
	cout<<Ans<<endl;
	return 0;
}

这题就这么过了吧,也没太大难度。

但是,我们不应该这么过。一位叫小学生的洛谷用户提供了这样的算法:

作者: 小学生 更新时间: 2018-04-26 08:44  在Ta的博客查看   


  • 我看了其他题解都是做了排序,可是题目只是问需要多少次移动,没问排序结果啊!!!

  • 所以我没有做排序,只是迭代去计算每个数字前有几个数字比它大,这意味着它必须要移动几次。

  • 没有做冒泡排序,双层循环写法也和冒泡无关。


#include <iostream>
using namespace std;
int n, sum;
int main()
{
    cin >> n;
    int a[n];
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (a[j] > a[i])
                ++sum;
    cout << sum;
    return 0;
}

我们看看他的算法。

第一眼望过去,貌似是错的。没有改变之前的状态,后面怎么排序呢?

好吧,他说了,不用排序。其实思想跟冒泡排序没太大差别。

我们想一想,假设有n个数,6,5,4,3,2,1。

在6后面,有5个比6小的数,就要旋转5次,

在5后面,有4个比5小的数,就要旋转4次,

······

在1后面,有0个比1小的数,就要旋转0次,

SO,Ans=0+1+2+3+4+5=15。

结果完全一样。

好了,今天的内容就到这里,我们下一期将给大家介绍插入排序,我们下次见!




网友评论

登录后评论
0/500
评论
小笨笨qaq
+ 关注