六大常用排序算法

Share

六大常用排序算法

1
2
3
4
5
6
7
8
9
排序方法       时间复杂度            空间复杂度      稳定性    代码复杂度
         最坏情况 平均情况  最好情况
冒泡排序   O(N^2)  O(N^2)   O(N)       0(1)       稳定         简单
直接排序   O(N^2)  O(N^2)   O(N^2)     O(1)       不稳定       简单
直接插入   O(N^2)  O(nlogn) O(nlogn)   0(1)       稳定        简单
快速排序   O(N^2)  O(nlogn) O(nlogn) 平均O(logn)  不稳定       较复杂
                                    最坏情况O(n)
堆排序    O(nlogn) O(nlogn) O(nlogn)   O(1)      不稳定        复杂
归并排序  O(nlogn) O(nlogn) O(nlogn)   O(n)       稳定        较复杂

较高级排序算法

希尔排序（shell）

时间复杂度：最坏：O(N^2) 平均：O(N)~O(N^2)

  • 首先去一个整数d1 = n/2,将数据以d1为间隔分组，之后每组进行一次插入排序
  • 取第二个整数d2= d1/2, 重复上述步骤
  • 直至d 的值变为1 ，即完成排序

也可以按{5，3，1}进行增量排序

希尔排序每趟并不是使某些元素有序，而是使整体数据越来越趋近与有序

计数排序

时间复杂度：O(N)

  • 先创建一个范围表例如 [0，n]推荐用字典

  • 设数据都在范围标内，然后然后遍历数据,对每一数据进行计数

  • 最后根据计数创建出排列的好的序列

缺点：对于精度高的数据，消耗的空间多

桶排序（基于计数排序）

时间复杂度：平均：O(n+k) 最坏 O(n^2*k) 空间复杂度：O(nk) 其中k = logmlogn m为桶的容量

将元素分在不同的桶内，再对桶中的元素进行排序

  • 但是对桶内的数据可以以冒泡排序
基数排序

时间复杂度 ： O(nk) 空间复杂度 O(n+K)

  • 若有一整数数列
  • 先按个位排序，再按十位排序

按这个思路发散，即是基数排序