冒泡排序

2018-12-17  本文已影响0人  点一下我的id

冒泡排序(交换排序)

基本思想:每趟不断将记录两两比较,并按“前小后大”
交换规则
第一行趟数i从1算起,因为两两交换,第一趟最多只能比较n-1次,推理第n-1趟比较1次,故总趟数=n-1。
第二行比较次数j,因为两两比较,第一趟,最多比较n-1次,推理第i趟最多比较n-i次。
例子
总数n=3,数组a[3]={3,2,1},共需要n-1=3-1=2趟交换
3 2 1

第一趟 2 1 3 第一次比较n-i=3-1=两次
第二趟 1 2 3 第二次比较n-i=3-2=一次
#include<iostream>
using namespace std;
int main()
{
    int n=6,a[6]={21,25,49,25,16,8};//定义 n为整数,a为整数组
    for(int i=1;i<=n-1;i++)     //趟数n-1
    {
        for(int j=0;j<n-i;j++)  //比较次数n-i
        {
            if(a[j]>a[j+1])     //如果前面的数比后面的大,交换
            {
                int t=a[j];     //定义t为整数型,用于暂时保存大的值
                a[j]=a[j+1];    //交换次序,a[j+1]较小,放前面
                a[j+1]=t;       //a[j+1]从暂时保存的大的值t取回来
            }
        }
    }
    return 0;
}

过程展示

21 25 49 25 16 8    初始值
21 25 *25 *16 *8 49 第一趟
21 25 *16 *8 25 49  第二趟
21 *16 *8 25 25 49  第三趟
*16 *8 21 25 25 49  第四趟
*8 16 21 25 25 49   第五趟

优点:每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素;一旦下趟没有交换,还可提前结束排序
改进代码

#include<iostream>
using namespace std;
int main()
{
    int n=6,a[6]={21,25,49,25,16,8};//定义 n为整数,a为整数组
    for(int i=1,flag=1;i<=n-1;i++)      //趟数n-1
    {
        flag=0;
        for(int j=0;j<n-i;j++)  //比较次数n-i
        {
            if(a[j]>a[j+1])     //如果前面的数比后面的大,交换
            {
                flag=1;
                int t=a[j];     //定义t为整数型,用于暂时保存大的值
                a[j]=a[j+1];    //交换次序,a[j+1]较小,放前面
                a[j+1]=t;       //a[j+1]从暂时保存的大的值t取回来
            }
        }
        if(flag!=1)
            break;
    }
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}
上一篇 下一篇

猜你喜欢

热点阅读