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

算法2——折半插入排序"/>

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

编写折半插入排序算法，对元素序列 75、61、82、36、99、26、41进行从小到大排序。
【算法思想】
折半插入排序算法是对直接插入排序的一种改进。主要思想是在查找插入位置过程中引入折半查找算法思想，利用折半查找法在有序集中确定待排序元素插入位置。

【与直接插入排序的区别】
*直接插入排序：从右到左按照顺序查找插入的位置。
*折半插入排序：在有序集中查找插入的位置。
【示例】
假设有7个待排序元素：75、61、82、36、99、26、41。使用折半插入排序算法对该元素序列进行第1趟排序过程，如图1所示。

其中i=1表示第一趟排序，待排序元素为a[1]，t存放的是待排元素。当low>high时，low指向元素要插入的位置。依次将low---i-1之间的元素依次向后移一个位置，然后将t的值插入到a[low]中。

第二趟折半插入排序过程如图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;elselow = 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");
}

结果：

【插入排序的链式实现】
L指向有序链表，p指向待排序链表。初始时，令L->next=NULL，即有序链表为空。若有序链表为空，则将p指向的结点直接插入空链表中。然后将p指向的第二个结点与L所指链表中的每一个结点比较，并将结点*p插入到L所指链表的相应位置，使其按有序排序。重复上述操作，直到待排序链表中所有结点都插入L所指向的链表，此时L就成为一个有序链表。

首页
博客
学院
下载
论坛
APP
问答
商城
活动
VIP会员专题
招聘
ITeye
GitChat
图文课
疯狂Python精讲
写博客 消息Markdown编辑器
富文本编辑器
查看主页
内容
文章管理
专栏管理
评论管理
个人分类管理
博客搬家
数据
百度关键词
自定义百度统计
设置
博客设置
自定义域名
博客模块管理CSDN博客交流群打开手机QQ扫码
或点击这里加入群聊QQ客服排序算法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;}}
}

【主要用途】
折半排序算法与直接排序算法一样，通常也用于待排序元素的个数较少的情况。如果待排序序列基本有序，则最好采用直接插入排序算法。
【稳定性与复杂度】
折半排序也是一种稳定的排序算法。通常折半排序在查找插入的位置时改进了查找算法，减少了比较次数，但是移动元素的时间复杂度仍然没有变，因此折半排序算法的整体时间复杂度仍然为O(n*n)。空间复杂度为O(1)。