排序算法总结

同样先上这张图

最后我们总结一下这八种排序算法：

从时间复杂度上来讲：

可以把这8个算法分为三类，第一类是效率比较差的，插入排序、选择排序和冒泡排序，它们的时间复杂度都是O(n2)，其中冒泡和插入在最好情况下可以达到O(n)，所以可以说，选择排序是所有算法中效率最差的，因为它最简单粗暴。

第二类是效率比较高的，希尔排序、堆排序、合并排序和快速排序，它们的时间复杂度为O(nlogn)。其中快速排序在最差情况下为O(n2)，较堆和希尔、合并差，但在其它情况下，快速排序的表现是最优秀的。

第三类是多关键字排序，基数排序，其复杂度为O(d(n+r))。

从空间复杂度上来讲：

除了合并排序和基数排序需要用到额外空间，其它排序都不需要，空间复杂度为O(1)，合并排序的空间复杂度为O(n)，基数排序的空间为O(d+n)。

从稳定性上来讲：

稳定的算法有：插入排序、冒泡排序、合并排序和基数排序。