直接插入排序、冒泡排序、直接选择排序是3种简单的排序方法,时间复杂度均为O(n2),而快速排序、二路归并排序的时间复杂度都为O(log2n),希尔排序的时间复杂度大致介于这两者之间。若从最好的时间复杂度考虑,则直接插入排序和冒泡排序的时间复杂度最好为O(n),其他的最好时间复杂度同平均情况相同。若从最坏的时间复杂度考虑,则快速排序的为O(n2),直接插入排序、冒泡排序、希尔排序同平均情况相同,但系数大约增加一倍,所以运行速度将降低一半,最坏情况对直接选择排序和归并排序影响不大。
归并排序的空间复杂度最大,为O(n),快速排序的空间复杂度为O(log2n),其他排序的空间复杂度为O(1)。
直接插入排序、冒泡排序、归并排序都是稳定的排序方法,而直接选择排序、希尔排序、快速排序是不稳定的排序方法。
直接插入排序、冒泡排序、直接选择排序都是简单的排序方法,算法简单,易于理解,而希尔排序、快速排序、归并排序都是改进型的排序方法,算法比简单排序要复杂得多,也难于理解。
对记录个数较多的排序,可以选择快速排序、归并排序,记录个数较少时,可以选择简单的排序方法。
尽量选空间复杂度为O(1)的排序方法,其次选空间复杂度为O(log2n)的快速排序方法,最后选空间复杂度为O(n)的二路归并排序方法。
(1)当待排序记录的个数n较大,关键字分布是随机的,而对稳定性不做要求时,最好采用快速排序为好。
(2)当待排序记录的个数n较大,内存空间允许,且要求排序稳定时,最好采用二路归并排序为好。
(3)当待排序记录的个数n较大,记录的关键字可能会出现正序或反序的情况,且对稳定性不做要求时,最好采用二路归并排序。
(4)当待排序记录的个数n较小,记录基本按关键字有序或分布较随机,且要求排序稳定时,最好采用直接插入排序。
(5)当待排序记录的个数n较小,对稳定性不做要求时,采用直接选择排序为好,若记录的关键字不接近反序,也可以采用直接插入排序。