冒泡排序算法(起泡排序)及其C语言实现

冒泡排序算法(起泡排序)及其C语言实现更多学习资料Q群:569268376例如,对无序表{49,38,65,97,76,13,27,49}进行升序排序的具体实现过程如图1所示:图1第

欢迎大家来到IT世界,在知识的湖畔探索吧!

冒泡排序

起泡排序,别名“冒泡排序”,该算法的核心思想是将无序表中的所有记录,通过两两比较关键字,得出升序序列或者降序序列。

冒泡排序算法(起泡排序)及其C语言实现

更多学习资料Q群:569268376

例如,对无序表{49,38,65,97,76,13,27,49}进行升序排序的具体实现过程如 1 所示:

冒泡排序算法(起泡排序)及其C语言实现

图 1 第一次起泡

如图 1 所示是对无序表的第一次起泡排序,最终将无序表中的最大值 97 找到并存储在表的最后一个位置。具体实现过程为:

  1. 首先 49 和 38 比较,由于 38<49,所以两者交换位置,即从(1)到(2)的转变;
  2. 然后继续下标为 1 的同下标为 2 的进行比较,由于 49<65,所以不移动位置,(3)中 65 同 97 比较得知,两者也不需要移动位置;
  3. 直至(4),97 同 76 进行比较,76<97,两者交换位置,如(5)所示;
  4. 同样 97>13(5)、97>27(6)、97>49(7),所以经过一次冒泡排序,最终在无序表中找到一个最大值 97,第一次冒泡结束;

由于 97 已经判断为最大值,所以第二次冒泡排序时就需要找出除 97 之外的无序表中的最大值,比较过程和第一次完全相同。

冒泡排序算法(起泡排序)及其C语言实现

经过第二次冒泡,最终找到了除 97 之外的又一个最大值 76,比较过程完全一样,这里不再描述。

通过一趟趟的比较,一个个的“最大值”被找到并移动到相应位置,直到检测到表中数据已经有序,或者比较次数等同于表中含有记录的个数,排序结束,这就是起泡排序。

完整代码

#include <stdio.h>
//交换 a 和 b 的位置的函数
void swap(int *a, int *b);
int main()
{
 int array[8] = {49,38,65,97,76,13,27,49};
 int i, j;
 int key;
 //有多少记录,就需要多少次冒泡,当比较过程,所有记录都按照升序排列时,排序结束
 for (i = 0; i < 8; i++){
 key=0;//每次开始冒泡前,初始化 key 值为 0
 //每次起泡从下标为 0 开始,到 8-i 结束
 for (j = 0; j+1<8-i; j++){
 if (array[j] > array[j+1]){
 key=1;
 swap(&array[j], &array[j+1]);
 }
 }
 //如果 key 值为 0,表明表中记录排序完成
 if (key==0) {
 break;
 }
 }
 for (i = 0; i < 8; i++){
 printf("%d ", array[i]);
 }
 return 0;
}
void swap(int *a, int *b){
 int temp;
 temp = *a;
 *a = *b;
 *b = temp;
}

欢迎大家来到IT世界,在知识的湖畔探索吧!

运行结果为:

13 27 38 49 49 65 76 97

总结

使用起泡排序算法,其时间复杂度同实际表中数据的无序程度有关。若表中记录本身为正序存放,则整个排序过程只需进行 n-1(n 为表中记录的个数)次比较,且不需要移动记录;若表中记录为逆序存放(最坏的情况),则需要 n-1趟排序,进行 n(n-1)/2 次比较和数据的移动。所以该算法的时间复杂度为O(n2)。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/22346.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信