java算法之希尔排序

基本思想
先将待排序的数组元素分成多个子数组，使得每个子数组的元素个数相对较少，然后对各个子数组分别进行直接插入排序，待整个待排数组“基本有序”后，最后在对所有元素进行一次直接插入排序。
代码

public class ShellSort {

    public static void shellSort(int[] arrays) {
        int temple;

        if (arrays == null || arrays.length <= 1) {
            return;
        }
        // 增量
        int incrementNum = arrays.length / 2;
        while (incrementNum >= 1) {
            for (int i = incrementNum; i < arrays.length; i++) {
                // 进行插入排序
                for (int j = i; j >= incrementNum; j = j - incrementNum) {
                    if (arrays[j] < arrays[j - incrementNum]) {
                        temple = arrays[j];
                        arrays[j] = arrays[j - incrementNum];
                        arrays[j - incrementNum] = temple;
                    }
                }
            }
            // 设置新的增量
            incrementNum = incrementNum / 2;
        }
    }

    public static void main(String[] args) {
        int[] a = new int[] { 49, 38, 65, 97, 76, 13, 27, 50 };
        shellSort(a);
        for (int i : a)
            System.out.print(i + " ");
    }
}

时间复杂度
O(n)——–最好
O(n^2)—–最坏
O(nlog2n)–平均