1.排序的时间复杂度(均为平均值)
O(n^2) :冒泡排序,选择排序,插入排序。
O(n * log(n)):堆排序,快速排序,归并排序。
O(n^1.3):希尔排序
2.空间复杂度:
O(n) :
归并排序
O(log(n)) ~ O(n):快速排序
O(1) :冒泡排序,选择排序,插入排序,
堆排序,
希尔排序
3.使用思想分类
1.插入:直接插入排序,希尔排序
2.分治:快速排序,归并排序
3. 选择:选择排序,冒泡排序,堆排序
4.稳定性分类
1.稳定:归并排序,冒泡排序,插入排序
2.不稳定:希尔排序,选择排序,快速排序,堆排序
5.适用场合
归并排序:要求稳定又相对较快
冒泡排序:简单
插入排序 希尔排序:本身就是相对有序的数组
选择排序:很少用
快速排序:快
堆排序:优于选择,较快
附具体时间复杂度: