十大排序算法整理(一):概览

十大排序算法分类、特点和关系

十大排序算法整理(一):概览

(1)冒泡排序(交换排序的一种)

(2)选择排序

(3)插入排序

(4)归并排序(采用了分治思想,额外的空间复杂度O(N),容易记错,最后合并大数组的时候需要开辟一个长度为N的数组)  https://blog.csdn.net/u010452388/article/details/81008727

(5)快速排序(采用了分治思想,交换排序的一种,额外的空间复杂度O(NlogN),容易记错)  

  • 归并排序每次递归需要用到一个辅助表,长度与待排序的表相等,虽然递归次数是O(log2n),但每次递归都会释放掉所占的辅助空间,所以下次递归的栈空间和辅助空间与这部分释放的空间就不相关了,因而空间复杂度还是O(n)。
  • 而快速排序每次递归都会返回一个中间值的位置,必须使用栈。所以空间复杂度就是栈用的空间。

(6)堆排序(树形的选择排序,非递归版空间复杂度才是O(1))

(7)希尔排序(插入排序的改进版)

(8)桶排序(分成多个桶,每个桶内采用其他方法排序)

(9)计数排序(桶排序思想的一种实现,(8)中桶排序的一种特例,即按照步长为1设定桶,桶内不需要内部排序)

(10)基数排序(桶排序思想的一种实现)

https://www.jianshu.com/p/ffe06398045b

  • 桶排序既可以看做是一种思想,也可以看做是最直接的桶排序实现,看语境

十大排序算法整理(一):概览

 右键:在新标签中打开图片

十大排序算法整理(一):概览