折半插入排序（Binary Insertion Sort）是对插入排序算法的一种改进，所谓排序算法过程，就是不断的依次将元素插入前面已排好序的序列中。
排序思想：有一组数据待排序，排序区间为Array[0]~Array[n-1]。将数据分为有序数据和无序数据，第一次排序时默认Array[0]为有序数据，Array[1]~Array[n-1]为无序数据。有序数据分区的第一个元素位置为low，最后一个元素的位置为high。
遍历无序区间的所有元素，每次取无序区间的第一个元素Array[i]，因为0~i-1是有序排列的，所以用中点m将其平分为两部分，然后将待排序数据同中间位置为m的数据进行比较，若待排序数据较大，则low~m-1分区的数据都比待排序数据小，反之，若待排序数据较小，则m+1~high分区的数据都比 待排序数据大，此时将low或high重新定义为新的合适分区的边界，对新的小分区重复上面操作。直到low和high 的前后顺序改变，此时high+1所处位置为待排序数据的合适位置。
时间复杂度：O(n^2)
稳定性：稳定。
#include
#include
int *Array; /*Array是一个int 型地址，指向数组的首地址。*/ int Count; /*Count用来存储所要排序的数字的数目。*/ /*建立未排序数组*/ void CreateArray() { int i; /*创建数组必须用常量分配，而我们事先并不知道要处理的数据个数，所以用malloc动态分配数组单元。*/ Array = (int *)malloc(sizeof(int)*Count); for (i = 0; i < Count; i++) { printf("Please enter an integer of NO.%d to sort:\n",i+1); scanf("%d",&Array[i]); } } /*输出已排序数组*/ void Print() { int i; for (i = 0; i < Count; i++) { printf(" %d ",Array[i]); } printf("\n"); } /*折半插入排序升序排列*/ void BinaryInsertSortup() { int i,j,x,m; /*i,j均为循环变量，x用来存储当前待排序的数据，m充当比较区间的中点*/ int low,high; /*low代表要与Array[i]进行比较的有序区间的第一个元素所在位置。 high代表要与Array[i]进行比较的有序区间的最后一个元素所在位置。*/ for (i = 1; i < Count; i++) { x = Array[i]; low = 0; /*第一次划分有序比较区间，比较区间的第一个元素所在位置为0*/ high = i-1; /*第一次划分有序比较区间，比较区间的最后一个元素所在位置为n-1*/ /*比较查找Array[i]合适插入的位置*/ while (low <= high) { m = (low + high)/2; if (x >= Array[m]) { low = m+1; } else { high = m-1; } } /*确定好位置后，将位置之后的数据后移，插入待排序数据*/ for (j = i-1;j > high; j--) { Array[j+1] = Array[j]; } Array[j+1] = x; } } /*折半插入排序降序排列*/ void BinaryInsertSortdown() { int i,j,x,m; /*i,j均为循环变量，x用来存储当前待排序的数据，m充当比较区间的中点*/ int low,high; /*low代表要与Array[i]进行比较的有序区间的第一个元素所在位置。 high代表要与Array[i]进行比较的有序区间的最后一个元素所在位置。*/ for (i = 1; i < Count; i++) { x = Array[i]; low = 0; /*第一次划分有序比较区间，比较区间的第一个元素所在位置为0*/ high = i-1; /*第一次划分有序比较区间，比较区间的最后一个元素所在位置为n-1*/ /*比较查找Array[i]合适插入的位置*/ while (low <= high) { m = (low + high)/2; if (x <= Array[m]) { low = m+1; } else { high = m-1; } } /*确定好位置后，将位置之后的数据后移，插入待排序数据*/ for (j = i-1;j > high; j--) { Array[j+1] = Array[j]; } Array[j+1] = x; } } int main(void) { int i; printf("Please enter the number of Numbers to sort:\n "); scanf("%d",&Count); CreateArray(); /*创建数组用来存储将要排序的数。*/ /*插入排序法*/ BinaryInsertSortup(); /*折半插入排序*/ printf("升序排列\n"); Print(); BinaryInsertSortdown(); /*折半插入排序*/ printf("降序排列\n"); Print(); return 0; }
图示：以i=4时为例：
第一步
第二步
第三步：
第四步：
第五步：
第六步：
第七步：
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/204438.html原文链接：https://javaforall.net
