iOS - 插入排序

Demo_github

图片源于网络

插入排序

插入排序法（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) 。

• 算法稳定性

  直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。

插入排序和选择排序的区别

插入排序和选择排序都有两层循环，外循环遍历整个数组，内循环稍有区别：

• 选择排序的内循环是遍历一组未排过序的数组。

• 插入排序的内循环是遍历一组已排过序的数组。

参考

排序三 直接插入排序