软设之排序算法对比

直接插入 

时间复杂度:平均情况为O(n^2)。特殊情况下基本有序最优为O(n)

空间复杂度:O(1)

希尔排序

时间复杂度:平均情况O(n^1.3)

空间复杂度:O(1)

直接选择排序

时间复杂度:O(n^2)

空间复杂度:O(1)

堆排序

时间复杂度:O(nlog(2)n)

空间复杂度:O(1)

冒泡排序

时间复杂度:平均情况O(n^2)

空间复杂度:O(1)

快速排序

时间复杂度:平均情况O(nlog(2)n)，基本有序最差是O(n^2)

空间复杂度:O(1)

归并排序

时间复杂度 O(nlog(2)n)

空间复杂度O(n)

基数排序

时间复杂度:O(d(n+rd))

空间复杂度:O(rd)

排序算法选择

如果数据元素数目n比较小，可采用直接插入排序和简单选择排序

如果要排列记录基本有序，可以采用直接插入排序或冒泡排序

如果数据数目很大，应采用时间复杂度为O(nlog(2)n)的排序方法。

快速排序目前被认为是内部排序中最好的方法，如果待排序的关键字为随机分布，快速排序的平均运行时间最短

堆排序只需要一个辅助空间，并且不会出现在快速排序中可能出现的最快情况

快速排序和堆排序都是不稳定的排序方法，如果追求排序稳定，可选择归并排序。