什么叫做冒泡排序?

发布网友

共3个回答

热心网友

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。

　　大家一定都喝过汽水，汽水中常常有许多小小的气泡，哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻，所以小气泡可以一点一点向上浮动。而我们的冒泡排序之所以叫做冒泡排序，正是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身大小，一点一点向着数组的一侧移动。

冒泡排序算法的原理如下：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

具体如何来移动呢？让我们来看一个栗子：

请点击输入图片描述

有8个数组成一个无序数列：5，8，6，3，9，2，1，7，希望从小到大排序。按照冒泡排序的思想，我们要把相邻的元素两两比较，根据大小来交换元素的位置，过程如下：

首先让5和8比较，发现5比8要小，因此元素位置不变。

接下来让8和6比较，发现8比6要大，所以8和6交换位置。

请点击输入图片描述

继续让8和3比较，发现8比3要大，所以8和3交换位置。

请点击输入图片描述

继续让8和9比较，发现8比9要小，所以元素位置不变。

接下来让9和2比较，发现9比2要大，所以9和2交换位置。

请点击输入图片描述

接下来让9和1比较，发现9比1要大，所以9和1交换位置。

请点击输入图片描述

最后让9和7比较，发现9比7要大，所以9和7交换位置。

请点击输入图片描述

这样一来，元素9作为数列的最大元素，就像是汽水里的小气泡一样漂啊漂，漂到了最右侧。

这时候，我们的冒泡排序的第一轮结束了。数列最右侧的元素9可以认为是一个有序区域，有序区域目前只有一个元素。

请点击输入图片描述

下面，让我们来进行第二轮排序：

首先让5和6比较，发现5比6要小，因此元素位置不变。

接下来让6和3比较，发现6比3要大，所以6和3交换位置。

请点击输入图片描述

继续让6和8比较，发现6比8要小，因此元素位置不变。

接下来让8和2比较，发现8比2要大，所以8和2交换位置。

请点击输入图片描述

接下来让8和1比较，发现8比1要大，所以8和1交换位置。

请点击输入图片描述

继续让8和7比较，发现8比7要大，所以8和7交换位置。

请点击输入图片描述

第二轮排序结束后，我们数列右侧的有序区有了两个元素，顺序如下：

请点击输入图片描述

至于后续的交换细节，我们这里就不详细描述了，第三轮过后的状态如下：

请点击输入图片描述

第四轮过后状态如下：

请点击输入图片描述

第五轮过后状态如下：

请点击输入图片描述

第六轮过后状态如下：

请点击输入图片描述

第七轮过后状态如下（已经是有序了，所以没有改变）：

请点击输入图片描述

第八轮过后状态如下（同样没有改变）：

请点击输入图片描述

到此为止，所有元素都是有序的了，这就是冒泡排序的整体思路。

原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素，轮转的次数和元素数量相当，所以时间复杂度是O（N^2）。

冒泡排序代码

请点击输入图片描述

希望对您有所帮助！~

热心网友

冒泡排序（Bubble sort）是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为止。简单图示如下。

⌒ ⌒ ⌒ ..... ⌒
a1 a2 a3 … an-1 an

二、冒泡排序

1.从待排序队列的前端开始(a1)两两比较记录的关键字值，若ai>ai+1(i=1,2,…,n-1)，则交换ai和ai+1的位置，直到队列尾部。一趟冒泡处理，将序列中的最大值交换到an的位置。

2.如法炮制，第k趟冒泡，从待排序队列的前端开始(a1)两两比较ai和ai+1（i=1，2，…n-k)，并进行交换处理,选出序列中第k大的关键字值,放在有序队列的最前端。

3.最多执行n-1趟的冒泡处理，序列变为有序。

三、冒泡排序算法举例

设有数列{ 65,97,76,13,27,49,58 } 比较次数
第1趟 {65，76，13，27，49，58}，{97} 6
第2趟 {65，13，27，49，58}，{76，97} 5
第3趟 {13，27，49，58}，{65，76，97} 4
第4趟 {13，27，49}，{58，65，76，97} 3
第5趟 {13，27}，{49，58，65，76，97} 2
第6趟 {13}，{27，49，58，65，76，97} 1
总计： 21 次

从上述举例中可以看出，从第4趟冒泡起，序列已有序，结果是空跑了3趟。若两次冒泡处理过程中，没有进行交换，说明序列已有序，则停止交换。因此，我们可以对冒泡算法进行改进，减少比较次数。

如：对于数列{ 65,97,76,13,27,49,58 } 比较次数
第1趟 {65，76，13，27，49，58}，{97} 6
第2趟 {65，13，27，49，58}，{76，97} 5
第3趟 {13，27，49，58}，{65，76，97} 4
第4趟 {13，27，49}，{58，65，76，97} 3
总计： 18 次

热心网友

冒泡排序★★★★★★
#include<stdio.h>
#define N 5
void main()
{
int i,j;
int grade[N],temp;
printf("输入5个数\n");
for(i=0;i<N;i++)
{
scanf("%d",&grade[i]);
}
for(i=0;i<N;i++)
{
for(j=0;j<N-1-i;j++)
{
if(grade[j]<grade[j+1])
{
temp=grade[j+1];
grade[j+1]=grade[j];
grade[j]=temp;
}
}
}
printf("最后排序为:\n");
for(i=0;i<N;i++)
{
printf("%d",grade[i]);
}
printf("\n");
}
#include<stdio.h> //链接标准头文件
#define N 5 //定义常量N并赋值为5
void main() //主函数入口
{ //表示主函数开始
int i,j; //定义整形变量i和j
int grade[N],temp; //定义N维（N＝5，也就是五维啦^^）整形数组和整形变量temp
printf("输入5个数\n"); //在屏幕上显式“输入5个数”并且换行
for(i=0;i<N;i++) //开始for循环，从i＝0,每次加1，直到i=4,共需循环5次
{ //循环体开始
scanf("%d",&grade[i]); //依次获取用户输入的整数值并存入数组grade中
} //循环结束
for(i=0;i<N;i++) //开始外层for循环，从i＝0,每次加1，直到i=4
{ //外层循环体开始
for(j=0;j<N-1-i;j++) //开始外层for循环，从j＝0,每次加1直到i等于外层循环的N-j-1
{ //内层循环体开始
if(grade[j]<grade[j+1]) //条件判断
{ //如果整形数组前面的数比其后的小,执行以下语句
temp=grade[j+1]; //将比较大的数赋值给temp
grade[j+1]=grade[j]; //将比较小的数赋值给数组中后面的变量
grade[j]=temp; //将比较大的数赋值给数组中前面的变量
} //从此便完成大小变量的交换，使得大值往前放
} //结束内层循环
} //结外内层循环，完成排序
printf("最后排序为:\n");//在屏幕显式“最后排序为:”并换行
for(i=0;i<N;i++) //同开始的for循环类似
{ //开始循环输出
printf("%d",grade[i]); //只是这里要逐个输出数组中的五个数值
} //结束循环输出
printf("\n"); //输出换行到屏幕，看不到什么效果，可删掉
} //结束main()函数

全部栏目

什么叫做冒泡排序?