• 135456

    文章

  • 827

    评论

  • 13

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

排序算法 --- 希尔排序

2年想跳槽阿里,大咖揭秘大厂面试的那些事儿 >>

一、排序思想

之前说到插入排序,希尔排序就对其进行了一个优化,优化的思路是:

  • 对待排序列进行分组,组数为 gap = arr.length / 2
  • 对每一组进行插入排序,然后再进行分组, gap = gap / 2
  • 再对每一组进行插入排序,直到最后组数为1,再进行最后一次插入排序即可;

案例:

假如有待排序列如下:

8  9  1  7  2  3   5  4  6  0
  • 总共10个数, gap = 10 / 2 = 5,分成5组,并且不是两两相邻的为一组, arr[0]arr[0 + gap]为一组, arr[1]arr[1 + gap]为一组……第一次分组后的结果如下(数字后面带的符号相同的为同一组):
8*    9$    1@    7^    2&    3*     5$    4@    6^    0&

对这五组都进行插入排序,结果就是:

3*    5$    1@    6^    0&    8*     9$    4@    7^    2&
  • 对上面的序列再进行分组, gap = gap / 2 = 5 / 2 = 2,再分成两组, arr[0]arr[0+2]arr[0+2+2]……为一组,分组结果就是:
3*    5$    1*    6$    0*    8$     9*    4$    7*    2$

对这两组分别进行插入排序,结果就是:

0*    2$    1*    4$    3*    5$     7*    6$    8*    9$
  • 此时, gap = gap / 2 = 2 / 2 = 1,组数为1,所以不用分了,对这一组再进行插入排序,那么整个排序过程就完了。

二、代码实现

关于希尔的代码实现,网上很多花里胡哨的答案,什么交换法位移法之类的,其实不要想得那么复杂。刚才说了,希尔排序的主要思想就是分组,对每一组分别进行插入排序,那代码就简单了,就是这分组里面将之前插入排序的代码拷过来稍微改改就行了。分组的代码就是:

for(int gap = arr.length / 2; gap > 0; gap /= 2) {
    ……
}

这个for循环里面就直接把之前插入排序的代码粘过来,稍微改改就行,以前插入排序的代码是这样的:

for(int i=1; i<arr.length; i++) { // 默认第一个是有序表,从第二个元素开始进行插入排序
 int insertVal = arr[i]; // 待排元素
 int insertIndex = i - 1; // 从有序表最后一个元素开始比较
 while (insertIndex >= 0 && insertVal < arr[insertIndex]) { // 如果还没有将有序表比较完 && 待排元素还没找到位置
  arr[insertIndex + 1] = arr[insertIndex]; // 比待排元素大的元素后移一位
  insertIndex --; // 继续往前比较
 }
 // 找到位置后,其他元素都后移了,自己占坑
 if (insertIndex + 1 != i) {
  arr[insertIndex + 1] = insertVal;
 }
}

怎么改呢?聪明的你肯定发现了,以前只有一组,每次比较的时候,步长是1,现在步长是gap,所以,只要将以前插入排序循环中的1都改成gap就行了,完整代码如下:

public static void mySort(int[] arr) {
 if (arr == null || arr.length == 1) {
  return;
 }
 for(int gap = arr.length / 2; gap > 0; gap /= 2) {
  for(int i=gap; i<arr.length; i++) {
   int insertVal = arr[i];
   int insertIndex = i-gap;
   while (insertIndex >=0 && insertVal < arr[insertIndex]) {
    arr[insertIndex + gap] = arr[insertIndex];
    insertIndex -= gap;
   }
   if ((insertIndex + gap) != i) {
    arr[insertIndex + gap] = insertVal;
   }
  }
 }
}

怎么样,这样理解起来是不是简单多了?学废了吗



-java开发那些事-
长按扫描二维码
关注我 获取更多内容

本文分享自微信公众号 - java开发那些事(javawebkf)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。


695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

0条评论

Loading...


发表评论

电子邮件地址不会被公开。 必填项已用*标注

自定义皮肤 主体内容背景
打开支付宝扫码付款购买视频教程
遇到问题联系客服QQ:419400980
注册梁钟霖个人博客