插入排序（Insertion Sort）

1. 算法描述

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

• 从第一个元素开始，该元素可以认为已经被排序;
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素的值赋值给新元素；循环此步骤,直到不大于新元素;
• 一趟出来前面变为有序,再选取下一个元素;

2. 过程演示

插入排序.gif

原始数据

34 54  12  78 3  45  9  

I = 1;

34 54  12  78 3  45  9  

I =  2;

34  54  54  78 3  45  9  

34  34  54  78 3  45  9  

12  34  54  78 3  45  9  

I =  3;

12  34  54  78 3  45  9  

I = 4;

12  34  54  78 78  45  9  

12  34  54  54 78  45  9  

12  34 34  54 78  45  9  

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

I = 5;

3    12 34  54 78  78  9  

3    12 34  54 54  78  9  

3    12 34 45 54  78  9  

I = 6;

3    12 34 45 54  78  78  

3    12 34 45 54 54  78  

3    12 34 45 45 54  78  

3    12 34 34 45 54  78  

3    12 12 34 45 54  78  

3     9 12 34 45 54  78 

3. 代码实现

/*
 1. 从第一个元素开始，该元素可以认为已经被排序；
 2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
 3. 如果该元素（已排序）大于新元素，将该元素的值赋值给新元素；循环此步骤,直到不大于新元素.
 4.一趟出来前面变为有序,再选取下一个元素
 */

- (NSArray *)insertSort:(NSArray *)sortArray {
    NSMutableArray *sort = [NSMutableArray arrayWithArray:sortArray];
    NSInteger length = sortArray.count;
    
    NSInteger count1 = 0;// 外层循环次数
    NSInteger count2 = 0;//内层循环次数
    
    for (int i = 1; i < length; i ++) {
        count1 ++;
        NSInteger preIndex = i -1;
        NSInteger currentValue = [sort[i] integerValue];
        
        // 如果有序集合还没有扫描完  并且当前值 小于集合里的值
        while (preIndex >= 0 && currentValue < [sort[preIndex] integerValue]) {
            count2 ++;
            sort[preIndex + 1] = sort[preIndex];
            preIndex --;
        }
        
        // 如果没有进入上面循环 就是把当前值付给当前位置
        sort[preIndex + 1] = @(currentValue);
    }
    NSLog(@"count1 : %ld\n count2 :%ld\n sort: %@",(long)count1,(long)count2,sort);
    return sort;
}

4. 验证

NSArray *arr = [self pakageNumber:1000];  // 1000个随机数
NSArray *arr1 = [self selectedSort:arr];
count1 : 999                         // 外层循环
count2 : 249739                  // 内层循环

5. 插入排序＋二分查找

// 插入排序 ＋ 二分查找
- (NSArray *)binarySort:(NSArray *)sortArray {
    NSMutableArray *sort = [NSMutableArray arrayWithArray:sortArray];
    NSInteger length = sortArray.count;
    
    NSInteger count1 = 0;// 外层循环次数
    NSInteger count2 = 0;//内层循环次数
    
    for (int i = 1; i < length; i ++) {
        count1 ++;
        NSInteger currentValue = [sort[i] integerValue];

        // 先通过二分查找找到确定的位置的index
        NSInteger low = 0;
        NSInteger high = i -1;
        while (low <= high) {
            count2 ++;
            NSInteger midle = (low + high) / 2;
            if ([sort[midle] integerValue] <= currentValue) {
                low = midle + 1;
            } else {
                high = midle - 1;
            }
        }
        
        [sort removeObjectAtIndex:i];
        [sort insertObject:@(currentValue) atIndex:low];
    }
    NSLog(@"count1 : %ld\n count2 :%ld\n sort: %@",(long)count1,(long)count2,sort);
    return sort;
}

验证

NSArray *arr = [self pakageNumber:1000];  // 1000个随机数
NSArray *arr1 = [self binarySort:arr];
count1 : 999                         // 外层循环
count2 : 8590                     // 内层循环

一万条数据所用时间
times:1.518605s(插入)
times:0.050543s(插入+ 2分查找)