直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
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的平方），谢谢支持。
