原始插入排序

• 1.前部分為排序好的元素，后部分為待排序元素
• 2.拿待排序元素與之前排序好的元素進行挨個比對臣镣，如果待排序元素小于前面元素則進行元素交換，直到待排序元素大于前面元素則停止循環(huán)

//插入排序
- (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;
            }
        }
    }
}

優(yōu)化1

• 1.減少交換次數(shù)智亮，先找到合適的插入位置退疫，然后進行元素挪動

//插入排序優(yōu)化1
//原始的插入排序是挨個比對交換，優(yōu)化思路：先查找到合適的插入位置鸽素，然后在進行元素挪動，減少交換次數(shù)
- (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;
    }
}

優(yōu)化2

• 1.在優(yōu)化1的基礎(chǔ)上再次進行優(yōu)化亦鳞， 優(yōu)化點：查找部分可以使用二分查找思想減少查找次數(shù)

//插入排序優(yōu)化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;
    }
}
//二分查找- 優(yōu)化插入排序馍忽，返回插入位置
- (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;
}
//二分查找返回索引->傳入有序數(shù)組，用于參考
- (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;
}