10种排序算法基础总结

Java基础

浏览数:32

2019-10-8

基于比较的排序:

  基础排序:

      冒泡排序:谁大谁上,每一轮都把最大的顶到天花板 效率太低——掌握swap。

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

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

    希尔排序(缩小增量排序):是插排的改良,对空间思维训练有帮助 时间复杂度O(n1.3),介于O(nlgn)~O(n2)之间

  分治法:

    快速排序:是软件工业中最常见的常规排序法,其双向指针扫描和分区算法是核心,特别地partition算法用来划分不同性质的元素,如选择第K大元素的问题。快速排序时间复杂度为O(NlgN),但是如果主元不是中位数的话,特别地如果每次主元都在数组区间的一侧,复杂度将退化为N²,工业上的优化方法见快速排序分区以及优化方法。快速排序重视子问题的划分。

    归并排序:分治法的完美使用,开辟了辅助空间,常见的题目如逆序对数,归并排序重视子问题的解的合并

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

    上面三个都是NlgN的复杂度,其中快排表现最好,是原址的不用开辟辅助空间;归并排序需要开辟辅助空间;堆排也是原址的,但是常数因子较大,不具备优势。

基于非比较排序:

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

  桶排序:用它解决问题必须注意序列的值是否均匀地分布在桶中。如果不均匀,那么个别桶中的元素会远多于其他桶,桶内排序用比较排序,极端情况下,全部元素在一个桶内,那么复杂度还是会退化成NlgN。

  基数排序:kN级别(k是最大数的位数)是整数数值型排序里面又快又稳的,无论元素分布如何,只开辟固定的辅助空间(10个桶),基数排序几乎不需要任何“比较”操作。因此,在实际应用中,对十进制整数来说,基数排序更好用。

  上面三种排序其实都是支持负数的,我们可以找出最小的数来,计算出与0的距离,然后把所有的数同时减去这个距离,这样就全部成为自然数,排好序然后再恢复回去就OK了。

十种排序算法对比:

  

 

作者:|旧市拾荒|