025-86901720


全国监督服务热线:9:00-23:00

海量精品课程
点击免费试听

  • Java四种常见排序算法及其使用场景

  • 分类: 合肥学码思 > java教程 时间:2018年12月24日
  • 摘要:冒泡排序是比较简单的排序之一了,其大体思想就是通过与相邻元素的比较和交换来把小的数交换到前面。这个过程类似于水泡向上升一样,因此而得名。

  • 排序算法在很多领域都到运用和重视,尤其是在大量的数据处理这一方面。好的算法可以节省大量的资源,下面合肥学码思的老师就和大家说下Java四种常见排序算法以及其使用场景。

    Java四种常见排序算法及其使用场景

     

      冒泡排序

     

      冒泡排序是比较简单的排序之一了,其大体思想就是通过与相邻元素的比较和交换来把小的数交换到前面。这个过程类似于水泡向上升一样,因此而得名。>>初学者学习Java的零基础学习路线分享


      举个例子,对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡,4和6比较,把4交换到前面,序列变成5,3,8,4,6。

     

      同理4和8交换,变成5,3,4,8,6,3和4无需交换。5和3交换,变成3,5,4,8,6,3.这样一次冒泡就完了,把比较小的数3排到前面了。

     

      对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)

    Java四种常见排序算法及其使用场景

     

      选择排序

     

      选择排序的思想其实和冒泡排序有点类似,都是在一次排序后把比较小的元素放到前面,但是过程不同,冒泡排序是通过相邻的比较和交换,而选择排序是通过对整体的选择。

     

      举个例子,对5,3,8,6,4这个无序序列进行简单选择排序,首先要选择5以外的比较小数来和5交换,也就是选择35交换,一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换,这样就会得到一个有序序列。

     

      其实选择排序可以看成冒泡排序的优化,因为其目的相同,只是选择排序只有在确定了比较小数的前提下才进行交换,大大减少了交换的次数。选择排序的时间复杂度为O(n^2)

    Java四种常见排序算法及其使用场景

     

      快速排序

     

      快速排序一听名字就觉得很高端,在实际应用当中快速排序确实也是表现非常好的排序算法。冒泡排序虽然高端,但其实其思想是来自冒泡排序,冒泡排序是通过相邻元素的比较和交换把比较小的冒泡到顶端,而快速排序是比较和交换小数和大数,这样一来不仅把小数冒泡到上面同时也把大数沉到下面。

     

      举个例子:对5,3,8,6,4这个无序序列进行快速排序,思路是右指针找比基准数小的,左指针找比基准数大的,交换之。

     

      5,3,8,6,4用5作为比较的基准,会把5小的移动到5的左边,比5大的移动到5的右边。

     

      5,3,8,6,4首先设置i,j两个指针分别指向两端,j指针先扫描(思考一下为什么?)4比5小停止。然后i扫描,8比5大停止。交换i,j位置。

     

      5,3,4,6,8然后j指针再扫描,这时j扫描4时两指针相遇。停止。然后交换4和基准数。

     

      4,3,5,6,8一次划分后达到了左边比5小,右边比5大的目的。之后对左右子序列递归排序,这样就得到有序序列。

     

      上面留下来了一个问题为什么一定要j指针先动呢?首先这也不是绝对的,这取决于基准数的位置,因为在后面两个指针相遇的时候,要交换基准数到相遇的位置。一般选取第一个数作为基准数,那么就是在左边,所以后面相遇的数要和基准数交换,那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。

     

      快速排序是不稳定的,其时间平均时间复杂度是O(nlgn)

    Java四种常见排序算法及其使用场景

    Java四种常见排序算法及其使用场景



     

      其实上面的代码还可以再优化,上面代码中基准数已经在pivotKey中保存了,所以不需要每次交换都设置一个temp变量,在交换左右指针的时候只需要先后覆盖就可以了。

     

      这样既能减少空间的使用还能降低赋值运算的次数。优化代码如下:

     

      插入排序

     

      插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历,特别是牌数较大的。

     

      在分牌时可能要整理自己的牌,牌多的时候怎么整理呢?就是拿到一张牌,找到一个合适的位置插入。这个原理其实和插入排序是一样的。

     

      举个例子,对5,3,8,6,4这个无序序列进行简单插入排序,首先假设第一个数的位置时正确的,想一下在拿到第一张牌的时候,没必要整理。

     

      然后3要插到5前面,把5后移一位,变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动,6插在8前面,8后移一位,4插在5前面,从5开始都向后移一位。

     

      注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)

    Java四种常见排序算法及其使用场景

     

      以上是合肥学码思关于Java四种常见排序算法及其使用场景,希望对大家的Java学习有所帮助,如果你在Java的学习过程中还有其他疑问或者问题,欢迎大家进一步咨询合肥学码思的老师。


  • 初学者学习Java的零基础学习路线分享
    Java的主要特性有哪些?

申请试听 | 学费咨询 | 在线报名 | 申请补贴 | 软件培训 | 网站地图

2016-2020 南京学码思教育科技有限公司 .All Rights Reserved

苏ICP备16033487号 www.hfxms.com.cn

全国热线

400-080-3312

全国监督服务热线:9:00-23:00