要求

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

    算法描述

    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. }

    参考资料