iOS 插入排序

  插入排序（Insertion Sort）的核心思想是：从数组中第二个元素开始，查找其适合放到该元素之前的数组中哪个位置最合适。

方式一：

  最简单粗暴的方式就是直接倒叙遍历当前待插入元素前边的数组，如果比当前数据大就进行交换。

- (void)sort
{
    NSInteger arrayCount = self.sortArray.count;

    for (NSInteger begain = 1; begain < arrayCount; begain++) {
        for (NSInteger end = begain; end >= 1 && [self compareObjcet:self.sortArray[end] anotherObject:self.sortArray[end - 1]]; end--) {
            [self swapObjectWithIndex:end anotherIndex:end - 1];
        }
    }
}

方式二：

  此种方式类似方式一，只是减少交换次数，首先需要备份待插入元素，倒序依次比较其与前边元素的值大小，如果当前元素小，就让其前边元素后移，直到找到比当前元素小或者相等的元素，记录此处位置，即为待插入元素，然后插入即可。

- (void)sort
{
    NSInteger arrayCount = self.sortArray.count;

    for (NSInteger begain = 1; begain < arrayCount; begain++) {
        NSInteger insertIndex = begain;
        id currentObject = self.sortArray[begain];
        for (NSInteger current = begain; current >= 1 && [self compareObjcet:currentObject anotherObject:self.sortArray[current - 1]]; current--) {
            self.sortArray[current] = self.sortArray[current - 1];
            insertIndex = current - 1;
        }
        self.sortArray[insertIndex] = currentObject;
    }
}

方式三：

  这种方式跟玩扑克牌抓牌及其相似。

第一步：查找到待插入元素适合插入的位置(快速查找插入位置中又利用了二分查找算法)

//    [0, index) 范围内找到 index的插入位置
- (NSInteger)searchIndexInArrayWithWaitIndex:(NSInteger)index
{
    if (self.sortArray.count < 1 || index >= self.sortArray.count) {
        return -1;
    }
    NSInteger begain = 0;
    NSInteger end = index;
    //  二分查找
    while (begain < end) {
        NSInteger mid = (begain + end) >> 1;
        if ([self compareObjcet:self.sortArray[index] anotherObject:self.sortArray[mid]]) {
            end = mid;
        } else {
            begain = mid + 1;
        }
    }
    
    return begain;
}

第二步：将待插入元素放入该位置，同时数组中剩余元素依次后移（此处应先移动最后一个数组元素）

- (void)insertObjectIndex:(NSInteger)currentIndx intoIndex:(NSInteger)index
{
    if (currentIndx <= index) {
        return;
    }
    id currentObjcet = self.sortArray[currentIndx];
    for (NSInteger begain = currentIndx; begain > index; begain--) {
        self.sortArray[begain] = self.sortArray[begain - 1];
    }
    self.sortArray[index] = currentObjcet;
}

第三步：整体的排序过程就是个遍历调用上述两步的过程

- (void)sort
{
    NSInteger arrayCount = self.sortArray.count;

    for (NSInteger begain = 1; begain < arrayCount; begain++) {
        NSInteger insertIndex = [self searchIndexInArrayWithWaitIndex:begain];
        [self insertObjectIndex:begain intoIndex:insertIndex];
    }
}

总结：插入排序可以分成两部分，一部分就是插入位置的确定（依次比较确定；二分查找确定），一部分就是插入操作（交换实现；数组中元素后移，待插入元素插入对应位置）