10种排序算法对比分析

1. 冒泡排序:

效率太低,通过冒泡可以掌握swap。

2. 选择排序:

效率较低,但经常使用它内部的循环方式来找最大值和最小值。

3. 插入排序:

虽然平均效率低,但在序列基本有序时,它很快,所以也有其适用范围。

4. 希尔排序:

是插入排序的改良,对空间思维训练有帮助。

5. 快速排序:

快排是软件工业中最常见的常规排序法,其双向指针扫描和分区算法是核心。

往往用于解决类似问题,特别地partition算法用来划分不同性质的元素, partition->selectK,也用于著名的top问题 O(NlgN),但是如果主元不是中位数的话,特别地如果每次主元都在数组区间的一侧,复杂度将退化为N² 工业优化:三点取中法,绝对中值法,小数据量用插入排序 快排重视子问题拆分

6. 归并排序:

空间换时间——逆序对数,

归并重视子问题的解的合并

7. 堆排序:

用到了二叉堆数据结构,是继续掌握树结构的起手式。=插排+二分查找

上面7种都是基于比较的排序,可证明它们在元素随机顺序情况下最好是NlgN的,用决策树证明

下面三个是非比较排序,在特定情况下会比基于比较的排序要快:

8. 计数排序:

可以说是最快的:O(N+k),k=maxOf(sourceArr),用它来解决问题时必须注意如果序列中的值分布非常广(最大值很大,元素分布很稀疏), 空间将会浪费很多 所以计数排序的适用范围是:序列的关键字比较集中,已知边界,且边界较小

9. 桶排序:

先分桶,再用其他排序方法对桶内元素排序,按桶的编号依次检出。(分配-收集) 用它解决问题必须注意序列的值是否均匀地分布在桶中。 如果不均匀,那么个别桶中的元素会远多于其他桶,桶内排序用比较排序,极端情况下,全部元素在一个桶内,还是会退化成NlgN。

其时间复杂度是:时间复杂度: O(N+C),其中C=N(logN-logM),约等于NlgN N是元素个数,M是桶的个数。

10. 基数排序:

kN级别(k是最大数的位数)是整数数值型排序里面又快又稳的,无论元素分布如何, 只开辟固定的辅助空间(10个桶)

对比桶排序,基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作,而桶排序在桶相对较少的情况下,桶内多个数据必须进行基于比较操作的排序。因此,在实际应用中,对十进制整数来说,基数排序更好用。

算法复杂度对比:

alt

alt

参考

十大排序算法总结

十大排序算法总结