冒泡排序
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;
}