希尔排序

基本思想

希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

---

实现步骤

• 计算数组中间值，划分间隔gap
• 按照gap间隔，划分为新的子序列
• 分别使用插入排序，使每个子序列变得相对有序
• 减少间隔gap，重复步骤2、3

划分序列

---

实现代码

public class Shell_Sort {

    public static void shell_sort(int[] array){
        if (array==null||array.length<=0){
            return;
        }
        int length = array.length;
        int gap=length/2;
        int temp = 0;
        while (gap>0){
            for (int i = gap; i <length; i++) {
                temp = array[i];
                int preIndex = i-gap;
                while (preIndex>=0&& array[preIndex]>temp){
                    array[preIndex+gap] = array[preIndex];
                    preIndex-=gap;
                }
                array[preIndex+gap]=temp;
            }
            gap /=2;
        }


    }
    public static void main(String[] args) {
        int[] array = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};

        shell_sort(array);
        System.out.println(Arrays.toString(array));
    }
}