折半插入排序算法 C语言代码达成
发布时间：2022-07-10 15:02:45 所属栏目：语言 来源：互联网
导读：上一节介绍了直接插入排序算法的理论实现和具体的代码实现，如果你善于思考就会发现该算法在查找插入位置时，采用的是顺序查找的方式，而在查找表中数据本身有序的前提下，可以使用折半查找来代替顺序查找，这种排序的算法就是折半插入排序算法。 该算法的
|
上一节介绍了直接插入排序算法的理论实现和具体的代码实现，如果你善于思考就会发现该算法在查找插入位置时，采用的是顺序查找的方式，而在查找表中数据本身有序的前提下，可以使用折半查找来代替顺序查找，这种排序的算法就是折半插入排序算法。 该算法的具体代码实现为： #include <stdio.h> void print(int a[], int n ,int i){ printf("%d:",i); for(int j=0; j<n; j++){ printf("%d",a[j]); } printf("n"); } void BInsertSort(int a[],int size){ int i,j,low = 0,high = 0,mid; int temp = 0; for (i=1; i<size; i++) { low=0; high=i-1; temp=a[i]; //采用折半查找法判断插入位置，最终变量 low 表示插入位置 while (low<=high) { mid=(low+high)/2; if (a[mid]>temp) { high=mid-1; }else{ low=mid+1; } } //有序表中插入位置后的元素统一后移 for (j=i; j>low; j--) { a[j]=a[j-1]; } a[low]=temp;//插入元素 print(a, 8, i); } } int main(){ int a[8] = {3,1,7,5,2,4,9,6}; BInsertSort(a, 8); return 0; } 运行结果为： 1:13752496 2:13752496 3:13572496 4:12357496 5:12345796 6:12345796 7:12345679 折半插入排序算法相比较于直接插入排序算法，只是减少了关键字间的比较次数，而记录的移动次数没有进行优化，所以该算法的时间复杂度仍是 O(n2)。 （编辑：大连站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
站长推荐