您的位置: 网站首页 > 程序开发 > 数据结构 > 第8章 排序 > 【8.5 各种排序方法的比较和选择】

8.5 各种排序方法的比较和选择

 

8.5  各种排序方法的比较和选择

8.5.1  各种排序方法的比较

1.从时间复杂度比较

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

2.从空间复杂度比较

归并排序的空间复杂度最大,为O(n),快速排序的空间复杂度为O(log2n),其他排序的空间复杂度为O(1)

3.从稳定性比较

直接插入排序、冒泡排序、归并排序都是稳定的排序方法,而直接选择排序、希尔排序、快速排序是不稳定的排序方法。

4.从算法简单性比较

直接插入排序、冒泡排序、直接选择排序都是简单的排序方法,算法简单,易于理解,而希尔排序、快速排序、归并排序都是改进型的排序方法,算法比简单排序要复杂得多,也难于理解。

8.5.2  各种内排序方法的选择

1.从时间复杂度选择

对记录个数较多的排序,可以选择快速排序、归并排序,记录个数较少时,可以选择简单的排序方法。

2.从空间复杂度选择

尽量选空间复杂度为O(1)的排序方法,其次选空间复杂度为O(log2n)的快速排序方法,最后选空间复杂度为O(n)的二路归并排序方法。

3.一般选择规则

1)当待排序记录的个数n较大,关键字分布是随机的,而对稳定性不做要求时,最好采用快速排序为好。

2)当待排序记录的个数n较大,内存空间允许,且要求排序稳定时,最好采用二路归并排序为好。

3)当待排序记录的个数n较大,记录的关键字可能会出现正序或反序的情况,且对稳定性不做要求时,最好采用二路归并排序。

4)当待排序记录的个数n较小,记录基本按关键字有序或分布较随机,且要求排序稳定时,最好采用直接插入排序。

5)当待排序记录的个数n较小,对稳定性不做要求时,采用直接选择排序为好,若记录的关键字不接近反序,也可以采用直接插入排序。