C++冒泡法排序

冒泡排序简介：
冒泡排序，最优时间复杂度O(N)，平均时间复杂度O(N^2)，最差空间复杂度O(N)，平均时间复杂度O(1)是一种代码简单的排序也是几乎最慢的算法，（稳定）。

冒泡排序原理：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动图演示：

代码实现：

#include<bits/stdc++.h>
using namespace std;
int n, a[10000005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)//输入
    cin>>a[i]; 
    for(int i=1;i<n;i++)//总共进行n-1轮冒泡
    {
         for(int j=1;j<=n-i;j++)//一轮冒泡  
         {
              if(a[j]>a[j+1])
              {
                   swap(a[j],a[j+1]);
              }
         }
    }
    for(int i=1;i<=n;i++)//输出
    cout<<a[i]<<" ";
    return 0;//结束
}

这就是最简单的排序算法——冒泡排序。

补充一下：

为了使我们更好的观察冒泡排序的过程，下面的程序可以将每轮冒泡输出。

#include<bits/stdc++.h>
using namespace std;
int n, a[105]; 
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];//输入 
    for(int i=1;  i<n ;  i++)  //n-1轮冒泡
    {    
        for(int j=1; j<= n-i ; j++)  //一轮冒泡
         {
              if( a[j]>a[j+1] ) 
                   swap(a[j],a[j+1]);   
         }
    for(int m=1; m<=n; m++) cout<<a[m]<<" ";  //输出
	cout<<endl;//换行
	}
    return 0;
}

输入，输出：

in：

9

9 5 6 8 2 7 3 4 1

out:

5 6 8 2 7 3 4 1 9

5 6 2 7 3 4 1 8 9

5 6 2 3 4 1 7 8 9

5 2 3 4 1 6 7 8 9

2 3 4 1 5 6 7 8 9

2 3 1 4 5 6 7 8 9

2 1 3 4 5 6 7 8 9

1 2 3 4 5 6 7 8 9

这就是这篇文章的全部内容，非常感谢你能看到这，如果可以，请给我点个赞，下期做插入、选择，和快排。

海报图正在生成中...

竖版 宽版