课程咨询 :186 8716 1620      qq:2066486918

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

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

  • 排序在程序中是需要经常使用到的地方,昆明java培训今天也将三种排序,小伙伴们要好好学习哦!

    昆明java培训讲述插入排序的特点:stable sort、In-place sort

    最优复杂度:当输入数组就是排好序的时候,复杂度为O(n),而快速排序在这种情况下会产生O(n^2)的复杂度。

    最差复杂度:当输入数组为倒序时,复杂度为O(n^2)

    插入排序比较适合用于“少量元素的数组”。

    其实插入排序的复杂度和逆序对的个数一样,当数组倒序时,逆序对的个数为n(n-1)/2,因此插入排序复杂度为O(n^2)。

    昆明java培训

    循环不变式:在每次循环开始前,A[1...i-1]包含了原来的A[1...i-1]的元素,并且已排序。

    初始:i=2,A[1...1]已排序,成立。

    保持:在迭代开始前,A[1...i-1]已排序,而循环体的目的是将A[i]插入A[1...i-1]中,使得A[1...i]排序,因此在下一轮迭代开 始前,i++,因此现在A[1...i-1]排好序了,因此保持循环不变式。

    终止:最后i=n+1,并且A[1...n]已排序,而A[1...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