A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 韩基鑫 中级黑马   /  2014-3-18 21:03  /  954 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 韩基鑫 于 2014-3-19 15:30 编辑

毕老师在视频中说,希尔排序是最快的排序方法,网上的没看懂,希望高手们帮帮忙,谢谢

2 个回复

倒序浏览
所谓希尔排序就是分组插入排序,比如一组数{2,5,4,1,8,6},第一步先两个一组,再组内排序{2,5} {1,4}  {6,8},然后再分成两组,组内在排序{1,2,4,5}  {6,8}  最后再合并{1,2,4,5,6,8},排序完成,这是以前老师上课大概讲的,现在就记得这么多了,希望能帮助你
回复 使用道具 举报
希尔排序(缩小增量法) 属于插入类排序,由Shell提出,希尔排序对直接插入排序进行了简单的改进:它通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项大跨度地移动,当这些数据项排过一趟序之后,希尔排序算法减小数据项的间隔再进行排序,依次进行下去,进行这些排序时的数据项之间的间隔被称为增量,习惯上用字母h来表示这个增量。
常用的h序列由Knuth提出,该序列从1开始,通过如下公式产生:
h = 3 * h +1
反过来程序需要反向计算h序列,应该使用
h=(h-1)/3
  1. public static void shellSort(int[] arr) // 计算出最大的h值
  2. {
  3.         int h=1;
  4.         while(h<=arr.length/3)
  5.                 h=h*3+1;
  6.         while(h>0)
  7.         {
  8.                 for(int i=h;i<arr.length;i+=h)
  9.                 {
  10.                         if(arr[i]<arr[i-h])
  11.                         {
  12.                                 int tmp=arr[i];
  13.                                 int j=i-h;
  14.                                 while(j>=0&&arr[j]>tmp)
  15.                                 {
  16.                                         arr[j+h]=arr[j];
  17.                                         j-=h;
  18.                                 }
  19.                                 arr[j+h]=tmp;
  20.                         }                 
  21.                 }
  22.                 h=(h-1)/3; // 计算出下一个h值
  23.         }
  24. }
复制代码



评分

参与人数 1技术分 +1 收起 理由
菜小徐 + 1

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马