第八章 排序 各种排序算法的比较

各种排序算法的比较

时间复杂度

平均????????????????????????????????最好????????????????????最坏????????????????????辅助空间

直接插入排序 : ????$O(n^2)$ ???????????????????????$O(n)$ ???????? ????$O(n^2)$ ????????????? ??????$O(1)$

希尔排序 : $O(nlo{g}_{2}n)～O(n^2)$ $O(n^{1.3})$ $O(n^2)$ $O(1)$

冒泡排序: $O(n^2)$ $O(n)$ $O(n^2)$ ???????????? ? ?? ??$O(1)$

快速排序:????????? ???$O(nlo{g}_{2}n)$ ?????????????????$O(nlo{g}_{2}n)$ ???????$O(n^2)$ ?$O(nlo{g}_{2}n)～O(n)$

简单选择排序: $O(n^2)$ ???????????????????????????$O(n^2)$ ??????????? ?$O(n^2)$ ???????????? ?? ??$O(1)$

堆排序:????????????????$O(nlo{g}_{2}n)$ ?????????????????$O(nlo{g}_{2}n)$ ????????$O(nlo{g}_{2}n)$ ??????? ?$O(1)$

归并排序: ???????????$O(nlo{g}_{2}n)$ ?????????????????$O(nlo{g}_{2}n)$ ????????$O(nlo{g}_{2}n)$ ???? ????$O(n)$

分类讨论算法

从平均情况来看 ,
 直接插入排序, 简单选择排序, 冒泡排序 : O(n^2)
 堆排序, 快速排序, 堆排序 : O(nlogn)
 希尔排序 : O(nlogn) ~ O(n^2)

从空间复杂度看 :
    归并排序 : O(n)
    快速排序 : O(nlogn) ~ O(n)
    其余 : O(1)

从稳定性看 :
    稳定的 : 直接插入排序, 冒泡排序, 归并排序
    不稳定的 : 快速排序, 简单选择排序, 希尔排序, 堆排序

性质

在一趟排序结束后 ， 就选出一个元素在其最终位置上的排序算法 ？

可以的 : 简单选择排序 , 快速排序 , 冒泡排序 , 堆排序

不可以的 : 插入排序 , 希尔排序 , 二路归并排序