首页 > 编程语言 > 详细

排序算法复杂度

时间:2019-03-15 22:05:27      阅读:20      评论:0      收藏:0      [点我收藏+]

标签:sub   style   nbsp   外排序   算法复杂度   justify   表示   复杂度   直接   

内排序

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。

内排序有可以分为以下几类:

  (1)、插入排序:直接插入排序、二分法插入排序、希尔排序。

  (2)、选择排序:直接选择排序、堆排序。

  (3)、交换排序:冒泡排序、快速排序。

  (4)、归并排序

  (5)、基数排序

复杂度

排序方法

时间复杂度

空间复杂度

稳定性

平均情况

最好情况

最坏情况

插入排序

直接插入

O(n2)

O(n)

O(n2)

O(1)

稳定

Shell排序

O(n1~2)

O(nlog2n)

O(n2)

O(1)

不稳定

选择排序

直接选择

O(n2)

O(n2)

O(n2)

O(1)

不稳定

堆排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(1)

不稳定

交换排序

冒泡排序

O(n2)

O(n)

O(n2)

O(1)

稳定

快速排序

O(nlog2n)

O(nlog2n)

O(n2)

O(nlog2n)

不稳定

归并排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(n)

稳定

基数排序

O(d(n+r))

O(d(n+r))

O(d(n+r))

O(n+rd)

稳定

注:1.希尔排序的时间复杂度和增量的选择有关。

      2.基数排序的复杂度中,r代表关键字的基数,d代表长度,n表示关键字的个数。

 

排序算法复杂度

标签:sub   style   nbsp   外排序   算法复杂度   justify   表示   复杂度   直接   

原文:https://www.cnblogs.com/fanguangdexiaoyuer/p/10539631.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号