图片源于网络
插入排序
插入排序法（Inser Sort）是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。
算法思想
从第一个元素开始，认为该元素已经是排好序的。
取下一个元素，在已经排好序的元素序列中从后向前扫描。
如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
重复上一步骤，直到已排好序的元素小于或等于新元素。
在当前位置插入新元素。
重复"取下一个元素，在已经排好序的元素序列中从后向前扫描"过程。
图-直接插入排序示例图
范例代码
/**
插入排序
@param array 需要排序的Array
*/
+ (void)inserSort:(NSMutableArray *)array{
//插入排序的原理：始终定义第一个元素为有序的，将元素逐个插入到有序排列之中，其特点是要不断的
//移动数据，空出一个适当的位置，把待插入的元素放到里面去。
for (int i = 0; i < array.count; i++) {
NSNumber *temp = array[i];
//temp 为待排元素 i为其位置 j为已排元素最后一个元素的位置（即取下一个元素，在已经排好序的元素序列中从后向前扫描）
int j = i-1;
//当j < 0 时， i 为第一个元素 该元素认为已经是排好序的 所以不进入while循环
// [array[j] compare:temp] == NSOrderedDescending与[array[j] intValue] > [temp intValue] 作用相同
while (j >= 0 && [array[j] compare:temp] == NSOrderedDescending) {
//如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置
[array replaceObjectAtIndex:j+1 withObject:array[j]];
j--;
}
//跳出while循环时，j的元素小于或等于i的元素(待排元素)。插入新元素 i= j+1
[array replaceObjectAtIndex:j+1 withObject:temp];
NSLog(@"插入排序排序中:%@",array);
}
}
算法分析
-
直接插入排序的算法性能
直接插入排序的算法性能
-
时间复杂度
当元素的初始序列为正序时，仅外循环要进行n-1趟排序且每一趟只进行一次比较，没有进入if语句不存在元素之间的交换(移动)。此时比较次数(Cmin)和移动次数(Mmin)达到最小值。 此时时间复杂度为O(n)。
Cmin = n-1; Mmin = 0;当元素的初始序列为反序时，每趟排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移(arr[j+1] = arr[j])，i个元素后移移动次数当然也就为i了，再加上temp = arr[i]与arr[j+1] = temp的两次移动，每趟移动的次数为i+2,此时比较次数(Cmin)和移动次数(Mmin)达到最小值。 此时时间复杂度为O(n2)。
Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n2) Mmax = (1+2)+(2+2)+...+(n-1+2) = (n-1)*(n+4)/2 = O(n2) (i取值范围1~n-1)数据越接近正序，直接插入排序的算法性能越好。
-
空间复杂度
由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 O(1) 。
-
算法稳定性
直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。
插入排序和选择排序的区别
插入排序和选择排序都有两层循环，外循环遍历整个数组，内循环稍有区别：
选择排序的内循环是遍历一组未排过序的数组。
插入排序的内循环是遍历一组已排过序的数组。
