希尔排序

public class ShellSort {

    public static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void shellSort(int a[], int n) {
        int i, j, d,temp,k;
        // 步长
        for (d = n / 2; d > 0; d /= 2) {
            // 直接插入排序
            for (i = 0; i < d; i++) {
                for (j = i + d; j < n; j += d) {
                    if (a[j] < a[j - d]) {
                        temp = a[j];
                        k = j - d;
                        while (k >= 0 && a[k] > temp) {
                            a[k + d] = a[k];
                            k -= d;
                        }
                        a[k + d] = temp;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = { 43, 37, 64, 90, 76, 11, 29, 43 };
        shellSort(arr, arr.length);
        print(arr);
    }

}