希尔排序

概述

希尔排序是直接插入排序的改进，是一种非稳定排序。
通过加大排序的间隔，并让相隔这个"间隔"的子序列进行插入排序。当排序完一趟后，通过减小数据项的"间隔"依次排序下去。

java代码

public class ShellSort {
    public static void main(String[] args) {
        int[] array = {98,21,62,48,33,6,55,17};
        System.out.print("ShellSort\n");
        printArray(array);
        System.out.print("start:\n");
        shellSort(array);
        System.out.print("end:\n");
    }

    static void shellSort(int[] arr){
        int increment = arr.length;
        while (true){
            increment = increment/3+1;

            for(int i=0;i<increment;i++){//分组
                //对分组进行插入排序
                for(int j=i+increment;j<arr.length;j=j+increment){
                    int temp = arr[j];
                    for(int k = j-increment;k>=0;k=k-increment){
                        if(temp<arr[k]){
                            arr[k+increment] = arr[k];
                            arr[k] = temp;
                        }else{
                            arr[k+increment] = temp;
                            break;
                        }

                    }

                }
                printArray(arr);
            }

            if(increment==1){
                break;
            }
        }
    }

    static void printArray(int[] arr){
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        System.out.print("\n");
    }
}

输出

ShellSort
98 21 62 48 33 6 55 17 
start:
48 21 62 55 33 6 98 17 
48 17 62 55 21 6 98 33 
48 17 6 55 21 62 98 33 
6 17 21 55 48 62 98 33 
6 17 21 33 48 55 98 62 
6 17 21 33 48 55 62 98 
end:

通过代码发现，直接插入排序与希尔排序的区别就是数据项间隔为1.

时间复杂度

平均时间复杂度 : O(n^1.25)

空间复杂度

没有分配额外空间，空间复杂度为O(1)。