概述

希爾排序是直接插入排序的改進(jìn)，是一種非穩(wěn)定排序。
通過(guò)加大排序的間隔，并讓相隔這個(gè)"間隔"的子序列進(jìn)行插入排序。當(dāng)排序完一趟后，通過(guò)減小數(shù)據(jù)項(xiàng)的"間隔"依次排序下去。

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++){//分組
                //對(duì)分組進(jìn)行插入排序
                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:

通過(guò)代碼發(fā)現(xiàn)，直接插入排序與希爾排序的區(qū)別就是數(shù)據(jù)項(xiàng)間隔為1.

時(shí)間復(fù)雜度

平均時(shí)間復(fù)雜度 : O(n^1.25)

空間復(fù)雜度

沒有分配額外空間，空間復(fù)雜度為O(1)。