数据结构和算法 希尔排序

原理：

也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

核心是设定一个gap，如下图中设定gap为4，

第一次将红色底，间隔为4位的数字排序

第二次将蓝色底，间隔为4位的数字排序

第三次将紫色低，间隔为4位的数字排序

第四次将橙色低，间隔为4位的数字排序

最后整体基本有序，将整体进行插入排序

图解：

代码实现：

public class ShellSort {
    public static void main(String[] args) {
//        int[] arr = SortUtil.randomArr(15);
        int[] arr = {9,6,11,3,5,12,8,7,10,15,14,4,1,13,2};
        SortUtil.printArr(arr);
//        shellSort(arr);
//        shellSortByTemp(arr);
        shellSortDirect(arr);
        SortUtil.printArr(arr);
    }

    private static void shellSort(int[] arr){
//        int gap = 4;
        for (int gap = 4; gap >0 ; gap=gap/2) {
        // 插入排序
            for (int i = gap; i < arr.length; i++) {
                for (int j = i; j >=gap ; j-=gap) {
                    if(arr[j]<arr[j-gap]){
                        SortUtil.swap(arr,j,j-gap);
                    }
                }
            }
        }
    }
    private static void shellSortByTemp(int[] arr) {
        for (int gap = 4; gap > 0; gap = gap / 2) {
            // 插入排序
            for (int i = 0; i < arr.length; i++) {
                int temp = arr[i];
                int j = i - gap;
                while (j >= 0 && temp < arr[j]) {
                    arr[j + gap] = arr[j];
                    j = j - gap;
                }
                arr[j + gap] = temp;
            }
        }
    }
    private static void shellSortDirect(int[] arr) {
        for (int gap = arr.length/2; gap > 0; gap = gap / 2) {
            // 插入排序
            for (int i = 0; i < arr.length; i++) {
                int temp = arr[i];
                int j = i - gap;
                while (j >=0 && temp > arr[j]) {
                    arr[j + gap] = arr[j];
                    j = j - gap;
                }
                arr[j + gap] = temp;
            }
        }
    }
}

时间复杂度分析：

稳定性：

       不稳定。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。