04数据结构排序算法之直接插入排序

直接插入排序（Straight Insertion Sort）基本思想是将数据分为有序区和无序区，每次从无序区中拿出一个数据插入到有序区中。

直接插入排序和简单选择排序很类似，简单选择排序的基本思想也是将数据分为有序区和无序区，每次从无序区中选择一个最小值放入有序区最后。具体参考简单选择排序（https://www.jianshu.com/p/9fbc1678f5aa）

具体代码实现如下：

/**
 *  直接插入排序
 *
 *  @param dataArray 要排序的数据源
 *
 *  @return 已排序的数据
 */
+ (NSArray *)straightInsertionSort:(NSArray *)dataArray {
    NSMutableArray *resultArray = [NSMutableArray arrayWithArray:dataArray];
    NSNumber *temp;
    NSInteger j;
    for (NSInteger i = 1; i < resultArray.count; i ++) {
        if (resultArray[i] < resultArray[i-1]) {
            temp = resultArray[i];//保存带排序的数据
            for (j = i - 1; j >= 0 && resultArray[j] > temp; j --) {//插入到前面已经排序的有序区中
                resultArray[j + 1] = resultArray[j];
            }
            resultArray[j + 1] = temp;
        }
        NSLog(@"i=%ld array:%@",i, resultArray);
    }
    return resultArray;
}