- 简介
二分法插入排序，简称二分排序，是在插入第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)。
- 算法稳定性
是稳定的排序算法。
