思想：待排序的記錄按增量分割若干區(qū)域，然后對每個區(qū)域的對應(yīng)的元素進行insertionSort。

增量為n/2，即將序列分成兩份,注意：增量按需而定
排序前

Paste_Image.png

插入排序后

Paste_Image.png

Paste_Image.png

排序前

Paste_Image.png

Java展現(xiàn)其思想

package sortingAlgo;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 水皮蛋 
 * 思想：待排序的記錄按增量分割若干區(qū)域，然后對每個區(qū)域的對應(yīng)的元素進行
 * 
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = createRandomArray();
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(shellSort(arr)));
    }

    /**
     * 每個增量區(qū)進行元素對應(yīng)插入排序
     * 
     * @param arr
     * @param d
     * @return
     */
    public static int[] shellInsertSort(int[] arr, int d) {
        int n = arr.length, j = 0, key = 0;
        // i是未排序的第一個角標
        for (int i = d; i < n; i++) {
            j = i - d;
            key = arr[i];
            while (j >= 0 && arr[j] > key) {
                arr[j + d] = arr[j];
                j -= d;
            }
            arr[j + d] = key;
        }
        return arr;
    }

    /**
     * 每輪增量排序依次
     * 
     * @param arr
     * @return
     */
    public static int[] shellSort(int[] arr) {
        if (arr == null)
            throw new NullPointerException();
        int n = arr.length;
        if (!(n > 1))
            return null;
        // 定義增量
        int d = n / 2;
        while (d >= 1) {
            shellInsertSort(arr, d);
            d /= 2;
        }
        return arr;
    }

    /**
     * 使用Random類產(chǎn)生隨機數(shù)組的對象
     * 
     * @return 隨機數(shù)組
     */
    public static int[] createRandomArray() {
        Random random = new Random();
        int[] array = new int[10];
        for (int i = 0; i < 10; i++) {
            array[i] = random.nextInt(100);
        }
        return array;
    }

}