希尔排序

发表于 分类于 ， ， 本文字数： 1.1k

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private void sort(int l,int r){
       int tmp;
       int gap = r-l+1;
       while (gap>1){
           gap=gap/2;
           System.out.println("gap: "+gap);
           for (int d = 0,j; d < gap; d++) {
               for (int i = (l+d)+gap; i <= r; i+=gap) { //起始值(l+d) 间隔gap
                   tmp = data[i];
                   for (j= i; j>=(l+d)+gap; j-=gap) { //直接插入排序
                       if(data[j]<data[j-gap]){
                           data[j]=data[j-gap];
                       }else {
                           break;
                       }
                   }
                   data[j]=tmp;
               }
           }
           System.out.println(Arrays.toString(data));
       }
   }

希尔排序

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。希尔排序是记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

我们分割待排序记录的目的是减少待排序记录的个数，并使整个序列向基本有序发展。而如上面这样分完组后，就各自排序的方法达不到我们的要求。因此，我们需要采取跳跃分割的策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

img

操作步骤：

初始时，有一个大小为 10 的无序序列。

（1）在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。

（2）接下来，按照直接插入排序的方法对每个组进行排序。

在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。

（3）按照直接插入排序的方法对每个组进行排序。

（4）在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。

（5）按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

效率分析

img

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧！
itingyu 微信打赏 微信打赏