直接插入排序

将一个记录插入到已排好序的序列中，从而得到一个新的有序序列（将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序）

重点：使用哨兵，用于临时存储和判断数组边界。

//插入排序
- (void)insertionSortArray:(NSMutableArray *)array {
    for (int i = 1; i < array.count; i++) {
        int j = i;  /* j是一个坑， 确定坑的位置，再把数从坑里取出来，注意顺序*/
        id temp = array[i]; /* temp 是从坑里取数*/
        if ([array[i] intValue] < [array[i-1] intValue]) {  /* j > 0 防止越界。写&&前面效率更高*/
            while (j > 0 && [temp intValue] < [array[j-1] intValue]) {
                array[j] = array[j-1];
                j--;
            }
            array[j] = temp;
        }
    }
    NSLog(@"%@",array);
}

截屏2021-05-25 下午1.29.56.png