二分插入排序算法-OC实现

• 简介

二分法插入排序，简称二分排序，是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

• 基本过程

（1）计算 0 ~ i-1 的中间点，用 i 索引处的元素与中间值进行比较，如果 i 索引处的元素大，说明要插入的这个元素应该在中间值和刚加入i索引之间，反之，就是在刚开始的位置 到中间值的位置，这样很简单的完成了折半；
（2）在相应的半个范围里面找插入的位置时，不断的用（1）步骤缩小范围，不停的折半，范围依次缩小为 1/2 1/4 1/8 .......快速的确定出第 i 个元素要插在什么地方；
（3）确定位置之后，将整个序列后移，并将元素插入到相应位置。

• C语言实现

void binaryInsertSort(int numbers[],int count) {
    for (int i = 1; i < count; i++) {
        if (numbers[i] < numbers[i - 1]) {
            int temp = numbers[i];//记录待插入的值
            int left = 0, right = i - 1;
            while (left <= right) {
                int mid = (left + right)/2;
                if (numbers[mid] < temp) {//待插入的值小于中间值
                    left = mid + 1;
                }else {//待插入的值大于中间值
                    right = mid - 1;
                }
            }
            for (int j = i; j > left; j--) {//将目标位置(left)和i位置之间的元素后移一位
                numbers[j] = numbers[j - 1];
            }
            numbers[left] = temp;//插入
        }
    }
}

//调用
    int number1[7] = {2, 2, 23, 11, 9, 43, 18};
    binaryInsertSort(number1, 7);
    for (i = 0; i < 7; i++) {
        printf("%d\n", number1[i]);
    }

• OC实现

- (void)binaryInsertSortWithNumbers:(NSMutableArray *)numbers {
    for (int i = 1; i < numbers.count; i++) {
        if ([numbers[i] intValue] < [numbers[i - 1] intValue]) {
            int temp = [numbers[i] intValue];//记录待插入的值
            int left = 0, right = i - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if ([numbers[mid] intValue] < temp) {//待插入的值小于中间值
                    left = mid + 1;
                }else {//待插入的值大于中间值
                    right = mid - 1;
                }
            }
            [numbers removeObjectAtIndex:i];
            [numbers insertObject:@(temp) atIndex:left];
        }
    }
    NSLog(@"%@",numbers);
}

//调用
NSMutableArray *array = [NSMutableArray arrayWithObjects:@(10),@(4),@(8),@(6),@(16),@(19),@(3), nil];
[self binaryInsertSortWithNumbers:array];

• 时间复杂度

最好的时间复杂度O(logn)。
最坏和平均时间复杂度O(n^2)。

• 算法稳定性

是稳定的排序算法。