封裝成類：

package com.roc.algorithms.sort;

/**
 * 希爾排序
 *
 * @author imroc
 */
public class ShellSort {
    //交換數(shù)組元素
    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void sort(int[] a) {
        int h = 1;
        while (h < a.length / 3) {//尋找合適的間隔h
            h = 3 * h + 1;
        }
        while (h >= 1) {
            //將數(shù)組變?yōu)殚g隔h個元素有序
            for (int i = h; i < a.length; i++) {
                //間隔h插入排序
                for (int j = i; j >= h && a[j] < a[j - h]; j -= h) {
                    swap(a, j, j - h);
                }
            }
            h /= 3;
        }
    }
}

測試：

int[] a = {9,0,6,5,8,2,1,7,4,3};
System.out.println(Arrays.toString(a));
ShellSort.sort(a);
System.out.println(Arrays.toString(a));

輸出：
[9, 0, 6, 5, 8, 2, 1, 7, 4, 3]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]