希尔排序(Shell sort)
LanyuanXiaoyao's Blog ヽ(✿゚▽゚)ノ

希尔排序(Shell sort)

2017-03-09

概念

将整个序列分割成若干小的子序列,再分别对子序列进行直接插入排序,使得原来序列成为基本有序。这样通过对较小的序列进行插入排序,然后对基本有序的数列进行插入排序,能够提高插入排序算法的效率。

希尔排序也是插入排序的一种,使用了分治的思想,让排序的时间复杂度较插入排序有大幅的提升,于是单独拿出来作为一章.
希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名.

步骤

  1. 先取一个正整数$d_1<n$,把所有序号相隔d1的数组元素放一组
  2. 组内进行直接插入排序
  3. 然后取$d_2<d_1$,重复上述分组和排序操作
  4. 直至$d_i=1$,即所有记录放进一个组中排序为止。

    举例

    例1

    n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例
    第一次gap=10/2=5

    1A,1B,2A,2B等为分组标记,数字相同的表示在同一组,大写字母表示是该组的第几个元素, 每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26),下同。
    第二次gap=5/2=2

    第三次gap=2/2=1

    第四次gap=1/2=0排序完成

例2

假定有一个数组[5, 7, 4, 10, 9, 6, 1, 3],我们要把这个数组按从小到大排列

  1. 首先我们先定义一个步长(step),这个step的意思就是一个间隔的距离,用来将数列进行分组.
  2. 在这个例子里面,我们取步长为数列长度的一半,也就是step=4,然后我们就按照从一个数开始,每隔step长度就取一个数,以此作为一组.也就是第一组为[5, 9].
  3. 然后从第二个数开始取,第二组为[7, 6]
  4. 依次类推,把所有的数都分组,这样我们就会得到step个组数,在这个例子里面,我们共得到4个分组:[5, 9],[7, 6],[4, 1],[10, 3].
  5. 然后对每一组进行直接插入排序,这样我们就得到了第一次分组后的数列[5, 6, 1, 3, 9, 7, 4, 10]
  6. 然后我们把step缩小,也就是把每一组的范围缩小,于是我们取新的step是原来step的一半,也就是step=2,然后获得新的分组为[5, 6, 1, 3][9, 7, 4, 10]
  7. 然后对新的分组分别进行直接插入排序,获得第二次排序后的数列为[1, 3, 5, 6, 4, 7, 9, 10]
  8. 最后step再次缩小变成step=1,即取全部的数为一组,进行直接插入排序,也就是对整个数组直接插入排序.
  9. 排序完成.

代码实现

这是严格按照定义来写的希尔排序

private static int[] shellSort1(int[] num) {
  for (int step = num.length / 2; step > 0; step /= 2) {
    for (int i = step; i < num.length; i += step) {
      for (int j = i; j > 0; j -= step) {
        if (num[j] < num[j - step]) {
          int temp = num[j];
          num[j] = num[j - step];
          num[j - step] = temp;
        }
      }
    }
  }
  return num;
}
private static int[] Sort(int[] num) {
  int gap = 1;
  int i, j, len = num.length;
  int temp;
  while (gap < len / 3)
  gap = gap * 3 + 1;
  for (; gap > 0; gap /= 3)
    for (i = gap; i < len; i++) {
      temp = num[i];
      for (j = i - gap; j >= 0 && num[j] > temp; j -= gap)
        num[j + gap] = num[j];
      num[j + gap] = temp;
    }
    return num;
}

实际测试

可以看到时间提升得非常多,这是一种高效的排序算法

数组大小(整数个数) 运行时间(ms)
100 0
1000 0
10000 5
100000 17
1000000 213
10000000 2823

评论