IOS 插入排序

最近在招IOS开发。发现好多IOS的开发，基础的东西比较差。都是在写一些页面啊，业务逻辑啊（自己也没有多厉害）

自己就想整理一些东西，都是用oc写的。也当自己复习一下吧，第一次写，有问题，还请见谅

插入排序

相关概念

将原有序列分为有序区和无序区，然后通过比较将无序区的数据插入到有序区里

v1.0

v1.0 普通插入排序

假设数组为a[0…n]

1. 将原本的序列分为有序区和无序区，a[0…i-1]为有序区，a[i…n]为无序区
2. 从无序区拿出第一个元素即：a[i],跟有序区末尾进行比较即：a[i-1]
3. 若a[i-1]大于a[i]，则交换位置，然后继续向前比较，指导a[i-1]不大于a[i]为止
4. 重复2~3步骤

-(void)insertionSort:(NSMutableArray*)data{
    for(int i = 0 ; i < data.count ; i ++){
        for(int j = i ; j > 0 && data[j] < data[j-1] ; j --){
            NSNumber *t = data[j];
            data[j] = data[j-1];
            data[j-1] = t;
        }
    }
}

v2.0

v2.0 优化插入排序

普通版：每次都要和前一位比较，小的话进行交换，要有3次赋值操作，

优化后 ：

1. 将原本的序列分为有序区和无序区，a[0…i-1]为有序区，a[i…n]为无序区
2. 从无序区拿出第一个元素即：a[i],跟有序区末尾进行比较即：a[i-1] (到此步骤和v1.0一样)
3. 若a[i-1]大于a[i]，则a[i-1]向后移动一位
4. 重复步骤3，直到找到小于或等于a[i]的有序元素，将a[i]插入到该位置的下一个位置中
5. 重复2~4步骤

可以看出优化后的步骤，每次减少了两次赋值，每次比较只是让有序数组的位置向后挪动一位

找到对应的位置后，再将无序的元素插入到指定位置

-(void)insertionSortToOptimize:(NSMutableArray*)data{
    for (int i = 0 ; i < data.count ; i ++){
        NSNumber * t = data[i];
        int j ;
        for(j = i ; j > 0 && t < data[j-1] ; j --){
            data[j] = data[j-1];
        }
        data[j] = t;
    }
}

思考：

如果我们前面的有序数组是按照顺序的，待插入的需要从有序区的末尾去找到自己对应的位置，那么我们是否可以对这个查找的过程进行优化呢？比如，二分查找！

v3.0

在2.0的基础上进行优化，采用二分查找法，向前面的有序数组进行查找并交换

-(void)insertionSortByBinarySearch:(NSMutableArray*)data{
    for(int i = 0 ; i < data.count ; i ++){
        NSNumber * t = data[i];
        int left = 0;
        int right = i -1;
        int mid = 0;
        
        while (left <= right) {
            mid = (right - left)/2 +left;
            if(t > data[mid])
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        
        for(int j = i ; j > left ; j --){
            data[j] = data[j-1];
        }
        data[left] = t;
    }
    
}

耗时比较

乱序数组(数据量大时)

耗时(毫秒)	v1.0	v2.0	V3.0	系统
1W数据	1361	741	694	9
5W数据	33978	18879	15443	50

通过表格可以看出，优化过后的2.0相比较1.0速度快了1倍，但是距离系统的排序相差还很多

思考：

如果是很少的数据量呢？插入排序会有什么效果

乱序数据(小数据量)

耗时(微秒)	v1.0	v2.0	V3.0	系统
10数据	7	3	3	11
20数据	11	7	7	16
50数据	47	25	25	29

通过表格测试数据可以看出，在数据量小的时候，插入排序还是有优势的

思考：

插入排序，相较其他的排序还有什么优点呢？（现在只有系统排序）只有数据量少的时候可用吗？

近似有序的数组

抽取整体数据抽取10条进行无序操作

耗时(毫秒)	V2.0	v3.0	系统
1W数据	3	4	4
5W数据	11	15	15
10W数据	26	36	30
100W数据	241	473	320

通过数据我们可以发现在近似有序的数组进行排序的时候，插入排序还是很有优势的。

因为在近似有序的数组进行排序的时候，每次从无序区拿出数据进行比较的时候，只需要比较一次就可以了

从而插入排序

但是我们会发现v3.0的反而会比v2.0的耗时多一些。

这是因为在3.0我们使用了二分查找法，从而使每次比较的次数反而增加了

结论

在近似有序的数组进行排序的时候。插入排序会从 进化成

使用场景

我们会在哪些场景使用插入排序呢？

• 如果我们本地有1万个有序的列表。服务器会每秒发过来一条新数据进行排序，那么我们每次拿到新数据，加入到数组里进行排序的时候插入排序就有用武之地了！