直接插入排序(Straight Insertion Sort)

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要点：设立哨兵，作为临时存储和判断数组边界之用。

假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，直接插入排序的时间复杂度是O(N2)。
时间复杂度：O（n^2）.

例：

- (void)viewDidLoad {
    [super viewDidLoad];
    NSMutableArray *arrSort = [NSMutableArray arrayWithArray:@[@(7), @(3), @(5), @(7), @(2), @(4), @(9), @(6)]];
    [self p_InsertSort:arrSort];
}

- (void)p_InsertSort:(NSMutableArray *)arrSort {
    NSInteger num = arrSort.count;
    
    for (int i = 1; i < num; i++) {
        if (arrSort[i] < arrSort[i-1]) {
            int j       = i - 1;
            
            // x 临时存储当前哨兵变量
            NSNumber *x = arrSort[i];
            
            // 将i-1 赋值给i  就会有两个一样的数字
            arrSort[i]  = arrSort[i-1];

            // 利用哨兵在已排序的数组中依次逆序遍历找到自己的位置并插入
            while (x < arrSort[j]) {
                arrSort[j+1] = arrSort[j];
                j--;
                if (j < 0) {
                    break;
                }
            }
            arrSort[j+1] = x;
        }
        
        [self p_PrintLog:i SortArray:arrSort];
    }
}


- (void)p_PrintLog:(NSInteger)index SortArray:(NSMutableArray *)arrSort{
    NSLog(@"index == %ld",(long)index);
    
    NSString *strResult;
    for (int j = 0; j< arrSort.count; j++) {
        strResult = [NSString stringWithFormat:@"%@ %ld",strResult, (long)[arrSort[j]integerValue]];
    }
    NSLog(@"%@",strResult);
}

image.png