昆明java培训
达内昆明广州春城路

18487146383

热门课程

昆明java培训分享:冒泡排序

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

昆明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培训分享:选择排序

“因材施教,分级培优”十问十答

达内举办“2016授课讲师资格认证培训“,不断提升教学品质

达内牵手猿圈科技,打造技能测评、学习、就业一站式服务

毕业三年之内能转行学编程吗?

选择城市和中心
贵州省

广西省

海南省

台湾