• 欢迎加“百元导航”为主页,windows8风格,0.3s极速加载
  • 王柏元的博客专用搜索引擎:极客人,就用“极客搜”!
  •    2年前 (2014-12-30)  算法语言 |   4 条评论  1077 
    文章评分 2 次,平均分 5.0

    1.插入排序:每次将一个待排的记录插入到前面的已经排好的队列中的适当位置。

    ①.直接插入排序

    直接排序法在最好情况下(待排序列已按关键码有序),每趟排序只需作1次比较而不需要移动元素。所以n个元素比较次数为n-1,移动次数0。
    最差的情况下(逆序),其中第i个元素必须和前面的元素进行比较i次,移动个数i+1,所以总共的比较次数 比较多,就不写出来了
    总结:是一种稳定的排序方法,时间复杂度O(n^2),排序过程中只要一个辅助空间,所以空间复杂度O(1)

    ②.希尔排序

    缩小增量排序,对直接插入排序的一种改进
    分组插入方法。
    总结:是一种不稳定的排序方法,时间复杂度O(n^1.25),空间复杂度O(1)

    2.交换排序

    ①.冒泡排序

    最好的情况下,就是正序,所以只要比较一次就行了,复杂度O(n)
    最坏的情况下,就是逆序,要比较n^2次才行,复杂度O(n^2)
    总结:稳定的排序方法,时间复杂度O(n^2),空间复杂度O(1),当待排序列有序时,效果比较好。

    ②.快速排序

    通过一趟排序将待排的记录分割成独立的两部分,其中一部分记录的关键字均比另一个部分的关键字小,然后再分别对这两个部分记录继续进行排序,以达到整个序列有效。
    总结:在所有同数量级O(nlogn)的排序方法中,快速排序是性能最好的一种方法,在待排序列无序时最好。算法的时间复杂度是O(nlogn),最坏的时间复杂度O(n^2),空间复杂度O(nlogn)

    3.选择排序

    ①.直接选择排序

    和序列的初始状态无关
    总结:时间复杂度O(n^2),无论最好还是最坏

    ②.堆排序

    直接选择排序的改进
    总结:时间复杂度O(nlogn),无论在最好还是最坏情况下都是O(nlogn)

    4.归并排序

    总结:时间复杂度O(nlogn),空间复杂度O(n)

    5.基数排序

    按组成关键字的各个数位的值进行排序,是分配排序的一种。不需要进行排码值间的比较就能够进行排序。
    总结:时间复杂度O(d(n+rd))

    总总结:

    n比较小的时候,适合 插入排序和选择排序
    基本有序的时候,适合 直接插入排序和冒泡排序
    n很大但是关键字的位数较少时,适合 链式基数排序
    n很大的时候,适合 快速排序 堆排序 归并排序
    无序的时候,适合 快速排序
    稳定的排序:冒泡排序 插入排序 归并排序 基数排序
    复杂度是O(nlogn):快速排序 堆排序 归并排序
    辅助空间(大 次大):归并排序 快速排序
    好坏情况一样:简单选择(n^2),堆排序(nlogn),归并排序(nlogn)
    最好是O(n)的:插入排序 冒泡排序

     

    王柏元的博客著作权保留,转载请注明出处http://wangbaiyuan.cn/data-summary-several-time-and-space-complexity-of-sorting-algorithms.html,如果你觉得这篇文章对你有用,可以点击下面的“赞助作者”打赏作者!

    关于
    记录生活,镌刻心路;泼洒文墨,分享技术!王柏元的博客致力于IT经验交流,并原创翻译引进外文文章,打开IT国际化视野

    发表评论

    格式
    1. 各种算法总结得很详细

      flow 评论达人 LV.1 12个月前 (12-19) [1] [0]
    2. 不错哦,数据结构考试前可以看一发

      始相知 评论达人 LV.1 12个月前 (12-19) [1] [0]
    3. 终于有一篇我可以看懂的博客了 :?:

      6艘恶露肚饿 评论达人 LV.4 2年前 (2015-01-03) [0] [0]
    4. 不明觉厉

      周家新 评论达人 LV.1 2年前 (2014-12-30) [0] [0]

    登录

    忘记密码 ?

    您也可以使用第三方帐号快捷登录

    切换登录

    注册