千锋教育-做有情怀、有良心、有品质的IT职业教育机构

400-811-9990
当前位置:首页 > 关于学院 > 技术论坛  >  正文

Java技术学习之快速掌握八种基本排序

时间:2018-05-29 11:05:51     来源:千锋教育 作者:千锋老师

  在学习java技术时候,对于排序的应用需要熟练的掌握,这样才能够确保Java学习时候能够有扎实的基础能力。

  经典的排序算法有八种,分别为:

  Ø 冒泡排序

  Ø 选择排序

  Ø 插入排序

  Ø 归并排序

  Ø 希尔排序

  Ø 快速排序

  Ø 堆排序

  Ø 基数排序

  其中冒泡排序、选择排序、插入排序称为三大基本排序。

  虽然这三大基本排序算法时间复杂度都是O(n2),但是其实细细讨论之下,还是有各自的特点的。

  冒泡排序

  冒泡排序法的思路

  基本思路:

  假设我们需要进行升序排列

  进行N轮的比较,每一轮将相邻的两个元素依次比较,根据大小进行交换,每轮比较结束后,将最大的元素依次‘冒’到数组的末尾,经过几轮比较后,数组就会呈现有序的状态。

  图解:

  假设对5个元素进行冒牌排序,先准备5个随机元素:

<a href=http://www.mobiletrain.org/ target=_blank class=infotextkey>Java培训</a>.png

  1)第一轮中,将第一个元素(10)与相邻的元素(20)进行比较,因为20比10大所以无需进行交换。再将第二个元素(20)与相邻的元素(5)比较,因为20比5大,所以需要往上‘冒’,因此需要与5进行交换

<a href=http://www.mobiletrain.org/ target=_blank class=infotextkey>Java培训</a>.png

  接着将第三个元素(20)与相邻的元素进行比较,这样经过与14和1的比较之后,因为20最大,所以被冒到了最后的位置

<a href=http://www.mobiletrain.org/ target=_blank class=infotextkey>Java培训</a>.png

  2)后面每轮都按照此方法进行比较,但是需要注意,此后的每一轮都需要比前一轮少比较一次,因为前面已经确定了最大元素的位置,为了提高性能,可以不用再和后面确定了位置的元素进行比较。

  3)由此可以确定,当数组的长度为N时,需要比较的轮数为N-1轮。每轮中从第一个元素开始相邻元素两两进行比较,第一轮需要比较N-1次,第2轮需要比较N-2次,依次类推,实现整体排序

  冒泡排序法的代码实现

<a href=http://www.mobiletrain.org/ target=_blank class=infotextkey>Java培训</a>.png

  Ø 首先通过一个外层的for循环确定比较的轮数,循环元素数量-1轮。

  Ø 内部通过一个for循环实现每轮的两两元素比较的效果。每轮需要比较的次数都会比上一轮减少一次,通过j

  Ø 元素两两比较通过array[j] > array[j+1]来实现。

  冒泡排序法优化

  以上的冒泡排序法还有优化的空间。因为如果一个数组已经是完全有序的情况下,冒泡排序法仍然会进行逐轮的比较,这无疑是浪费性能的行为。因此我们可以确定,当冒泡的比较中,有一轮如果没有发生交换,则可以确定当前数组已经完全有序,后面的轮数完全不必在进行。故做以下的调整:

<a href=http://www.mobiletrain.org/ target=_blank class=infotextkey>Java培训</a>.png

  通过定义一个标识符isSort,如果有一轮没有发生任何交换,则isSort就会为true,下次直接break,后面的轮数就不用再进行比较了。

  选择排序

  选择排序的思路

  基本思路:

  选择排序和冒泡排序不同,选择排序会通过一轮比较,选出最小的那个元素的下标,然后和第一个元素进行交换,这样第一个元素的位置就可以确定了。

  第二轮如法炮制,从第二个元素开始依次比较,选出最小的元素的下标,和第二个元素交换位置,这样第二小的元素位置就确定了。

  后面依次类推,直到整个数组呈现有序状态。

  选择排序法的代码实现

<a href=http://www.mobiletrain.org/ target=_blank class=infotextkey>Java培训</a>.png

  Ø 选择排序比较的轮数和冒泡排序比较的轮数是一样的

  Ø K表示当前最小值的下标,当前是第几轮,k就先代表第几个元素的下标,然后依次和后面的元素进行比较,如果发现比k位置元素小的元素时,改变k的下标,这样一轮过后k代表的位置就是本轮最小的元素,和i进行交换即可

  Ø 如果一轮过后k==i,则说明i本来就是最小的元素,则无需交换提高性能。

  插入排序

  插入排序的思路

  基本思路

  假设一个数组已经基本有序,则这个时候插入排序就是一个不错的选择。插入排序是先保证左边元素是基本有序的,然后将后面的元素依次和左边元素进行比较,如果比较到一个比自己小的元素时就可以停止比较了,因为左边已经呈现有序状态,找到比自己小的元素时,就不用再往后比较了。

  插入排序的代码实现

<a href=http://www.mobiletrain.org/ target=_blank class=infotextkey>Java培训</a>.png

  Ø 插入排序的轮数和冒泡排序一样,但是i从1开始,因为我们假设第一个元素已经是呈现有序状态了。

  Ø 内部循环依次从当前位置开始,和前面元素进行比较,如果找到了比自己小的元素,则停止比较,直接退出本轮比较,进行下一轮比较

  总结

  Ø 虽然三种排序法的时间复杂度都是O(N2),但是不同的场景还是会有不同的性能差异。

  Ø 冒泡排序法是性能最差的算法,正式运用中,基本不会用冒泡排序法进行排序。

  Ø 选择排序将交换次数降到最低,但是比较次数仍然很大。当数据量小,并且交换耗时相对于比较耗时更多的情况下,选择排序是个不错的选择。

  Ø 基本有序的情况下,插入排序是最好的选择,但是如果数据基本逆序的情况下,插入排序的性能和冒泡排序就基本一样了。

  Ø 从平均情况下来看,插入排序性能会比选择排序略好一些。

  千锋Java培训作为中国IT研发人才一体化服务的开拓者,为学生制定合理有序的学习计划,0学费入学,2周免费试听不满意不收费,与学员签订就业协议,坚持良心面授,从千锋Java培训班出去的学员均已高薪就业。千锋推出的免费java视频教程,让学员能够方面的巩固基础技术能力。

相关文章

  • 北京天丰利校区(总部)地址:北京市海淀区宝盛北里西区28号天丰利商城4层
    北京沙河校区:北京市昌平区沙阳路18号北京科技职业技术学院广场服务楼2、3层
    咨询电话:400-811-9990
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训、好程序员
  • 深圳西部硅谷校区地址:深圳市宝安区宝安大道5010号深圳西部硅谷B座A区605-619
    深圳大学城校区地址:深圳市南山区留仙大道1201号大学城创客小镇16栋3楼
    咨询电话: 0755-23015275/23015546-801(硅谷) 0755-86660670-801(大学城)
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训、好程序员
  • 上海校区地址:上海市宝山区同济支路199号智慧七立方3号楼2-4层
    咨询电话:400-811-9990 021-65233829-609
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训、好程序员
  • 郑州校区地址:郑州市二七区航海中路60号海为科技园C区10层、12层
    咨询电话:0371-55191750
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 广州校区地址:广州市天河区元岗路310号智汇park创意园E座5层
    咨询电话:020-22119207
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 大连校区地址:辽宁省大连市高新园区爱贤街10号大连设计城A座901
    咨询电话:400-811-9990
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 武汉金融港校区地址:武汉市东湖高新技术开发区光谷大道77号金融港B18栋3楼
    武汉智慧园校区地址:武汉市东湖高新技术开发区光谷大道61号智慧园21栋2楼
    咨询电话:027-59313371
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 成都校区地址:成都市武侯区科华北路62号力宝大厦N(北楼)18楼
    咨询电话:400-811-9990 028-83178771
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 西安校区地址:西安市雁塔区高新六路52号立人科技C座西区4楼
    咨询电话:029-85363390
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 杭州校区地址:浙江省杭州市江干区九堡旺田书画城A座4层
    咨询电话:400-811-9990 0571-86893632
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 青岛校区地址:青岛市市北区龙城路卓越世纪中心3号楼8层801
    咨询电话:0532-80911190
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 重庆校区地址:重庆市高新区科园一路2号大西洋国际12-1
    咨询电话:400-811-9990 023-68883009
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 长沙校区地址:湖南省长沙市岳麓区麓谷企业广场A2栋三单元306号
    咨询电话:0731-85513210
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 哈尔滨校区地址:哈尔滨市松北区创新一路699号 科技创新城19号楼B座五楼
    咨询电话:400-811-9990/0451-87173191
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 南京校区地址:南京市建邺区应天大街780号应天智汇产业园弘辉园1幢2楼
    咨询电话:400-811-9990
    面授课程:HTML5大前端培训、全链路UI/UE设计培训、PHP全栈+服务器集群培训、JavaEE+分布式开发培训、大数据+人工智能培训、 Unity游戏开发培训、Python培训、云计算+信息安全培训、全栈软件测试培训、智能物联网+嵌入式培训、Android培训、iOS培训
  • 千锋教育服务号

    了解千锋动态
    关注千锋教育服务号

  • 千锋教育移动站

    扫一扫快速进入
    千锋移动端页面

  • 千锋互联服务号

    扫码匿名提建议
    直达CEO信箱