https://blog.csdn.net/weixin_41317985/article/details/79461929
1.比较排序
A.冒泡排序
最佳情况：T(n) = O(n)最差情况：T(n) = O(n2)平均情况：T(n) = O(n2)B.选择排序
最佳情况：T(n) = O(n2)最差情况：T(n) = O(n2)平均情况：T(n) = O(n2)C.插入排序
最佳情况：输入数组按升序排列。T(n) = O(n)最坏情况：输入数组按降序排列。T(n) = O(n2)平均情况：T(n) = O(n2)D.希尔排序
最佳情况：T(n) = O(nlog2 n)最坏情况：T(n) = O(nlog2 n)平均情况：T(n) =O(nlog n)E.归并排序
最佳情况：T(n) = O(n)最差情况：T(n) = O(nlogn)平均情况：T(n) = O(nlogn)F.快速排序
最佳情况：T(n) = O(nlogn)最差情况：T(n) = O(n2)平均情况：T(n) = O(nlogn)G.堆排序
最佳情况：T(n) = O(nlogn)最差情况：T(n) = O(nlogn)平均情况：T(n) = O(nlogn)可以看出比较排序在大数据量的情况排名：
时间排序上来看： 1.归并排序 2.堆排序 3.快速排序
但归并排序需要开辟额外的空间去储存正在调整排序的数组
如果对于空间和时间都有要求，建议使用快速和堆排序
归并排序思路（递归）：
[2,1,4,3,9,6,5,8] 第一步分割数组
[2,1,4,3] [9,6,5,8] [2,1][4,3] [9,6][5,8]=>直到每个数组都不能再分割 第二步排序最底部子数组开始排序然后合并数组，顺序如下 [2,1] =>[1,2] [2,1][4,3] =>[1,2,3,4] [9,6] =>[6,9] [5,8] =>[5,8] [9,6][5,8] =>[5,6,8,9] [2,1][4,3] [9,6][5,8] =>[1,2,3,4,5,6,8,9]
2.非比较排序
对于大量的数据速度并不一定比比较排序快
A.计数排序
最佳情况：T(n) = O(n+k)最差情况：T(n) = O(n+k)平均情况：T(n) = O(n+k)要求：必须是整数，且给出接受数组为排序数组的最小到最大的范围如，排序数组是1-9，则参考数组必须要1-9
速度快于任何比较排序，但面临数量大的数组，会占有大量内存和时间
B.桶排序
最佳情况：T(n) = O(n+k)最差情况：T(n) = O(n+k)平均情况：T(n) = O(n2)说明：桶排序简单来说是计数排序的参考数组的优化，缩小参考数组聚集成为桶，然后对桶再排序，再合并桶数组为结果
如[1,2,3,4,5,6,7,8,9] =>[1,2,3]+ [4,5,6]+[7,8,9]
C.基数排序
最佳情况：T(n) = O(n * k)最差情况：T(n) = O(n * k)平均情况：T(n) = O(n * k)说明：依据于数字的位数上的数字大小放到桶里，再拿出来合并为新排序数组，从地位到高位如： 下图所示