排序算法实例
第 3 页 共 13 页
2 折半插入排序
/*
orginal:
[ 0 ] 49 38 65 97 76 13 27 49
sorting...
[ 38 ] 38 49 65 97 76 13 27 49
[ 38 ] 38 49 65 97 76 13 27 49
[ 38 ] 38 49 65 97 76 13 27 49
[ 76 ] 38 49 65 76 97 13 27 49
[ 13 ] 13 38 49 65 76 97 27 49
[ 27 ] 13 27 38 49 65 76 97 49
[ 49 ] 13 27 38 49 49 65 76 97
sorted:
[ 49 ] 13 27 38 49 49 65 76 97
折半插入排序算法的描述：
是直接插入排序的改进，主要在于缩短了查找待排序的元素 data[i]位于有序区的插入点的过程，
由于有序区的元素已经排好序，所以可以通过折半查找的方法快速找到 data[i]应该落入的插入点，其余
过程和直接插入排序方法相同，虽然加快了查找插入点的过程，但是不能减少移动元素的数量。
*/
#include <stdio.h>
void insort(int data[], int length);
void output(int data[], int length);
main()
{
int data[] = { 0, 49, 38, 65, 97, 76, 13, 27, 49 };
printf("orginal:\n");
output(data, sizeof(data) / sizeof(int)); /*显示原始数据*/
printf( "sorting...\n" );
insort(data, sizeof(data) / sizeof(int) - 1); /*显示动态排序的过程*/
printf("sorted:\n");
output(data, sizeof(data) / sizeof(int)); /*输出排序结果*/
}
void insort(int data[], int length)
{
int i, j;
int low, high, mid;
for (i = 2; i <= length; i++) {
if (data[i] < data[i - 1]) {
data[0] = data[i];
// 通过对于有序区的折半查找，找到 data[i]应该落入的插入点
low = 1;
high = i - 1;
while (low <= high) {
mid = (low + high) / 2;
if (data[0] < data[mid])
high = mid - 1;
else
low = mid + 1;
}// 折半查找结束，high+1 所指向的位置应为插入点，
//下面的循环将(i-1)~(high+1)区间的数据依次后移一个位置，腾出 high+1 的所指的位置，将 data[i]存入
for (j = i - 1; j >= high + 1; j--) {
data[j + 1] = data[j];
}
data[j + 1] = data[0];
}
output(data, length + 1);
}
}
void output(int data[], int length) //数据输出函数
{
int i;
剩余12页未读，继续阅读
jocks
- 粉丝: 15
- 资源: 126
我的内容管理
展开
最新资源
- C++标准程序库：权威指南
- Java解惑：奇数判断误区与改进方法
- C++编程必读：20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程：从入门到精通
- Spring3.0权威指南：JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略：从环境配置到索引创建
- 内存虚拟硬盘技术：提升电脑速度的秘密武器
- Java操作数据库：保存与显示图片到数据库及页面
- ISO14001：2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发：触发器与控制器重定向技术详解
- FPGA开发实战指南：创新设计与进阶技巧
- ShopExV4.8二次开发入门：解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
