折半插入排序算法(C语言代码实现)
上一节介绍了直接插入排序算法的理论实现和具体的代码实现,如果你善于思考就会发现该算法在查找插入位置时,采用的是顺序查找的方式,而在查找表中数据本身有序的前提下,可以使用折半查找来代替顺序查找,这种排序的算法就是折半插入排序算法。
该算法的具体代码实现为:
折半插入排序算法相比较于直接插入排序算法,只是减少了关键字间的比较次数,而记录的移动次数没有进行优化,所以该算法的时间复杂度仍是
该算法的具体代码实现为:
#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
2:13752496
3:13572496
4:12357496
5:12345796
6:12345796
7:12345679
折半插入排序算法相比较于直接插入排序算法,只是减少了关键字间的比较次数,而记录的移动次数没有进行优化,所以该算法的时间复杂度仍是
O(n2)
。所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频