ShellSort

思想：待排序的记录按增量分割若干区域，然后对每个区域的对应的元素进行insertionSort。

增量为n/2，即将序列分成两份,注意：增量按需而定
排序前

Paste_Image.png

插入排序后

Paste_Image.png
两个区域内的元素对应逐一排序
Paste_Image.png
增量为n/5

排序前

Paste_Image.png
以此类推...

Java展现其思想

package sortingAlgo;

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

/**
 * @author 水皮蛋 
 * 思想：待排序的记录按增量分割若干区域，然后对每个区域的对应的元素进行
 * 
 */
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)));
    }

    /**
     * 每个增量区进行元素对应插入排序
     * 
     * @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类产生随机数组的对象
     * 
     * @return 随机数组
     */
    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;
    }

}