课程咨询 :186 8716 1620      qq:2066486918

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

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

  • 选择排序很明确的就是有选择的进行派讯,昆明java培训希望小伙伴们好好学习吧!

    昆明java培训讲解选择排序你的特性:In-place sort,unstable sort。

    思想:每次找一个最小值。

    最好情况时间:O(n^2)。

    最坏情况时间:O(n^2)。

    昆明java培训

    证明算法正确性:

    循环不变式:A[1...i-1]包含了A中最小的i-1个元素,且已排序。

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

    保持:在某次迭代开始之前,保持循环不变式,即A[1...i-1]包含了A中最小的i-1个元素,且已排序,则进入循环体后,程序从 A[i...n]中找出最小值放在A[i]处,因此A[1...i]包含了A中最小的i个元素,且已排序,而i++,因此下一次循环之前,保持 循环不变式:A[1..i-1]包含了A中最小的i-1个元素,且已排序。

    终止:i=n,已知A[1...n-1]包含了A中最小的i-1个元素,且已排序,因此A[n]中的元素是最大的,因此A[1...n]已排序,证毕。

    算法导论2.2-2中问了"为什么伪代码中第3行只有循环n-1次而不是n次"?

    在循环不变式证明中也提到了,如果A[1...n-1]已排序,且包含了A中最小的n-1个元素,则A[n]肯定是最大的,因此肯定是已排序的。

    这是昆明java培训小编今天最后一个排序了,希望小伙伴们能够将昆明java培训小编今天所讲的内容都进一步理解,有可能的话将程序重新运行。

    推荐文章

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

下一篇:昆明java培训分享:实例变量

最新开班日期  |  更多

Java--零基础全日制班

Java--零基础全日制班

开班日期:12/29

Java--零基础业余班

Java--零基础业余班

开班日期:12/29

Java--周末提升班

Java--周末提升班

开班日期:12/29

Java--零基础周末班

Java--零基础周末班

开班日期:12/29

  • 网址: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