二分法插入排序，简称二分排序，是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left 二分插入排序是稳定的与二分查找的复杂度相同； 最好的情况是当插入的位置刚好是二分位置 所用时间为O(log₂n); 最坏的情况是当插入的位置不在二分位置 所需比较次数为O(n)，无限逼近线性查找的复杂度。 S<=∑n「log₂n「-2^n「log₂n「+1 k= 1 平均时间O(n^2)1. 时间复杂度
2. 算法实现
二分法排序C语言
/* 二分法插入排序的算法源程序*/
#include<stdio.h>
#define MAXNUM 100
typedef int KeyType;
typedef int DataType;
typedef struct
{
KeyType key; /* 排序码字段 */
/*DataType info; 记录的其它字段 */
} RecordNode;
typedef struct
{
int n; /* n为文件中的记录个数，n<MAXNUM */
RecordNode record[MAXNUM];
} SortObject;
void binSort(SortObject * pvector) /* 按递增序进行二分法插入排序 */
{
int i, j, left, mid, right;
RecordNode temp;
RecordNode *data = pvector->record;
for( i = 1; i < pvector->n; i++ )
{
temp = data[i];
left = 0;
right = i-1; /* 置已排序区间的下、上界初值 */
while (left <= right)
{
mid = (left + right)/2; /* mid指向已排序区间的中间位置 */
if (temp.key < data[mid].key)
right = mid-1; /* 插入元素应在左子区间 */
else left = mid+1; /* 插入元素应在右子区间 */
}
for (j = i-1; j >= left; j--)
data[j+1] = data[j]; /* 将排序码大于ki的记录后移 */
if (left != i) data[left] = temp;
}
}
SortObject vector= {10, 49,38,65,97,76,13,27,49,50,101};
int main()
{
int i;
binSort(&vector);
for(i = 0; i < vector.n; i++)
printf("%d ", vector.record[i]);
getchar();
return 0;
}
二分法排序JAVA
public static void advanceInsertSortWithBinarySearch(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int low = 0, high = i - 1;
int mid = -1;
while (low <= high) {
mid = low + (high - low) / 2;
if (arr[mid] > temp) {
high = mid - 1;
} else { // 元素相同时，也插入在后面的位置
low = mid + 1;
}
}
for(int j = i - 1; j >= low; j--) {
arr[j + 1] = arr[j];
}
arr[low] = temp;
}
}
二分法排序Python
# 二分法插入排序是在插入排序的基础上，使用二分法查找将元素插入的方法
# 基本原理：（升序）
# 1.将元素依次放入有序序列中
# 2.取出待排序元素，与有序序列的前半段进行比较
# 3.缩小有序序列范围，进一步划分比较，直至范围内仅有1或2个数字
# 4.将插入值与范围进行比较
# 3.重复实现升序
# 实现过程：外层循环控制循环次数，中层循环实现有序排列，内层循环实现查找插入
import random
# 生成序列
Range = 10
Length = 5
list = random.sample(range(Range),Length)
print('before sort:',list)
# 元素插入
for i in range(1,Length): #从第2个元素开始，插入到前一部分元素中
beg,end = 0,i-1 #定义插入范围
mid = (beg + end) // 2 #定义二分/中间边界
while beg < end: #当边界顺序时，进行二分比较
mid = (beg + end) // 2
if mid == beg: #如果中间值与边界相等，则边界已确定，结束二分
break
#在确定中间与边界不相等时，对边界继续缩小
if list[i] == list[mid]:
break
elif list[i]<list[mid]:
end = mid
else:
beg = mid
#首先确定是否因为找到同值而提前终止
if list[i] == list[mid]:
list.insert(mid, list[i])
list.pop(i + 1)
else:
if beg == end: #如果范围内仅仅有一个值
if list[i] < list[beg]:
list.insert(beg,list[i])
else:
list.insert(beg+1, list[i])
list.pop(i + 1)
elif beg < end: #如果范围内有两值
if list[i] < list[beg]:
list.insert(beg,list[i])
elif list[i] < list[end]:
list.insert(end, list[i])
else:
list.insert(end+1, list[i])
list.pop(i + 1)
else:
print("wrong, start at ",beg,', and end with ',end)
print('after sort:',list)
二分法排序Go语言
// BinaryInsertionSort 二分插入排序
func BinaryInsertionSort(arr []int) {
len := len(arr)
if len < 2 {
return
}
for i := 1; i < len; i++ {
low := 0
high := i
for low <= high {
middle := (low + high) / 2
if arr[middle] > arr[i] {
high = middle - 1
} else {
low = middle + 1
}
}
for j := i - 1; j >= low; j-- {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
return
}
二分法插入排序
2021-11-02|来源：|发布者：