import org.junit.Test;

import java.util.Arrays;

/**
 * Created by wc on 2018/4/28.
 */

public class 希爾排序 {

    @Test
    public void test(){
        int[] array={1,9,8,4,2,7,6,5};
        sort(array,3);
        System.out.print(Arrays.toString(array));
    }

    /**
     * 這是插入排序的變種
     * @param array
     * @param k 每一次的步長
     */
    public void sort(int[] array,int k) {
        for (int m = 0; m < k; m++) {
            for (int i = m+k; i < array.length; i=i+k) {
                int j = i;
                int target = array[i];
                while (j > k-1 && target < array[j - k]) {
                    array[j] = array[j - k];
                    j=j-k;
                }
                array[j] = target;
            }
        }
    }
}