算法【3】：直接插入排序（又叫增量法）

1，基本思想

假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

也可以这么理解：

比如斗地主，我们喜欢把最大牌的放到左边，最小的放到左边，那么我们在每拿起一张牌，去插入的时候，就需要找到合适的位置。这个过程的排序，就是直接插入排序。

2，示例代码

oc版本

 NSMutableArray * arr  = [NSMutableArray arrayWithObjects: @(27), @(73), @(59), @(46), @(92), @(50), @(54), @(37), @(27), @(90), @(84), @(79), @(71), @(24), @(75), @(80), @(75), @(77), @(38), @(98), nil];
        int temp;
        NSMutableArray * reslults = [NSMutableArray arrayWithObjects:arr[0], nil];

        for(int i = 1;i < arr.count;i++)
        {
            temp = [arr[i] intValue];
            for (int j = 0; j < i; j ++)
            {
                int currj = [reslults[j] intValue];
                if (temp <= currj)
                {
                    [reslults insertObject:@(temp) atIndex:j];
                    break;
                }
                else
                {
                    if (j == i - 1)
                    {
                        [reslults addObject:@(temp)];
                    }
                }
            }
        }

c语言版本

public void insertSort(int[] list) {
    // 第1个数肯定是有序的，从第2个数开始遍历，依次插入有序序列
    for (int i = 1; i < list.length; i++) {
        int j = 0;
        int temp = list[i]; // 取出第i个数，和前i-1个数比较后，插入合适位置

        // 因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(list[j])比temp大，就把这个数后移一位
        for (j = i - 1; j >= 0 && temp < list[j]; j--) {
            list[j + 1] = list[j];
        }
        list[j + 1] = temp;
    }
}

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序，最坏时间复杂度为O(n^2)。