希尔排序（Java实现）

希尔排序（Shell Sort）
1959年Shell发明； 第一个突破O(n^2)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

(1)算法简介

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。

(2)算法描述和实现

核心思想：将整个待排序的序列分割成为若干子序列，分别进行直接插入排序。

具体过程：

<1>.设定增量数列t1，t2，…，tk，其中ti > tj（i<j），tk=1；
<2>.计增量数列中的增量个数为k，则对需要排序的序列进行k趟排序；
<3>.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m（m=n/ti）的子序列，分别对各子序列进行直接插入排序。
当增量为1 时，整个序列作为一个序列来处理，序列长度即为整个序列的长度。


【com/self/exercise/ShellSort.java】

package com.self.exercise;

import java.util.Arrays;

/**
 * 希尔排序
 */
public class ShellSort {

    public void sort(int[] arr) {
        int len = arr.length;

        for (int inc = len / 2; inc >= 1; inc /= 2) {
            for (int i = 0; i < inc; ++i) {
                for (int j = i; j < len; j += inc) {    // 需要排序的元素
                    int tmp = arr[j];
                    for (int k = j; k >= i + inc; k -= inc) {    // 怎么排？
                        if (arr[k - inc] > tmp) {
                            arr[k] = arr[k - inc];
                            if (k - inc == i) {
                                arr[i] = tmp;
                                break;
                            }
                        } else {
                            arr[k] = tmp;
                            break;
                        }
                    }
                }
            }
            // System.out.println(Arrays.toString(arr));
        }
    }
}

【com/self/exercise/ShellSortTest.java 】

package com.self.exercise;

import org.junit.Assert;
import org.junit.Test;

public class ShellSortTest {

    private ShellSort shellSort = new ShellSort();

    @Test
    public void sort1() {
        int[] src = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        int[] dst = {2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50};
        shellSort.sort(src);
        Assert.assertArrayEquals(dst, src);
    }

    @Test
    public void sort2() {
        int[] src = {592, 401, 874, 141, 348, 72, 911, 887, 820, 283};
        int[] dst = {72, 141, 283, 348, 401, 592, 820, 874, 887, 911};
        shellSort.sort(src);
        Assert.assertArrayEquals(dst, src);
    }
}