黑马程序员技术交流社区

标题: 求希尔排序的代码和解析 [打印本页]
作者: 韩基鑫    时间: 2014-3-18 21:03
标题: 求希尔排序的代码和解析
本帖最后由 韩基鑫 于 2014-3-19 15:30 编辑

毕老师在视频中说，希尔排序是最快的排序方法，网上的没看懂，希望高手们帮帮忙，谢谢
作者: zhxu188    时间: 2014-3-18 21:29
所谓希尔排序就是分组插入排序，比如一组数{2,5,4,1,8,6}，第一步先两个一组，再组内排序{2,5} {1，4}  {6，8}，然后再分成两组，组内在排序{1,2,4,5}  {6,8}  最后再合并{1,2,4,5,6,8}，排序完成，这是以前老师上课大概讲的，现在就记得这么多了，希望能帮助你
作者: syw02014    时间: 2014-3-18 21:44
希尔排序(缩小增量法) 属于插入类排序,由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. }
复制代码







欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2