直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。

1024555-20161126000335346-416319390.png

代码实现
oc:

// 直接插入排序
- (void)insertionSort:(NSMutableArray *)arr{
    for (int i = 1; i < arr.count; i++) {
        int j = i;
        while (j > 0 && arr[j] < arr[j - 1]) {
            [self swap:arr from:j to:j-1];
            j--;
        }
    }
}

swift:

// 直接插入排序
    func insertionSort(arr:inout Array<Int>){
        for i in 1..<arr.count  {
            var j = i;
            while j>0&&arr[j] < arr[j - 1] {
                self.swap(arr: &arr, a: j, b: j-1)
                j = j - 1;
            }
        }
    }

简单插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);在最坏情况下，时间复杂度依然为O(n2)。但是在数组元素随机排列的情况下，插入排序还是要优于上面两种排序的。

总结

上面三篇文章列举了排序算法中最基本的三种算法（简单选择，冒泡，插入），这三种排序算法的时间复杂度均为O(n的平方)，后续会陆续更新其他更高阶一些的排序算法，时间复杂度也会逐步突破O(n的平方），谢谢支持。