上手難度：★★★★

算法復(fù)雜度：O(n^(1.3—2))

shell.gif

排序思想：

最開始以整個(gè)數(shù)組長(zhǎng)度的一半作為步長(zhǎng)gap進(jìn)行分組；
例如8個(gè)元素，索引0和索引4一組，索引1和索引5一組，索引2和索引6一組，索引3和索引7一組，分別對(duì)分好的組使用插入排序進(jìn)行排序，這樣就得到了4個(gè)已經(jīng)排好序的四組數(shù)據(jù)，
再對(duì)步長(zhǎng)gap進(jìn)行對(duì)半取值得到2，就會(huì)將索引0、索引2、索引4和索引6一組，索引1、索引3、索引5和索引7一組，再對(duì)這兩組進(jìn)行插入排序，就得到了兩個(gè)排好序的數(shù)組；
再對(duì)步長(zhǎng)gap進(jìn)行對(duì)半取值得到1，就得到了一組數(shù)據(jù)，再對(duì)這一組數(shù)據(jù)進(jìn)行插入排序，就能得出最終結(jié)果；

之所以沒有一開始就進(jìn)行插入排序，是因?yàn)椋诖罅繑?shù)據(jù)面前，希爾排序通過對(duì)一個(gè)個(gè)分組進(jìn)行排序，減少了比較和交換需要的次數(shù)，下圖是10000個(gè)元素下插入排序和希爾排序的對(duì)比

代碼實(shí)現(xiàn)：

public class ShellSort {

    /**
     * 插入排序，以gap為分組，往前進(jìn)行比較
     * 在gap為一半時(shí)，insert是每次對(duì)不同的分組進(jìn)行操作
     * 當(dāng)gap為四分之一時(shí)，在i的自增和循環(huán)過程中，insert會(huì)先以四分之一的步長(zhǎng)對(duì)前面的一部分進(jìn)行排序，         
     * 然后再通過步長(zhǎng)找到后面的值加入到前面的分組中，例如索引0、索引2、索引4和索引6一組，會(huì)先將索引0和2排好序，然后將4加入到0和2的數(shù)組中進(jìn)行排序，這里和動(dòng)圖演示的不一樣，動(dòng)圖是分組執(zhí)行，實(shí)際操作是多個(gè)分組交替執(zhí)行
     */
    private static void insert(int[] arr, int gap, int i){
        int temp = arr[i];
        //第一次進(jìn)來i就等于gap的值，從gap開始往前比較
        int j;

        //插入的時(shí)候按組進(jìn)行插入（組內(nèi)元素兩兩相隔gap）
        //這里循環(huán)的次數(shù)根據(jù)gap的值來確定，第一個(gè)gap等于整個(gè)數(shù)組長(zhǎng)度的一半，這里只能循環(huán)一次，后面gap會(huì)慢慢按2等比縮小，循環(huán)的次數(shù)也多了，gap越小，分到的組員就越多
        for(j = i - gap; j >= 0 && temp < arr[j]; j -= gap){
            //將兩兩相隔gap的值進(jìn)行比較，如果前一個(gè)值大于temp，就把前面的值賦給后面的值
            //之所以把這個(gè)加入到判斷條件，是因?yàn)榘凑詹迦肱判虻乃季S，默認(rèn)前面已經(jīng)排好序了
            // 事實(shí)也的確如此，因?yàn)樽铋_始對(duì)半取到的gap，只會(huì)有兩個(gè)值作為1組，然后排好這一組后，才會(huì)在i的自增中把后面的gap步長(zhǎng)的值加入進(jìn)來
            arr[j+gap] = arr[j];
        }

        arr[j+gap] = temp;
        //由于j已經(jīng)自減了gap，此時(shí)j+gap是gap前面的值，等于是交換了元素位置，把小值換到前面了
    }

    private static void shellSort(int[] arr){
        int n = arr.length;
        //每次都對(duì)半取gap的值，以gap為步長(zhǎng)進(jìn)行分組
        for(int gap = n/2; gap > 0; gap /= 2){
            for(int i = gap; i < n; i++){
                //對(duì)各個(gè)分組進(jìn)行插入排序 這里會(huì)循環(huán)n-gap次，每一次的循環(huán)，都是以gap為步長(zhǎng)找到組員進(jìn)行排序
                //這個(gè)循環(huán)的目的是以gap距離等比作為一組
                insert(arr, gap, i);
            }
        }
    }

    public static void main(String[] args) {

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        shellSort(arr);

        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }

    }
}

優(yōu)點(diǎn)：

減少交換次數(shù)，比插入排序提高了效率，因?yàn)椴迦肱判蛎看沃槐容^一位，而希爾排序通過分組的形式，減少了比較次數(shù)

缺點(diǎn)：

反直覺，只適合計(jì)算機(jī)中使用

優(yōu)化方式：

希爾排序的間隔序列不推薦用2的冪(1 2 4 8 16...)，因?yàn)檫@樣直到間隔為1之前，
都不會(huì)將奇數(shù)位置與偶數(shù)位置的元素進(jìn)行比較，這樣是低效的。希爾自己認(rèn)為可以用2的冪 - 1序列(1 3 7 15...)，后來又有文章建議用3x + 1(1 4 13 40 121...)，都是可以的。

    public static void shellSort2(int[] arr){
        int gap = 1;
        while (gap < arr.length/3) {
            gap = gap * 3 + 1;
        }
//        當(dāng)gap小于數(shù)組整個(gè)長(zhǎng)度的三分之一時(shí)，就自增3倍并且加1
//        1 4 13 40這種增長(zhǎng)模式

        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                insert(arr, gap, i);
            }
            gap = (int) Math.floor(gap / 3);
        }
    }