直接插入
时间复杂度:平均情况为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)的排序方法。
快速排序目前被认为是内部排序中最好的方法,如果待排序的关键字为随机分布,快速排序的平均运行时间最短
堆排序只需要一个辅助空间,并且不会出现在快速排序中可能出现的最快情况
快速排序和堆排序都是不稳定的排序方法,如果追求排序稳定,可选择归并排序。