1. 算法描述

1959年Shell發(fā)明，第一個突破O(n2)的排序算法，是簡單插入排序的改進版。它與插入排序的不同之處在于，它會優(yōu)先比較距離較遠的元素。希爾排序又叫縮小增量排序。

• 先取一個整數(shù)increment（小于數(shù)組長度）作為間隔將全部元素分為increment個子序列;
• 然后分別對每一個子序列進行插入排序；
• 當increment為1時,只剩一個序列,進行插入排序,完成排序;

2. 過程演示

希爾排序.gif

原始數(shù)據(jù)

34 54  12  78 3  45  9           


increment = length / 2;
increment = 7 /2;
increment = 3;

34  78    9         

54  3               

12 45                 


I = 3;

34 54  12  78 3  45  9         (34 78  9)

I = 4;  

34  54  12  78  54  45  9     
34    3  12  78  54  45  9        (3  54)

I = 5
  
34 3  12  78  54  45  9         (12  45)

I =  6 

34  54  12 78  3  45  78
34  54  12 34  3  45  78  
9    54  12 34  3  45  78        (9  34 78 )



increment = 1;

9  54  12 34 3  45  78 

I = 1;

9  54  12 34 3  45  78 

I = 2

9  54  54 34 3  45  78 
9  12  54 34 3  45  78 

I = 3

9 12 54 54 3  45  78 
9 12  34 54 3  45  78 

I = 4

9 12  34 54 54  45  78 

9 12  34 34 54  45  78 

9 12 12  34 54  45  78 

9  9 12  34 54  45  78 

3 9 12  34 54  45  78 

I = 5

3 9 12  34 54 54  78 

3 9 12  34 45 54  78 

I = 6
3 9 12  34 45 54  78 

3. 代碼實現(xiàn)

- (NSArray *)shellSort:(NSArray *)sortArray {
    NSMutableArray *sort = [NSMutableArray arrayWithArray:sortArray];
    NSInteger length = sortArray.count;

    NSInteger count1 = 0;// 外層循環(huán)次數(shù)
    NSInteger count2 = 0;//內(nèi)層循環(huán)次數(shù)

    //初始增量為數(shù)組長度的一半，然后每次除以2取整
    for (NSInteger increment = length/2; increment > 0; increment /=2) {
        //初始下標設(shè)為第一個增量的位置，然后遞增
        count1 ++;
        for (NSInteger i = increment; i < length; i++) {
            // 跳躍式  插入排序
            NSInteger preIndex = i - increment;
            NSInteger currentValue = [sort[i] integerValue];
            //然后將此位置之前的元素，按照增量進行跳躍式比較
            while (preIndex >= 0  && currentValue < [sort[preIndex] integerValue]) {
                sort[preIndex + increment] = sort[preIndex];
                preIndex -= increment;
                count2 ++;
            }
            sort[preIndex + increment] = @(currentValue);
        }
    }
    NSLog(@"count1 : %ld\n count2 :%ld\n sort: %@",(long)count1,(long)count2,sort);
    return sort;
}

4. 驗證

NSArray *arr = [self pakageNumber:1000];  // 1000個隨機數(shù)
NSArray *arr1 = [self selectedSort:arr];
count1  :9                        // 外層循環(huán)
count2 :8006                  // 中層循環(huán)
count3 :7272                  // 內(nèi)層循環(huán)

一萬條數(shù)據(jù)所用時間
time:0.038147s;