要求

  • 能够用自己语言描述希尔排序算法

    算法描述

  1. 首先选取一个间隙序列，如 (n/2，n/4 … 1)，n 为数组长度
  2. 每一轮将间隙相等的元素视为一组，对组内元素进行插入排序，目的有二
    ① 少量元素插入排序速度很快
    ② 让组内值较大的元素更快地移动到后方
  3. 当间隙逐渐减少，直至为 1 时，即可完成排序

    算法实现

    1. private static void shell(int[] a) {
    2. int n = a.length;
    3. for (int gap = n / 2; gap > 0; gap /= 2) {
    4.     // i 代表待插入元素的索引
    5.     for (int i = gap; i < n; i++) {
    6.         int t = a[i]; // 代表待插入的元素值
    7.         int j = i;
    8.         while (j >= gap) {
    9.             // 每次与上一个间隙为 gap 的元素进行插入排序
    10.             if (t < a[j - gap]) { // j-gap 是上一个元素索引，如果 > t，后移
    11.                 a[j] = a[j - gap];
    12.                 j -= gap;
    13.             } else { // 如果 j-1 已经 <= t, 则 j 就是插入位置
    14.                 break;
    15.             }
    16.         }
    17.         a[j] = t;
    18.         System.out.println(Arrays.toString(a) + " gap:" + gap);
    19.     }
    20. }
    21. }

    参考资料

插入排序的变形