十大排序算法

Posted by 帝八哥 on February 21, 2019

十大排序算法

– JAVA之10大排序算法

  • 知识范围

    1. 冒泡排序
    2. 快速排序
    3. 归并排序
    4. 插入排序
    5. 希尔排序
    6. 选择排序(后续补充)
    7. 堆排序(后续补充)
    8. 计数排序(后续补充)
    9. 桶排序(后续补充)
    10. 基数排序(后续补充)

    高能预警,动画来袭

  • 核心原理

    1. 冒泡排序

      从头遍历数组, 相邻元素比较

      前面元素比后面元素大(或小), 则交换这两个元素, 得到本次遍历的最后位置为最大(或最小)元素

      冒泡排序图示

    2. 快速排序

      分治法将一个数组分为两个子数组

      从数组中选择一个元素, 作为本数组(子数组)的基准

      遍历本数组(子数组), 将小于基准元素的值交换到基准前面, 大于基准元素的值交换到后面

      递归上面得到的2个子数组, 得到排序结果

      快速排序图示

    3. 归并排序

      分治法

      将长度为n的数组分为两个长度为n/2的子序列

      对这两个子序列分别采用归并排序

      将两个排序好的子序列合并成最终排序序列

      归并排序图示

    4. 插入排序

      对于未排序序列,将其与已排序元素从后往前(从前往后)扫描的元素作比较, 满足大于(小于)条件时插入

      从第一个元素开始, 该元素认为已经排序

      取下一个元素, 与已经排序好的排序元素从后往前扫描做比较

      若该元素大于排序元素, 将该元素移到下一位置

      重复比较直到找到已排序的元素大于(或小于)等于该元素, 将该元素插入该位置

      插入排序图示

    5. 希尔排序

      优先比较较远位置的元素.

      选择一个增量序列: t_1, t_2, …, t_k, 其中t_i > t_j, t_k=1;

      按照增量序列的个数, k个, 对序列进行k趟排序;

      每趟排序中, 根据对应的增量t_i, 将待排序序列分割成若干长度为m的子序列

      分别对各字表进行直接插入排序

      当且仅当增量为1时, 整个序列作为一个整表排序处理

      希尔排序图示

  • 经验探秘

    排序方法 平均时间复杂度 最优时间复杂度 最差时间复杂度 空间复杂度 稳定性
    冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
    快速排序 O(nLog_2_^n) O(nLog_2_^n) O(n^2) O(nLog_2_^n) 不稳定
    归并排序 O(nLog_2_^n) O(nLog_2_^n) O(nLog_2_^n) O(n) 稳定
    插入排序 O(n^2) O(n) O(n^2) O(1) 稳定
    希尔排序 O(n^m), m∈[1, 2) O(n) O(n^2) O(1) 不稳定
  • 总结输出

    1. 冒泡排序: 可以优化, 设置交换操作的标志, 当未发生交换时, 说明后续元素已经有序, 那么退出当前循环

      比较相邻元素,将大的元素放后边,小的放前边,每一轮比较,总有一个最大元素被冒到数组最后边。N轮比较下来,就完成了排序
      

      应用场景: 数据基本有序, 且数据量较小

    2. 快速排序: 通常是实际应用中的最好选择排序算法

      快速排序算法每次选择一个基准元素,将小于基准元素的数放到左边,大于基准元素的数放到右边,递归的重复这个划分过程,直到需要划分的数组中只有一个元素,结束递归。
      

      应用场景: 处理大量数据排序

    3. 归并排序: 由于使用递归,递归深度太深容易造成内存溢出,所以可使用非递归版本归并排序

      归并排序在结构上是递归的,归并排序每一次递归将原数组均分为规模较小的两个部分,直到无法再分为止,此时每一个部分只有一个元素,那么自然是有序的,于是递归开始自下往上进行合并; 
      合并时,新建一个数组,长度等于两个子数组长度之和,依次比较两个子数组中的元素,每次将较小的元素放进新数组即可; 
      对于归并排序,每一层递归将原数组均分成了两部分,于是递归树一共log_2_^n+1层,每一层最多进行n次比较,所以时间复杂度为nlog_2_^n。
      
      

      应用场景: 数据量较大且要求排序稳定

    4. 插入排序: 基本思想类似于我们抓扑克牌

      开始时,我们的左手为空,然后我们每次从牌堆中拿走一张牌并插入到正确的位置;为了找到每一张牌的正确位置,需要将它从右到左与每一张牌比较,直到找到小于它的那张牌,保证左手的牌随时都是有序的,同样N轮插入操作下来,数组有序。
      

      **应用场景: **数据基本有序且规模较小时,选用插入排序较好

    5. 希尔排序: 对插入排序的一种改进, 改进思想源于序列越基本有序,插入排序效率越高

      先将整个待排记录序列分割成若干列,即若干子序列,分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。
      

      应用场景: 数据基本有序且规模较小

总结

  • 捐赠|Donate, 实践撰文分享实属不易, 您的支持能为更多省时省事的分享提速, 谢谢!

微信


支付宝


MiXin