將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數(shù)增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。
要點：設(shè)立哨兵，作為臨時存儲和判斷數(shù)組邊界之用。

假設(shè)被排序的數(shù)列中有N個數(shù)。遍歷一趟的時間復(fù)雜度是O(N)，需要遍歷多少次呢？N-1！因此，直接插入排序的時間復(fù)雜度是O(N2)。
時間復(fù)雜度：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 臨時存儲當(dāng)前哨兵變量
            NSNumber *x = arrSort[i];
            
            // 將i-1 賦值給i  就會有兩個一樣的數(shù)字
            arrSort[i]  = arrSort[i-1];

            // 利用哨兵在已排序的數(shù)組中依次逆序遍歷找到自己的位置并插入
            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