冒泡排序
基本思路:对于一组要排序的元素列,依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面,如此继续,直到比较到最后的两个数,将小数放在前面,大数放在后面,重复步骤,直至全部排序完成。
例子:数组Num[5]={9,6,7,3,1},要求将Num内的元素进行冒泡排序并打印出来。
分析:
过程:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210126204115774.png)
Num[5]第一次进行一次整体的比较后,筛选出了9这个最大值后,后续的比较中,9不会进行比较.
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210126204243622.png)
Num[5]根据上次同样的步骤进行比较后,筛选出7后,后续的比较中,7不会进行比较.
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210126204347487.png)
Num[5]根据上次同样的步骤进行比较后,筛选出6后,后续的比较中,6不会进行比较.
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210126204435146.png)
当最后两个数完成比较后,本次排序结束。
过程总结:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210522164007372.png)
排序轮数的总轮数是与元素的个数相关,排序的总轮数=元素个数-1(不包括与自己比较).
比较次数也是与元素的个数相关,每层比较的次数=元素个数-1
每进行一次排序轮数,就会筛选出一个最大值,并且本次筛选的最大值不会参与下一次排序的比较中,所以每进行一次排序轮数,都会少一个相对最大值,从而影响每一层的比较次数,每层比较次数=元素个数-已进行的排序轮数-1(这里要减1的原因是防止数组越界,比如数组长度为3,当数组小标为2时,长度为3,如果数组下标再加1,则长度为4,则会超过数组的访问范围)
代码思路:需要两个循环和数的交换代码来实现,外循环是用来实现排序轮数,内循环用来实现比较次数,交换代码的功能是用来实现比较两个数,并且将小数放前,大数放后。
代码:
#include <iostream>
using namespace std;
int main ()
{
int num[5]={9,6,7,3,1};
for(int i=0;i<5-1;i++) //排序轮数
{
for(int j=0;j<5-i-1;j++) //比较次数
{
if(num[j]>num[j+1]) //数的交换代码
{
int temp;
temp=num[j];
num[j]=num[j+1];
num[j+1]=temp;
}
}
}
for (int k=0;k<5;k++)
cout<<num[k]<<" ";
system ("pause");
return 0;
}
运行界面:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210126204852226.png)
总结:
冒泡排序的难点有两个,第一是如何对两个数的大小进行判断并是否进行交互;第二是外、内层的循环实现的规律。