课程咨询 :186 8716 1620      qq:2066486918

昆明Java培训 > 达内新闻 > 昆明java培训分享:冒泡排序
  • 昆明java培训分享:冒泡排序

    发布:昆明Java培训      来源:达内新闻      时间:2016-01-05

  • 昆明java培训

    其实这个算法好像我们之前是讲过一下的,不过这一次整合了所有的排序算法就来和昆明java培训一起学习吧!

    昆明java培训介绍冒泡排序特点:stable sort、In-place sort

    思想:通过两两交换,像水中的泡泡一样,小的先冒出来,大的后冒出来。

    最坏运行时间:O(n^2)

    最佳运行时间:O(n^2)(当然,也可以进行改进使得最佳运行时间为O(n))

    证明算法正确性:

    运用两次循环不变式,先证明第4-6行的内循环,再证明外循环。

    内循环不变式:在每次循环开始前,A[j]是A[j...n]中最小的元素。

    初始:j=n,因此A[n]是A[n...n]的最小元素。

    保持:当循环开始时,已知A[j]是A[j...n]的最小元素,将A[j]与A[j-1]比较,并将较小者放在j-1位置,因此能够说明A[j-1]是A[j-1...n]的最小元素,因此循环不变式保持。

    终止:j=i,已知A[i]是A[i...n]中最小的元素,证毕。

    接下来证明外循环不变式:在每次循环之前,A[1...i-1]包含了A中最小的i-1个元素,且已排序:A[1]<=A[2]<=...<=A[i-1]。

    初始:i=1,因此A[1..0]=空,因此成立。

    保持:当循环开始时,已知A[1...i-1]是A中最小的i-1个元素,且A[1]<=A[2]<=...<=A[i-1],根据内循环不变式,终止时A[i]是A[i...n]中最小的元素,因此A[1...i]包含了A中最小的i个元素,且A[1]<=A[2]<=...<=A[i-1]<=A[i]

    终止:i=n+1,已知A[1...n]是A中最小的n个元素,且A[1]<=A[2]<=...<=A[n],得证。

    很多人都能够将冒泡排序的算法全部理解透彻,但是当我们要开始写程序的时候却不知道怎么办了,不懂的快来咨询昆明java培训带班项目经理吧!

    推荐文章

上一篇:昆明java培训分享:插入排序

下一篇:昆明java培训分享:选择排序

最新开班日期  |  更多

Java--零基础全日制班

Java--零基础全日制班

开班日期:11/30

Java--零基础业余班

Java--零基础业余班

开班日期:11/30

Java--周末提升班

Java--周末提升班

开班日期:11/30

Java--零基础周末班

Java--零基础周末班

开班日期:11/30

  • 网址:http://km .java.tedu.cn      地址:昆明市官渡区春城路62号证券大厦附楼6楼
  • 课程培训电话:186 8716 1620      qq:2066486918    全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56