排序(1):冒泡排序

2017年12月23日11:03:09 8 6,206 °C
摘要

冒泡排序是一种交换排序。什么是交换排序呢?答曰:两两比较待排序的关键字,并交换不满足次序要求的那对数,直到整个表都满足次序要求为止。

排序(1):冒泡排序

一、前言

冒泡排序是一种交换排序。

什么是交换排序呢?

答曰:两两比较待排序的关键字,并交换不满足次序要求的那对数,直到整个表都满足次序要求为止。

二、算法思想

它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端,故名冒泡排序。

动态效果示意图:

排序(1):冒泡排序

假设有一个大小为 N 的无序序列。以升序冒泡排序为例,冒泡排序就是要每趟排序过程中通过两两比较相邻元素,将小的数字放到前面,大的数字放在后面。

1、代码

C++:

运行结果:

排序(1):冒泡排序

Python:

运行效果同上。

三、算法分析

1、冒泡排序算法的性能

排序(1):冒泡排序

2、时间复杂度

若文件的初始状态是正序的,一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值:Cmin = N - 1, Mmin = 0。所以,冒泡排序最好时间复杂度为O(N)。

但是上述代码,不能扫描一趟就完成排序,它会进行全扫描。所以一个改进的方法就是,当冒泡中途发现已经为正序了,便无需继续比对下去。改进方法一会儿介绍。

若初始文件是反序的,需要进行 N -1 趟排序。每趟排序要进行 N - i 次关键字的比较(1 ≤ i ≤ N - 1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

Cmax = N(N-1)/2 = O(N^2)

Mmax = 3N(N-1)/2 = O(N^2)

冒泡排序的最坏时间复杂度为O(N^2)。

因此,冒泡排序的平均时间复杂度为O(N^2)。

总结起来,其实就是一句话:当数据越接近正序时,冒泡排序性能越好。

3、算法稳定性

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。

冒泡排序就是把小的元素往前调或者把大的元素往后调。是相邻的两个元素的比较,交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法

四、优化

对冒泡排序常见的改进方法是加入标志性变量exchange,用于标志某一趟排序过程中是否有数据交换。

如果进行某一趟排序时并没有进行数据交换,则说明所有数据已经有序,可立即结束排序,避免不必要的比较过程。

1、代码

C++:

运行结果:

排序(1):冒泡排序

Python:

运行效果同上。

 

本站整理自:

http://www.cnblogs.com/jingmoxukong/p/4302718.html

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:8   其中:访客  4   博主  4

    • avatar test 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学四舍(女生) 0

      666666666不错

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学四舍(女生)

          @test :idea: :idea: :idea:

        • avatar 海马儿 来自天朝的朋友 搜狗浏览器 Windows 10 江苏省苏州市 电信 0

          第二轮遍历,for(j=i;;),从i开始可否会更好点,前面的已经交换过了,从当前值继续换?

            • avatar Jack Cui Admin 这家伙可能用了美佬的代理 谷歌浏览器 Windows 10 美国 弗吉尼亚州

              @海马儿 对的,排好序的可以不用再管了。

            • avatar 紫潇银月 来自天朝的朋友 谷歌浏览器 Windows 10 湖北省恩施州 电信 4

              博主,你好,刚开始入门python,这边的几个程序的python版本是多少的呀,我用3.7运行的时候,没有报错也没有结果。。。。。。

                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点

                  @紫潇银月 python3.x的,你应该在ide中运行或者cmd中运行哈。

                • avatar 黄同学 来自天朝的朋友 Netscape Navigator iPhone iPhone OS 12_0 like Mac OS X) AppleWebKit 福建省泉州市 电信 0

                  博主,您好,动态效果示意图用什么工具弄的?

                    • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

                      @黄同学 你好,这个是网图,这一系列我都是直接百度**排序算法动态示意图找到的。