iOS - 插入排序

作者: SkyMing一C | 来源:发表于2017-12-25 21:01 被阅读65次

通过算法了解Swift 3—插入排序
iOS - 插入排序
iOS 插入排序
IOS 插入排序
希尔排序
iOS-插入排序
算法-插入排序
java快速学习排序---插入排序
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)
```
数据越接近正序，直接插入排序的算法性能越好。