插入排序

插入排序

一个有序的数组，往里面添加一个新的数据后，如何继续保持数据有序呢？很简单，只要遍历数组，找到数据应该插入的位置将其插入即可。

这是一个动态排序的过程，即动态地往有序集合中添加数据，可以通过这种方法保存集合中数据一直有序。而对于一组静态数据，也可以借鉴上面讲的插入方法，来进行排序，于是就有了插入排序算法。
那插入排序具体是如何借助上面的思想来实现排序的呢？
首先，将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素位空，算法结束。
如图所示，要排序的数据是4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。

插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当需要将一个数据a插入到已排序区间时，需要拿a与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素a插入。
对于不同的查找插入点算法（从头到尾、从尾到头），元素的比较次数是有区别的。但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度。
为什么说移动次数就等于逆序度呢？拿刚才的例子画个表，一看就明白了。满有序度是n * (n - 1) / 2 = 15，初始序列的有序度是5，所以逆序度是10.插入排序中，数据移动的个数总和也等于10 = 3 + 3 + 4。

代码实现如下

@interface DMInsertionSort : NSObject

// 插入排序
- (void)insertionPort:(NSMutableArray *)array;

@end

@implementation DMInsertionSort

- (void)insertionPort:(NSMutableArray *)array
{
    NSInteger moveCount = 0;
    NSLog(@"插入排序前数据：%@", array);
    if ([array count] > 1) {
        for (NSInteger i = 1; i < [array count]; i++) {
            NSNumber *num = [array objectAtIndex:i];
            NSInteger j = i - 1;
            // 查找插入位置
            for (; j >= 0; j--) {
                NSNumber *preNum = [array objectAtIndex:j];
                if ([preNum integerValue] > [num integerValue]) {
                    // 后移数据
                    [array replaceObjectAtIndex:j + 1 withObject:preNum];
                    moveCount += 1;
                } else {
                    break;
                }
            }
            
            // 插入数据
            [array replaceObjectAtIndex:j + 1 withObject:num];
        }
    }
    
    NSLog(@"插入排序后数据：%@", array);
    NSLog(@"移动总次数:%ld",(long)moveCount);
}

@end

@interface DMSortDemo : NSObject

@end

@implementation DMSortDemo

- (void)demo 
{   
    DMInsertionSort *insertionSort = [[DMInsertionSort alloc] init];
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:[NSNumber numberWithInteger:4]];
        [dataArray addObject:[NSNumber numberWithInteger:5]];
        [dataArray addObject:[NSNumber numberWithInteger:6]];
        [dataArray addObject:[NSNumber numberWithInteger:1]];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:2]];
        [insertionSort insertionPort:dataArray];
    }
    {
        NSMutableArray *dataArray = [[NSMutableArray alloc] init];
        [dataArray addObject:[NSNumber numberWithInteger:3]];
        [dataArray addObject:[NSNumber numberWithInteger:5]];
        [dataArray addObject:[NSNumber numberWithInteger:4]];
        [dataArray addObject:[NSNumber numberWithInteger:1]];
        [dataArray addObject:[NSNumber numberWithInteger:2]];
        [dataArray addObject:[NSNumber numberWithInteger:6]];
        [insertionSort insertionPort:dataArray];
    }
}

@end

第一，插入排序是原地排序算法吗？

从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，也就是说，这是一个原地排序算法。

第二，插入排序是稳定的排序算法吗？

在插入排序中，对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。

第三，插入排序的时间复杂度是多少？

如果要排序的数据已经是有序的，并不需要搬移任何数据。如果从尾到头在有序数据组里面查找插入位置，每次只需要比较一个数据就能确定插入的位置。所以这种情况下，最好时间复杂度为O(n)。注意，这里是从尾到头遍历已经有序的数组。
如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，所以最坏情况时间复杂度为O(n * n)。
在数组中插入一个数据的平均时间复杂度是O(n)。对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行n次插入操作，所以平均时间复杂度为O(n * n)。