折半插入排序算法(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)
。所有教程
- C语言入门
- C语言编译器
- C语言项目案例
- 数据结构
- C++
- STL
- C++11
- socket
- GCC
- GDB
- Makefile
- OpenCV
- Qt教程
- Unity 3D
- UE4
- 游戏引擎
- Python
- Python并发编程
- TensorFlow
- Django
- NumPy
- Linux
- Shell
- Java教程
- 设计模式
- Java Swing
- Servlet
- JSP教程
- Struts2
- Maven
- Spring
- Spring MVC
- Spring Boot
- Spring Cloud
- Hibernate
- Mybatis
- MySQL教程
- MySQL函数
- NoSQL
- Redis
- MongoDB
- HBase
- Go语言
- C#
- MATLAB
- JavaScript
- Bootstrap
- HTML
- CSS教程
- PHP
- 汇编语言
- TCP/IP
- vi命令
- Android教程
- 区块链
- Docker
- 大数据
- 云计算