package 排序.version_java;

import java.util.Arrays;

public class XiErSort {
    public static void shellSort(int[] array) {
        /**
         *  希尔排序
        -------------------------------- len = 10
        5, 3, 9, 12, 6, 1, 7, 2, 4, 11
        len / 2 = 5 步长是5
        --------------------------------索引5开始 与5-len/2相比
        , 3, 9, 12, 6, , 7, 2, 4, 11    
        5              1
        --------------------------------使用插入排序进行排序
        1, 3, 9, 12, 6, 5, 7, 2, 4, 11  
        --------------------------------
        #1, , 9, 12, 6, 5, , 2, 4, 11
        #   3              7
        #--------------------------------不变，这一步在遍历时就不会走
        1, 3, , 12, 6, 5, 7, , 4, 11
              9              2
        --------------------------------使用插入排序进行排序
        1, 3, 2, 12, 6, 5, 7, 9, 4, 11
        --------------------------------
        1, 3, 2, , 6, 5, 7, 9, , 11
                 12            4
        --------------------------------使用插入排序进行排序
        1, 3, 2, 4, 6, 5, 7, 9, 12, 11
        # 6 和 11 不走
        5 // 2 = 2 步长是2
        --------------------------------
        索引2开始，1-2跳过
        索引3，3-4跳过
        索引4，1-2-6跳过
        索引5，3-4-5跳过
        索引6，1-2-6-7跳过
        索引7，3-4-5-9跳过
        索引8，1-2-6-7-12跳过
        索引9，3-4-5-9-11跳过
        --------------------------------
        2 // 2 = 1
        1, 3, 2, 4, 6, 5, 7, 9, 12, 11
        --------------------------------
        索引1开始，1-3跳过
        索引2
         ,  ,  , 4, 6, 5, 7, 9, 12, 11
        1, 3, 2
        --------------------------------3右移，2补进去
        1, 2, 3, 4, 6, 5, 7, 9, 12, 11
        索引3，1-2-3-4跳过
        索引4，1-2-3-4-6跳过
        索引5
        1, 2, 3, 4, 6, 5, 7, 9, 12, 11
        1, 2, 3, 4, 6, 5
        --------------------------------6右移，5补进去
        1, 2, 3, 4, 5, 6, 7, 9, 12, 11
        --------------------------------
        ........
        --------------------------------
        12右移，11补进去
        1, 2, 3, 4, 5, 6, 7, 9, 11, 12
         */
        //希尔排序的增量
        int d = array.length;

        while (d > 1) {
            //使用希尔增量的方式，即每次折半
            d = d / 2;
            for (int x = 0; x < d; x++) {
                for (int i = x + d; i < array.length; i = i + d) {
                    int temp = array[i];
                    int j;
                    for (j = i - d; (j >= 0) && (array[j] > temp); j = j - d) {
                        array[j + d] = array[j];
                    }
                    array[j + d] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = { 5, 3, 9, 12, 6, 1, 7, 2, 4, 11 };
        // 这个例子希尔排序没有排上作用，反倒消耗了多余的性能
        // int[] array = { 2, 1, 5, 3, 7, 6, 9, 8 };  
        shellSort(array);
        System.out.println(Arrays.toString(array));
    }
}