排序总结（排序算法稳定性、如何选择排序算法以及排序算法常见的坑）

本文主要是介绍排序总结（排序算法稳定性、如何选择排序算法以及排序算法常见的坑），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、稳定性

处理相等数时的态度，可以决定算法的稳定性

时间复杂度为O(N^2) 空间复杂度O（1）的排序：

        选择排序：无稳定性

        冒泡排序：有稳定性

        插入排序：有稳定性

时间复杂度为O(N*logN)的排序：

        归并排序：有稳定性（空间复杂度：O（N））

        随机快排：无稳定性（空间复杂度：O（logN））

        堆排序：无稳定性（空间复杂度：O（1））

时间复杂度为O(N)的排序：

        计数排序：有稳定性（空间复杂度：O（M））

        基数排序：有稳定性（空间复杂度:O（N））

二、如何选择排序算法：

（1）想要绝对的速度选择快排

（2）想要节省空间选择堆排

（3）想要稳定性选择归并排序

三、常见的坑

（1）归并排序的额外空间复杂度可以变成O（1），但是将变得不再稳定，（通过“归并排序内部缓存法”实现，不推荐无意义，可以用堆排序）

（2）原地归并排序，会使时间复杂度变为O（N^2）（还不如直接选择插入排序）

（3）将快排稳定性改进，但是会对样本数据要求更多，还不如选择桶排序

这篇关于排序总结（排序算法稳定性、如何选择排序算法以及排序算法常见的坑）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！