八大排序之希尔排序

核心思想：增量分组插入排序

C++：

void Solution::shellSort(std::vector<int>& arrNumbers) {
    
    for ( int increment = arrNumbers.size() / 2; increment > 0; increment /= 2 ) {
        
        for ( int end = increment; end < arrNumbers.size(); ++end ) {
            
            insertSort(arrNumbers, increment, end);
        }
    }
}


void Solution::insertSort(std::vector<int>& arrNumbers, int increment, int i) {
    
    // increment 表示的是分组元素之间的 间隔
    // i 表示当前分组的最后一个元素
    int j = i;
    while ( j - increment >= 0 && arrNumbers[j] < arrNumbers[j - increment] ) {
        
        // swap
        // 异或：相同为 0，不同为 1
        arrNumbers[j] = arrNumbers[j] ^ arrNumbers[j - increment];
        arrNumbers[j - increment] = arrNumbers[j] ^ arrNumbers[j - increment];
        arrNumbers[j] = arrNumbers[j] ^ arrNumbers[j - increment];
        
        j -= increment;
    }
}

Objective-C：

+ (nullable NSArray<NSNumber *> *)shellSort:(nonnull NSArray<NSNumber *> *)arrNumbers {
    
    NSMutableArray<NSNumber *> *arrMNumbers = [arrNumbers mutableCopy];
    for ( NSInteger increament = arrMNumbers.count / 2; increament > 0; increament /= 2 ) {
        
        for ( NSInteger i = increament; i < arrMNumbers.count; ++i ) {
            
            for ( NSInteger j = i; j - increament >= 0; j -= increament  ) {
                
                if ( arrMNumbers[j].integerValue < arrMNumbers[j - increament].integerValue ) {
                     
                    NSNumber *tempNumber = arrMNumbers[j - increament];
                    arrMNumbers[j - increament] = arrMNumbers[j];
                    arrMNumbers[j] = tempNumber;
                }
            }
        }
    }
    
    return [arrMNumbers copy];
}

DEMO