7.3.1 交换排序之冒泡排序

所谓交换,就是根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。

冒泡排序算法的基本思想是:假设待排序表长为n,从后往前(或从前往后)两两比较相邻元素的值。若为逆序(即A[i-1]>A[i]),则交换它们,直到序列比较完。我们称它为一趟冒泡。结果将最小的元素交换到待排序的第一个位置(关键字最小的元素如气泡一般逐渐往上漂浮,直到水面,这就是冒泡排序名字的由来)。下一趟冒泡时,前一趟确定的最小元素不再参与比较,待排序序列减少一个元素,每趟冒泡的结果把序列中的最小元素放到了序列的最终位置……,这样最多做n-1趟冒泡就把所有元素排好序。

void BubbleSort(ElemType A[],int n){
     //用冒泡排序法将序列A中的元素按从小到大排序
     for(i=0;i<n-1;i++){
         flag=false;//表示本趟冒泡是否发生交换的标志
         for(j=n-1;j>i;j--){//一趟冒泡过程
            if(A[j-1].key>A[j].key){//若为逆序
                swap(A[j-1],A[j]);//交换
                flag=true;
            }
         }
         if(flag==false){
            return;//本趟遍历后没有发生交换,说明表已经有序
         }
     }  
}

空间效率:仅适用常数个辅助单元,因而空间复杂度为O(1)。

时间效率:当初始化序列有序时,显然这一趟冒泡后flag依然为false(本趟冒泡没有元素交换),从而直接跳出循环,比较次数为n-1,移动次数为0,从而最好情况下的时间复杂度为O(n);当初始化序列为逆序时,需要进行n-1趟排序,第i趟排序要进行n-i次关键字的比较,而且每次比较都必须移动元素3次来交换元素位置。这种情况下比较次数为1+2+……+n-1=n(n-1)/2,移动次数=3n(n-1)/2。

从而,最坏情况下时间复杂度为O(n^2)。其平均时间复杂度也为O(n^2)。

稳定性:由于当i<j且A[i].key=A[j].key时,不会交换两个元素,从而冒泡排序是一个稳定的排序方法。

注意:冒泡排序中所产生的有序子序列一定是全局有序的(不同于直接插入排序),也就是说有序子序列中所有元素的关键字一定小于或者大于无序子序列中所有元素的关键字,这样每趟排序都会将一个元素放置到其最终的位置上。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python研发

go基础编程 day-2

  零值并不等于空值,而是当变量声明为某种来兴后的默认零值,通常情况下默认值为0,bool为false,string为空字符串。

1132
来自专栏ml

c语言格式大整理

1、C语言中,非零值为真,真用1表示;零值为假,假用0表示。 2、转义字符参考: \a 蜂鸣,响铃  \b 回退:向后退一格 ...

5537
来自专栏程序员互动联盟

【面试宝典】continue、break和return

面试官:continue会用吧。 小白:用来结束当前循环的。 面试官:那break呢? 小白:也是用来结束循环的。 面试官:那么它们的区别呢? 面试解析: 面试...

3678
来自专栏章鱼的慢慢技术路

Go语言_range(范围)理解

这是因为 for _ 表示遍历数组的下标,从nums[0],nums[1],nums[2]依次开始遍历,所以最后的值为sum=2+3+4=9;但是如果把 for...

812
来自专栏抠抠空间

列表(List) 的增删改查及其他方法

一、列表的简介     列表是python中的基础数据类型之一,其他语言中也有类似于列表的数据类型,比如js中叫数组,他是以[ ]括起来,每个元素以逗号隔开,而...

41015
来自专栏一枝花算不算浪漫

[jQuery学习系列二 ]2-JQuery学习二-数组操作

38412
来自专栏desperate633

为什么Java中类的成员变量不能被重写?成员变量在Java中能够被重写么?不会重写成员变量,而是隐藏成员变量访问隐藏域的方法

这篇文章讨论了Java面向对象概念中一个基本的概念--Field Hiding(成员变量隐藏)

1514
来自专栏Modeng的专栏

JavaScript中的正则表达式

版权声明:本文为原创文章发布于公众号:Modeng , 你可以随意转载但请务必注明出处!!!https://blog.csdn.net/qq_32135281/...

842
来自专栏闵开慧

$.each()与$(selector).each()区别详解

$.each()与$(selector).each()不同, 后者专用于jquery对象的遍历, 前者可用于遍历任何的集合(无论是数组或对象),如果是数组,回...

37212
来自专栏Java帮帮-微信公众号-技术文章全总结

第六天 知识点练习与回顾【悟空教程】

1736

扫码关注云+社区

领取腾讯云代金券