插入排序算法实现（二分查找搜索版本）

我来为你写一个完整的C语言二分插入排序程序。

#include<stdio.h>// 二分查找插入位置intbinarySearch(intarr[],intleft,intright,intkey){while(left<=right){intmid=left+(right-left)/2;if(arr[mid]==key){returnmid+1;// 保持稳定性，插入到相同元素的后面}elseif(arr[mid]<key){left=mid+1;}else{right=mid-1;}}returnleft;// 返回插入位置}// 二分插入排序voidbinaryInsertionSort(intarr[],intn){for(inti=1;i<n;i++){intkey=arr[i];// 当前要插入的元素intj=i-1;// 使用二分查找找到插入位置intpos=binarySearch(arr,0,j,key);// 将插入位置之后的元素后移while(j>=pos){arr[j+1]=arr[j];j--;}// 插入元素arr[pos]=key;}}// 打印数组voidprintArray(intarr[],intn){for(inti=0;i<n;i++){printf("%d ",arr[i]);}printf("\n");}intmain(){intarr[]={64,34,25,12,22,11,90,88,75,50};intn=sizeof(arr)/sizeof(arr[0]);printf("原始数组: ");printArray(arr,n);binaryInsertionSort(arr,n);printf("排序后数组: ");printArray(arr,n);return0;}

程序说明：

1. 算法思想

· 将数组分为已排序和未排序两部分
· 对未排序部分的每个元素，使用二分查找在已排序部分找到插入位置
· 然后移动元素并插入

2. 时间复杂度

· 最好情况：O(n) - 数组已经有序时
· 平均情况：O(n²) - 但比较次数比普通插入排序少
· 最坏情况：O(n²) - 但移动元素的次数与普通插入排序相同

3. 空间复杂度

· O(1) - 原地排序，只需要常数级别的额外空间

4. 优化点

· 使用二分查找减少比较次数（从O(n)降到O(log n)）
· 但元素移动的次数没有减少

5. 变种版本（更简洁的实现）：

// 更紧凑的实现方式voidbinaryInsertionSortCompact(intarr[],intn){for(inti=1;i<n;i++){intkey=arr[i];intleft=0,right=i-1;// 二分查找插入位置while(left<=right){intmid=left+(right-left)/2;if(arr[mid]>key){right=mid-1;}else{left=mid+1;}}// 移动元素for(intj=i-1;j>=left;j--){arr[j+1]=arr[j];}// 插入元素arr[left]=key;}}

6. 使用示例

intmain(){// 测试示例1intarr1[]={3,1,4,1,5,9,2,6,5,3};intn1=sizeof(arr1)/sizeof(arr1[0]);printf("示例1 - 原始数组: ");printArray(arr1,n1);binaryInsertionSort(arr1,n1);printf("示例1 - 排序后: ");printArray(arr1,n1);// 测试示例2intarr2[]={100,64,34,25,12,22,11,90};intn2=sizeof(arr2)/sizeof(arr2[0]);printf("\n示例2 - 原始数组: ");printArray(arr2,n2);binaryInsertionSort(arr2,n2);printf("示例2 - 排序后: ");printArray(arr2,n2);return0;}

这个二分插入排序相比普通插入排序的主要优点是减少了比较次数，特别是当数组较大时，这个优势会更明显。