希尔排序-Shell's Sort

希尔排序（Shell's Sort）是插入排序的一种。又称递减增量排序算法，是在直接插入排序算法的基础上一种改进版本。希尔排序是非稳定的排序算法。

排序逻辑：把待排序元素按照下标的一定增量分组，对每组进行直接插入排序算法排序；每一轮之后，增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个元素恰被分成一组，算法终止。

排序步骤：
设待排序元素个数为N
1，第一轮，使用N/2作为间隔，将数据分组，对每个分组进行排序。
2，第二轮，使用N/4作为间隔，继续对原数组进行分组处理。
3，依次缩小间隔进行分组，直至分组间隔为1时，进行最后一次排序。
4，排序完成。

排序代码：

public void shellSort() {
    int[] befArrays = {3, 5, 1, 4, 12, 18, 19, 20, 9, 3, 15, 7, 0};
    int length = befArrays.length;
    for (int step=length/2; step>0;) {
        for (int i=0; i<step; i++) {
            for (int j=i; j+step<length; ) {
                for (int k=j+step; k>=step;) {
                    if (befArrays[k-step] > befArrays[k]) {
                        int swap = befArrays[k];
                        befArrays[k] = befArrays[k-step];
                        befArrays[k-step] = swap;
                    } else {
                        break;
                    }
                    k -= step;
                }
                j += step;
            }
        }
        step = step/2;
    }

    for (int i=0; i<length; i++) {
        System.out.printf(befArrays[i] + "\t");
    }
}

for循环优化处理：

public void shellSortSimple() {
    int[] befArrays = {3, 5, 1, 4, 12, 18, 19, 20, 9, 3, 15, 7, 0};
    int length = befArrays.length;
    for (int step=length/2; step>0; step = step/2) {
        for (int i=step; i<length; i++) {
            for (int j=i; j-step>=0; j-=step) {
                if (befArrays[j-step] > befArrays[j]) {
                    int swap = befArrays[j];
                    befArrays[j] = befArrays[j-step];
                    befArrays[j-step] = swap;
                } else {
                    break;
                }
            }
        }
    }

    for (int i=0; i<length; i++) {
        System.out.printf(befArrays[i] + "\t");
    }
}

算法分析：