希爾排序(Shell Sort)，一聽這名字就知道是一個(gè)叫希爾的外國人發(fā)明的排序。沒錯(cuò)，他就是唐納德 希爾（Donald Shell），一位美國的計(jì)算機(jī)科學(xué)家，他于1959年發(fā)明的希爾排序算法。

對(duì)于希爾排序，比較正式的官方的解釋是這樣：

希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

希爾排序也是插入排序的一種。既然是其中的一種，那么他們的區(qū)別是什么呢？插入排序在最壞的情況下，即整個(gè)數(shù)組是倒序的，此時(shí)時(shí)間復(fù)雜度達(dá)到了O(n²)。希爾排序在插入排序的基礎(chǔ)上增加一個(gè)叫增量的概念。那什么增量？插入排序只能與相鄰的元素進(jìn)行比較，而希爾排序則是進(jìn)行跳躍比較，而增量就是步長(zhǎng)。比如增量為3時(shí)，下標(biāo)為0的元素與下標(biāo)為3的元素比較，3再與6比較，1與4比較，4再與7比較……想必你肯定做過一群人站成一排，按一二報(bào)數(shù)，喊一的一隊(duì)，喊二的一隊(duì)，此時(shí)的增量就是2。所以你也可以理解為是按增量進(jìn)行了分組，再對(duì)每一組進(jìn)行插入排序。當(dāng)使用一個(gè)增量對(duì)所有的分組排好序后，再去減少增量，重復(fù)之前步驟，直到增量為1，此時(shí)只有一個(gè)分組了，再對(duì)這一個(gè)分組進(jìn)行插入排序，整個(gè)希爾排序就結(jié)束了（所以希爾排序也叫縮小增量排序，但顯然沒有希爾排序好聽和高大上 斜眼笑）。

從增量的初始值選取，到逐漸變?yōu)?，將所有用過的增量組成一個(gè)序列，就是增量序列。而希爾排序的增量序列選擇直接影響它的時(shí)間復(fù)雜度（不要問我為什么，我也不知道）。最簡(jiǎn)單的增量就是希爾鼓勵(lì)使用的希爾增量。增量初始值選擇為N/2（N為數(shù)組長(zhǎng)度），然后每次將增量除以2，得到下一個(gè)增量。所以它的增量序列為{N/2, (N / 2)/2, ..., 1}。除了希爾增量還有Hibbard 增量、Knuth增量等等都是很復(fù)雜的數(shù)學(xué)公式，我怕你看了暈，就放在后面介紹吧?。ㄕf的好像自己看了不暈一樣）

那下面我們就以最簡(jiǎn)單的希爾增量來進(jìn)行希爾排序。

 void shellSort (NSMutableArray *array) {
  int count = (int)array.count;
  //初始增量為數(shù)組長(zhǎng)度的一半，然后每次除以2取整
  for (int increment = count/2; increment>0; increment /=2) {
  //初始下標(biāo)設(shè)為第一個(gè)增量的位置，然后遞增
    for (int i = increment; i<count; i++) {
        //獲取當(dāng)前位置
        int j = i;
        //然后將此位置之前的元素，按照增量進(jìn)行跳躍式比較
        while (j-increment>=0 && array[j]<array[j-increment]) {
            [array exchangeObjectAtIndex:j withObjectAtIndex:j-increment];
            j-=increment;
        }
    }
  }
}

然后對(duì)比之前文章所寫的選擇排序和插入排序。

void selectorSort (NSMutableArray * array){
  NSInteger count = array.count;
  for (int i = 0; i< count; i++) {
    int minIndex = i;
    for (int j = i + 1; j < count; j++) {
        if (array[j] < array[minIndex]) {
            minIndex = j;
        }
    }
    [array exchangeObjectAtIndex:i withObjectAtIndex:minIndex];
  }
}
void insertionSort (NSMutableArray *array) {
  NSInteger count = array.count;
  for (int i = 1; i<count; i++) {
    for (int j = i; j>0; j--) {
        if (array[j] < array[j-1]) {
            [array exchangeObjectAtIndex:j withObjectAtIndex:j-1];
        }else{
            break;
        }
    }
  }
}

三個(gè)同樣的數(shù)組，分別使用選擇、插入、希爾進(jìn)行排序比較時(shí)間。

 int main(int argc, const char * argv[]) {
  @autoreleasepool {
    NSMutableArray * sortArray1 = createDifferentArr(20000);
    NSMutableArray * sortArray2 = [sortArray1 mutableCopy];
    NSMutableArray * sortArray3 = [sortArray1 mutableCopy];
    //插入排序
    double startTime1 = CFAbsoluteTimeGetCurrent();
    insertionSort(sortArray1);
    double endTime1 = CFAbsoluteTimeGetCurrent();
    NSLog(@"插入排序用時(shí):%f s",endTime1 - startTime1);
    //選擇排序
    double startTime2 = CFAbsoluteTimeGetCurrent();
    selectorSort(sortArray2);
    double endTime2 = CFAbsoluteTimeGetCurrent();
    NSLog(@"選擇排序用時(shí):%f s",endTime2 - startTime2);
    //希爾排序
    double startTime3 = CFAbsoluteTimeGetCurrent();
    shellSort(sortArray3);
    double endTime3 = CFAbsoluteTimeGetCurrent();
    NSLog(@"希爾排序用時(shí):%f s",endTime3 - startTime3);
  }
  return 0;
}

數(shù)組長(zhǎng)度1萬時(shí)打印結(jié)果為：

2017-07-12 14:14:22.484 排序比較[14883:1166946] 插入排序用時(shí):1.848809 s
2017-07-12 14:14:25.161 排序比較[14883:1166946] 選擇排序用時(shí):2.675773 s
2017-07-12 14:14:25.179 排序比較[14883:1166946] 希爾排序用時(shí):0.017643 s

數(shù)組長(zhǎng)度為兩萬時(shí)打印結(jié)果為：

2017-07-12 14:15:59.069 排序比較[14899:1169188] 插入排序用時(shí):6.654105 s
2017-07-12 14:16:07.687 排序比較[14899:1169188] 選擇排序用時(shí):8.615417 s
2017-07-12 14:16:07.726 排序比較[14899:1169188] 希爾排序用時(shí):0.039497 s

差距是很明顯的。

希爾排序?yàn)?strong>不穩(wěn)定性排序。因?yàn)橄嗤脑乜赡茉诟髯缘牟迦肱判蛑幸苿?dòng)，所以它的穩(wěn)定性就被打破了。可能有人想問，穩(wěn)定性是干嘛的??？穩(wěn)定的意思是指相同的元素在排序后的相對(duì)位置不變。比如有兩個(gè)5 ，作為區(qū)分前面的叫5₁，后面的叫5₂，排序完成后5₁還在5₂的前面。那你可能會(huì)問，反正是一樣的，換了就換唄。但是在實(shí)際應(yīng)用中被排序的對(duì)象會(huì)擁有不同的屬性，舉個(gè)栗子，公司在招聘時(shí)，想要年齡小的，所以對(duì)所有人進(jìn)行了按年齡的排序。之后還想看成績(jī)分?jǐn)?shù)高的。所以在按成績(jī)進(jìn)行排序時(shí)就有可能出現(xiàn)成績(jī)一樣的，但他們的年齡不一樣，而你不能把成績(jī)相同但年齡大的排在小的前面。此時(shí)算法的穩(wěn)定性就有了意義。

• 關(guān)于hibbard增量
  hibbard增量的遞推公式為：H₁ = 1，H_i = 2 * H_i-1 + 1……
  這一看，這是從后往前推倒的啊，那初始增量怎么算?。?br> 初始增量的確定跟排序的趟數(shù)有關(guān)，我們用t代表趟數(shù)，t = log₂(n+1)，有小數(shù)就取整，想知道第n個(gè)增量，則公式為：
  第n個(gè)增量 = 2^(t-n+1) - 1 ，同樣也是有小數(shù)就取整。

使用希爾增量，在最壞的情況下時(shí)間復(fù)雜度仍為O(n²),而使用hibbard增量在最壞的情況下卻為O(n^3/2)。

如果覺得作者對(duì)哪里的理解有偏差或者其他的優(yōu)化，希望不吝賜教，留言指正。謝謝支持~