插入排序

插入排序的基本思想如下：
将一个记录插入到已排序好的有序列表中，从而得到一个新的有序表。实现要点，我们需要设立一个哨兵，作为临时存储和判断数组边界来用。代码如下：

- (void)insertionSort{
    for(NSInteger i = 1;i < _array.count; i ++){
        
        NSInteger j = i - 1;
        int tmp = [_array[i] intValue];//设置哨兵
        
        [_array replaceObjectAtIndex:i withObject:_array[i-1]];
        
        while(j > -1 && tmp < [_array[j] intValue]){
            [_array replaceObjectAtIndex:j+1 withObject:_array[j]];
            j--;
        }
        [_array replaceObjectAtIndex:j+1 withObject:@(tmp)];
    }
}

改进

上述代码是直接插入排序，下面咱们看一下折半插入排序：
因为插入排序要求对已经有序的表进行插入，那么我们就可以利用折半查找法来查找要插入的位置。代码如下：

 for(NSInteger i = 1; i < _array.count; i ++){
        
        int tmp = [_array[i] intValue];
        NSInteger low = 0;
        NSInteger high = i - 1;
        while (low <= high) {//查找要插入的位置
            NSInteger mid = (low + high) / 2;
            if(tmp < [_array[mid] intValue]){//在左半区找
                high = mid - 1;
            }else{//在右半区找
                low = mid + 1;
            }
        }
        for(NSInteger j = i; j > low ; j--){
            [_array replaceObjectAtIndex:j withObject:_array[j-1]];//元素后移
        }
        [_array replaceObjectAtIndex:low withObject:@(tmp)];
    }