排序(1):冒泡排序

  • 6
  • 3,886 °C
  • A+
所属分类:算法基础
摘要

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

排序(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、算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。

所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法

四、优化

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

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

1、代码

C++:

运行结果:

排序(1):冒泡排序

Python:

运行效果同上。

 

本站整理自:

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

Jack Cui

发表评论

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

目前评论:6   其中:访客  3   博主  3

    • 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 湖北省恩施州 电信 3

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

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

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