原始插入排序

• 1.前部分为排序好的元素，后部分为待排序元素
• 2.拿待排序元素与之前排序好的元素进行挨个比对，如果待排序元素小于前面元素则进行元素交换，直到待排序元素大于前面元素则停止循环

//插入排序
- (void)insertSortWithArray:(NSMutableArray *)array
{
    for (int begin = 1; begin < array.count; begin ++) {
        int current = begin;
        while (current > 0) {
            NSNumber *a = array[current];
            NSNumber *b = array[current - 1];
            
            if ([a integerValue] < [b integerValue]) {
                array[current] = b;
                array[current - 1] = a;
                current--;
            }else{
                current = 0;
            }
        }
    }
}

优化1

• 1.减少交换次数，先找到合适的插入位置，然后进行元素挪动

//插入排序优化1
//原始的插入排序是挨个比对交换，优化思路：先查找到合适的插入位置，然后在进行元素挪动，减少交换次数
- (void)insertSortOneWithArray:(NSMutableArray *)array
{
    for (int begin = 1; begin < array.count; begin ++) {
        NSNumber *beginV = array[begin];
        int index = 0;
        for (int i = begin - 1; i >= 0; i --) {
            NSNumber *preV = array[i];
            if ([preV integerValue] < [beginV integerValue]) {
                index = i + 1;
                break;
            }
        }
        
        //往后挪
        for (int i = begin - 1; i >= index; i --) {
            array[i + 1] = array[i];
        }
        array[index] = beginV;
    }
}

优化2

• 1.在优化1的基础上再次进行优化， 优化点：查找部分可以使用二分查找思想减少查找次数

//插入排序优化2
- (void)insertSortTwoWithArray:(NSMutableArray *)array
{
    for (int begin = 1; begin < array.count; begin ++) {
        NSNumber *beginV = array[begin];
        int index = [self twoSearchInsertWithArray:array insertIndex:begin];
        //往后挪
        for (int i = begin - 1; i >= index; i --) {
            array[i + 1] = array[i];
        }
        array[index] = beginV;
    }
}
//二分查找- 优化插入排序，返回插入位置
- (int)twoSearchInsertWithArray:(NSMutableArray *)array insertIndex:(int)insertIndex
{
    int insertV = [array[insertIndex] intValue];
    int begin = 0;
    int end = insertIndex;
    while (begin != end) {
        int mid = (begin + end) >> 1;
        NSNumber *midV=  array[mid];
        if (insertV < [midV integerValue]) {
            end = mid;
        }else{
            begin = mid + 1;
        }
    }
    return begin;
}
//二分查找返回索引->传入有序数组，用于参考
- (int)twoSearchWithArray:(NSMutableArray *)array
{
    NSInteger v = 25;
    
    int begin = 0;
    int end = (int)array.count;
    while (begin < end) {
        int mid = (begin + end) >> 1;
        NSNumber *midV = array[mid];
        if (v < [midV integerValue]) {
            end = mid;
        }else if (v > [midV integerValue]){
            begin = mid + 1;
        }else{
            return mid;
        }
    }

    return -1;
}