排序算法的总结

本文主要是介绍排序算法的总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

八大排序：

(1)时间复杂度
直接插入排序、冒泡排序、直接选择排序这三种简单排序方法的时间复杂度都为O(n²)，快速排序、堆排序、二路归并排序的时间复杂度都为O(nlogn)，希尔排序的时间复杂度介于这两者之间。若从最好的时间复杂度考虑，则直接插入排序和冒泡排序的时间复杂度最好为O(n) ,其他排序算法的最好情况同平均情况相同。若从最坏的时间复杂度考虑，则快速排序为O(n²)，直接插人排序、冒泡排序、希尔排序同平均情况相同,但系数大约增加倍，所以运行速度将降低一-半，而最坏情况对直接选择排序、堆排序和归并排序影响不大。

(2)空间复杂度
归并排序的空间复杂度最大，为O(n),快速排序的空间复杂度为O(nlogn)，其他排序的空间复杂度为0(1)。
(3)稳定性
一般来说，简单排序算法是稳定的排序算法，如直接插人排序、冒泡排序都是稳定的排序算法,但值得注意的是，直接选择排序是不稳定的。

各种排序算法的选择
(1)当待排序记录数n较大时，排序关键字随机分布，同时对稳定性无要求时，则采用快速排序为宜。
(2)当待排序记录数n较大，内存空间允许,且要求排序稳定时，采用二路归并排序为宜。
(3)当待排序记录数n较大,排序关键字可能会出现正序或逆序的情况，同时对稳定性无要求时，则采用堆排序或二路归并排序为宜。
(4)当待排序记录数n较小，元素基本有序或随机分布，且要求稳定时，则采用直接插人排序为宜。
(5)当待排序记录数n较小,同时对稳定性无要求时，则采用直接选择排序为宜;若排序码不接近逆序，也可以采用直接插人排序。
总之,对记录数较多的排序,可以选择快速排序、堆排序、归并排序;当记录数较少时，可以选择简单的排序方法。若从空间的角度上，则尽量选择空间复杂度为0(1)的排序方法。

这篇关于排序算法的总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！