数据结构&算法实践—冒泡排序及改进

排序>>交换排序>>冒泡排序

List:

  1. start

基本概念:

维基百科http://zh.wikipedia.org/wiki/%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F

伪代码:(来自百科)

简要排序过程的示例:(基本冒泡排序)

初始数组

第一轮:

第二轮:

第三轮

第四轮:

第五轮:

cmp count 15

即共进行n-1=5轮冒泡,比较次数为 (n-1) + (n-2) + ……+1 =n*(n-1)/2=15

  1. start

基本冒泡排序python实现:

  1. start

问题:在基本冒泡排序的示例中,第三轮结束时,其实已经排序完成了,但是还是一直会持续后面几轮的排序,这就带来了无谓的浪费.

改进:加入标志,判断,若是上一轮不存在数据交换,代表上一轮已经是排序的了,退出

比较次数:12

  1. start

局部冒泡排序:(资料不多,不知道自己理解对不对)

序列[ a b c d ] 冒泡到了b,此时a小于b,比较b c,若是 b 大于 c,交换b c 得到 [ a c b d ]

通常冒泡排序一直往前,继续比较b和d

其实,在完成一次数据交换时(bc),可以反向增加一次比较,(a 和 c) ,若是a>c,再次交换得到[ c a b d] ——反向做一次冒泡

(百度百科有几行….凑合看)

定义:可以在一趟全局扫描中,对每一反序数据对进行局部冒泡排序处理,称之为局部冒泡排序
局部冒泡排序与冒泡排序算法具有相同的时间复杂度,并且在正序和逆序的情况下,所需的关键字的比较次数和移动次数完全相同。
由于局部冒泡排序和冒泡排序的数据移动次数总是相同的,而局部冒泡排序所需关键字的比较次数常少于冒泡排序,这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改进
当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销,而当数据量较大时,局部冒泡排序的时间性能则明显优于冒泡排序
(查看百度百科,有张对比图)

简而言之,正向冒泡时,若存在数据交换,反向再进行一次冒泡比较。减少了比较次数

why?

假设在第二轮冒泡 到了50 30

共 8次

共 6次

局部冒泡排序一个示例过程:

  1. start

仅是贴出来,权当复习,木有答案,后续补充

A.冒泡排序概念,过程描述?

B.最差,平均,最优 时间复杂度?

C.空间复杂度?

D.是否是稳定排序?

E.如何改进?

F.局部冒泡排序原理?

G.适用场景,什么情况下最优,什么情况下最差?

—————————————– END ————————————————-

P.S.

这是第一篇,有什么不对请指正哈,欢迎补充任何问题和答案

白天上班加班(SDET),夜深敲代码(python,java…….),会坚持写完的

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

任选一种支付方式

1 1 收藏 评论

关于作者:wklken

Pythonista/vimer 个人主页 · 我的文章 · 37 ·   

可能感兴趣的话题



直接登录
跳到底部
返回顶部