排序算法2——折半插入排序

大家好，欢迎来到IT知识分享网。

第二趟折半插入排序过程如图2所示：

以上两趟排序过程可以看出，折半排序与直接插入排序的区别仅仅在于查找插入位置的方法不同。一般情况下，折半查找的效率要高于顺序查找的效率。

code:

#include<stdio.h> #include <iostream> using namespace std; void PrintArray(int a[], int n); void main() { int a[] = { 75,61,82,36,99,26,41 }; int t, i, j, low, high, mid, n; n = sizeof(a) / sizeof(a[0]); printf("折半插入排序前:\n"); PrintArray(a, n); printf("折半插入排序:\n"); for (i = 1; i < n; i++) { t = a[i]; for (low = 0, high = i - 1; high >= low;) { mid = (low + high) / 2; if (t < a[mid]) high = mid - 1; else low = mid + 1; } for (j = i - 1; j >= low; j--) a[j + 1] = a[j]; a[low] = t; PrintArray(a, n); } system("pause"); } void PrintArray(int a[], int n) { int i; for (i = 0; i < n; i++) printf("%4d", a[i]); printf("\n"); }

结果：

首页 博客 学院 下载 论坛 APP 问答 商城 活动 VIP会员 专题 招聘 ITeye GitChat 图文课 疯狂Python精讲 写博客 消息 Markdown编辑器 富文本编辑器 查看主页 内容 文章管理 专栏管理 评论管理 个人分类管理 博客搬家 数据 百度关键词 自定义百度统计 设置 博客设置 自定义域名 博客模块管理 CSDN博客交流群 打开手机扫码 或点击这里加入群聊 客服 排序算法2.1——插入排序的链式实现 18/100 文章标签： 插入排序 数据结构与算法 添加标签 最多添加5个标签 个人分类： 插入排序 数据结构与算法 添加新分类 文章类型： * 博客分类： * 申请原创将启用（Creative Commons ）版权模板，如果不是原创文章，请选择转载或翻译 发布形式： void InsertSort(LinkList L) { ListNode *p=L->next,*pre,*q; L->next=NULL; while(p!=NULL) { if(L->next==NULL) { L->next=p; p=p->next; L->next->next=NULL; } else { pre=L; q=L->next; while(q!=NULL&&q->data<p->data) { pre=q; q=q->next; } q=p->next; p->next=pre->next; pre->next=p; p=q; } } }