使用OC写算法之插入排序

序言

看了一下最近写的OC写算法系列，好像还有不少排序算法都没有更新，可能有的朋友也有这方面的需求，所以最近我会把插入排序、归并排序、快速排序等更新出来，好吧，下面废话不多说，咱们进入正题。

什么是插入排序

先来简单的说句大白话，插入排序就是通过找到元素最合适插入位置的方式来进行排序的一中排序，下面再聊一下官方介绍：

插入排序是指每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

下面是我从网上扣的一张图，我觉得这张图描述的很清晰，下面请看图：

插入排序示意图.png

我们可以看到假如我们要找到4这个元素合适的插入位置，我们需要拿它与前面已经排好序的元素一次进行比较，当我们拿4和7进行比较后发现，4 比 7 小，然后我们就让他们交换位置，这是4和7已经是有序的了，这时候我们来寻找一下-2这个元素与前面已经排好序的元素去比较，发现-2比7小，交换位置，再与4比较发现比4小，此时它已经是第0个元素了，所以第0个位置就是它要插入的位置了，依次类推，你会发现经历5次寻找插入位置的操作过后，数组已经变成完全有序了，下面我们来看代码实现：

#pragma  mark -  未优化的插入排序
#pragma  mark -
/**
 未进行优化的插入排序（多次交换性能差）

 @param array 未排序数组
 */
- (void)insertionSort1:(NSMutableArray *)array {
    //i从1开始，因为第0个元素默认就是有序的
    for (int i = 1 ; i < array.count; i++) {
        //j从i这个位置开始 依次-- 和i前面的元素进行比较 寻找合适的插入位置 交换位置
        for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
            //每次比较当前元素和前一个元素 当前元素大于前一个时交换位置
            [array exchangeObjectAtIndex:j withObjectAtIndex:j -1];
        }
    }
}

我们这时可以测试一下50000的数据，执行效果和代码执行时长：

    //生成5万个元素的随机数组
    NSMutableArray *array1 = [self.testHelper generateRandomArray:50000 rangeLeft:1 rangeRight:100];

    NSLog(@"=============未优化的插入排序耗时==============");
    [self.testHelper testSortWithExcuteBlock:^{
        [self insertionSort1:array1];
    }];
    NSLog(@"%@",array1);

下面是测试结果：

未优化插入排序.png

插入排序的优化

我们发现耗时是相对比较长的，那到底是什么原因呢？从代码上看，我们就知道每一次插入都有多次交换操作，而一次交换操作相当于三次赋值操作，这是比较耗费性能的，那么我们有没有优化的方法呢？答案当然是有的，下面我们看下面的图，

插入排序优化图1.png

假如我们需要将下面的一个数组进行排序，我们从6这个元素开始考察，按照原来插入排序的做法是，发现与8比较要小于8，所以两个交换一下位置，但是我们这里不这么做，而是将这个元素复制一份假如就叫 temp，看下图：

插入排序优化图2.png

那么我们就可以拿temp这个元素与前面排好序的元素进行比较，我们发现temp比8小，此时我们将8往后挪动一个位置，再来考察8前面的元素与6进行比较，发现已经是第0个元素了，所以我们直接就可以将temp这个元素放入到8原来的位置上了，

插入排序优化图3.png

经历了上面的操作后，效果和原来的插入排序是一样的，但是效率却提升了不止一点，下面我们还是来看代码：

#pragma  mark -  优化后的插入排序
#pragma  mark -
/**
 优化后的插入排序（将多次交换优化为赋值）
 
 @param array 未排序数组
 */
- (void)insertionSort2:(NSMutableArray *)array {
    for (int i = 0; i < array.count; i++) {
        NSNumber *temp = array[i];
        int j ;//这里的j要声明在外面 因为最后temp和前面的元素比较完后 j就是temp要存放的位置
        for ( j = i; j > 0 && array[j - 1] > temp ; j--) {//只有j大于0以及前一个元素比比当前temp这个元素要大才让元素后移
                array[j] = array[j-1];
        }
        //经历了上面循环后 temp就找到了合适的插入位置了
        array[j] = temp;
    }
}

到这里，我们的插入排序也就完成了，当然我知道你们肯定要说了，你说提升了效率，那到底提升了多少你没说啊，别急，下面我就来测试一下:

    NSMutableArray *array1 = [self.testHelper generateRandomArray:50000 rangeLeft:1 rangeRight:100];
   NSMutableArray * insertionSort1 = array1.mutableCopy;
    NSMutableArray * insertionSort2 = array1.mutableCopy;
    NSLog(@"=============未优化的插入排序耗时==============");
    [self.testHelper testSortWithExcuteBlock:^{
        [self insertionSort1:insertionSort1];
    }];

    NSLog(@"=============优化后的插入排序耗时==============");
    [self.testHelper testSortWithExcuteBlock:^{
        [self insertionSort2:insertionSort2];
    }];

这里我们同样以5万的数量级来进行测试，发现测试结果如下：

插入排序优化前后对比.png

是不是很惊讶？优化后的插入排序是不是明显比未优化的插入排序提升了不少，大家也快去试验一下吧。最后再给大家提供一个第三个版本的插入排序，也就是给出两个边界left和right来进行排序的代码：

#pragma  mark -  插入排序3 根据传入的左边界和右边界进行排序
#pragma  mark -
- (void)insertionSort3:(NSMutableArray *)array left:(int)left right:(int)right {
    for (int i = left +1; i <= right; i++) {
        NSNumber *tempNum = array[i];
        int j ;
        for ( j = i; j > left && array[j - 1] > tempNum; j--) {
            array[j] = array[j - 1];
        }
        array[j] = tempNum;
    }
}

Swift版本的插入排序

最近看swift，所以更新一波

        for i in 1..<array.count {
            for j in (1...i).reversed(){
                if array[j] < array[j-1] {
                    array.swapAt(j, j-1)
                }
            }
        }
        

好吧，插入排序就讲这么多了，毕竟插入排序并不属于高级排序，下一篇文章我们来讲讲归并排序与插入排序的结合使用，欢迎关注