技术中心

这里象征着我们的态度和能力

>Java实现的几个常用排序算法
作者:中国IT实验室    来源:中国IT实验室    发布时间:2012-09-14      浏览次数:11002
分享到:
欢迎进入Java社区论坛,与200万技术人员互动交流 >>进入
    排序算法应用性很广泛,近期自己总结了一下他的作用,并自己简单地实现了一遍,特此记录下来,为以后复习留点材料。下面逐一看看经典的排序算法:
   
    1. 插入排序
   
    插入排序的基本思想是在遍历数组的过程中,假设在序号i 之前的元素即[0i-1] 都已经排好序,本趟需要找到i 对应的元素x 的正确位置k ,并且在寻找这个位置k 的过程中逐个将比较过的元素往后移一位,为元素x "腾位置",最后将k 对应的元素值赋为x ,插入排序也是根据排序的特性来命名的。
   
    以下是一个实例,红色 标记的数字为插入的数字,被划掉的数字是未参与此次排序的元素,红色 标记的数字与被划掉数字之间的元素为逐个向后移动的元素,比如第二趟参与排序的元素为[11, 31, 12] ,需要插入的元素为12 ,但是12 当前并没有处于正确的位置,于是我们需要依次与前面的元素31 、11 做比较,一边比较一边移动比较过的元素,直到找到第一个比12 小的元素11 时停止比较,此时31 对应的索引1 则是12 需要插入的位置。
   
    初始:    [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
   
    第一趟:[11, 31 , 12, 5, 34, 30, 26, 38, 36, 18] (无移动的元素)
   
    第二趟:[11, 12 , 31, 5, 34, 30, 26, 38, 36, 18] (31 向后移动)
   
    第三趟:[5 , 11, 12, 31, 34, 30, 26, 38, 36, 18] (11, 12, 31 皆向后移动)
   
    第四趟:[5, 11, 12, 31, 34 , 30, 26, 38, 36, 18] (无移动的元素)
   
    第五趟:[5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] (31, 34 向后移动)
   
    第六趟:[5, 11, 12, 26 , 30, 31, 34, 38, 36, 18] (30, 31, 34 向后移动)
   
    第七趟:[5, 11, 12, 26, 30, 31, 34, 38 , 36, 18] (无移动的元素)
   
    第八趟:[5, 11, 12, 26, 30, 31, 34, 36 , 38, 18] (38 向后移动)
   
    第九趟:[5, 11, 12, 18 , 26, 30, 31, 34, 36, 38] (26, 30, 31, 34, 36, 38 向后移动)
   
    插入排序会优于选择排序,理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势,有效地减少一些比较的次数,当然这种优势得看数组的初始顺序如何,最坏的情况下(给定的数组恰好为倒序)插入排序需要比较和移动的次数将会等于1 + 2 + 3…+ n = n * (n + 1) / 2 ,这种极端情况下,插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法,插入效率与数组初始顺序息息相关。一般情况下,插入排序的时间复杂度和空间复杂度分别为O(n2 ) 和O(1) .
   
    2. 希尔排序
   
    希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组"分而治之",划分为若干个小的数组,以gap 来划分,比如数组[1, 2, 3, 4, 5, 6, 7, 8] ,如果以gap = 2 来划分,可以分为[1, 3, 5, 7] 和[2, 4, 6, 8] 两个数组(对应的,如gap = 3 ,则划分的数组为:[1, 4, 7] 、[2, 5, 8] 、[3, 6] )然后分别对划分出来的数组进行插入排序,待各个子数组排序完毕之后再减小gap 值重复进行之前的步骤,直至gap = 1 ,即对整个数组进行插入排序,此时的数组已经基本上快排好序了,所以需要移动的元素会很小很小,解决了插入排序在处理大规模数组时较多移动次数的问题。希尔排序是插入排序的改进版,在数据量大的时候对效率的提升帮助很大,数据量小的时候建议直接使用插入排序就好了。

[1] [2] 下一页

4000-880-989
(24小时热线)
联系客服
微信公众号

官方公众号

小程序

©2008-2022 CORPORATION ALL Rights Reserved. 昆明奥远科技有限公司版权所有 滇ICP备09003328号-1 滇公网安备 53011102000818号 增值电信业务经营许可证号:滇B2-20110045
昆明那家网络公司好,新媒体运营,网站优化,网络推广,网站建设,网页设计,网站设计,网站推广,云南网站公司,昆明新媒体公司,云南网红主播,昆明SEO公司,昆明网站建设,昆明网络推广,昆明网站优化,昆明网站推广,红河网站建设,大理网络公司,曲靖网络公司,丽江网站设计,昭通网络公司,保山大数据服务,智慧高速建设,智慧校园服务,云南IDC服务商,网络安全测评,等保测评,网站关键词排名优化服务,服务客户尽超2000余家,一切尽在奥远科技,服务电话:13888956730