九种常见排序的比较

在这里插入图片描述

比较排序

在这里插入图片描述

由上表不难得出下面这几个重要的点：

从平均时间性能而言，快速排序最佳，其所需时间最佳，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。堆排序和归并之间，当n较大时，归并排序所需时间省，但是所需的辅助空间却是最大的，堆本身不是专门为排序产生的，而是解决优先级队列和TopK问题。
几种简单排序中，除了希尔排序外的所有插入排序，冒泡排序，和选择排序中，直接插入排序最为简单，并且当序列接近有序时或N值较小时，时间复杂度可以达到O(N)，因此在快速排序和归并排序中都用的高了直接插入排序。
从算法的稳定性而言，性能较好的几种排序算法都是不稳定的，什么叫稳定性，就是原序列中有相同的数，排完序后不改变其相对位置。

计数排序：

计数排序:时间复杂度:O(N), 空间复杂度O(最大数-最小数)

基数排序:时间复杂度:O(N*位数)，空间辅助度O(N)

计数排序和基数排序都是用与比较数之间较为几种的情况，计数排序关注最大数和最小数之间的区间大小，基数排序关注最大数的位数。

综上，没有那个算法是最好的，都要视具体的使用场景来看，不过综合而言快速排序是在实际中用的比较多的，比如c++ STL库中的sort()函数，底层就是快速排序。

最后再提一下稳定性问题，一般来说，排序过程中“比较”是在“相邻两个关键字”之间进行的排序方法都是稳定的。具体应用的，由于大多数情况下排序是按记录的主关键字进行的，则所需算法的稳定性就无关紧要了，但若是按记录的次关键字进行，这时候就要慎重选择排序算法了。