|
1、冒泡排序
n-1趟每趟两两比较最大的放右边
O(n2) 最佳情况：O(n)（上一次不交换就结束）
2、选择排序
左边为有序区，每趟选最小索引放有序区右边，n-1趟
O(n2)
3、插入排序
一个个插到左边有序区，插入要挪
O(n2) 最佳情况：O(n)不用挪
4、希尔排序
间距gap为一组，gap不停/2到1，每个gap为一趟进行插排
O(nlogn)：用了分治，复杂度很难证明
5、归并排序
每个数组分两半一直分直到数组长度小于2后两两按序合并（二路归并）相当于二叉树每层都要O(n)（merge）
证明：T(n)=2T(n/2)+n/2(最优)递归到2*k=n
O(nlogn)
6、快速排序
partion算法：选个支点，双指针使支点左边不大于右边，O(n)
对左右两边继续用
二叉树
O(nlogn) 最坏是O(n2)：n-1次递归
7、堆排序
建堆：用调整算法从最后一个非叶往前，O(n)
取最大
调整堆：一直往下子大的换父，递归，O(nlogn)
https://blog.csdn.net/qq_34228570/article/details/80024306
O(nlogn)
8、
|