7.2.2 插入排序之折半插入排序

从直接插入排序的过程中,都进行了两项工作:

①从前面的子表中查找出待插入元素应该被插入的位置;

②给插入位置腾出空间,将待插入元素复制到表中的插入位置。

注意到该算法中,总是边比较边移动元素,下面将比较和移动操作分离出来,即先折半查找出元素的待插入位置,然后再统一地移动待插入位置后的所有元素。

当排序表为顺序存储的线性表时,可以对直接插入排序做如下改造:

由于是顺序存储的线性表,所以查找有序子表时可以用折半查找来实现。

在确定出待插入位置后,就可以统一地后移元素了。

void InsertSort(ElemType A[ ],int n ){

            int i,j,low,high,mid;

            for(i=2;i<=n;i++){//依次将A[2]~A[n]插入到前面已经排序序列

                   A[0]=A[i];//将A[i]暂存到A[0]

                   low=1;high=i-1//设置折半查找的范围

                   while(low<=high){//折半查找(默认递增有序)

                          mid=(low+high)/2;//取中间点

                          if(A[mid].key>A[0].key){

                                   high=mid-1;//查找左半子表

                         }else{

                                   low=mid+1;//查找右半子表

                         }

                   }

                   for(j=i-1;j>=high+1;--j){

                             A[j+1]=A[j];//统一后移元素,空出插入位置

                   }

                   A[high+1]=A[0];//插入操作

            }

}

折半插入排序仅仅减少了比较元素的次数,约为O(nlog2 N),该比较次数与待排序表的初始状态无关,仅取决于表中的元素的个数n;

而元素的移动次数没有改变,它依赖于待排序表的初始状态,因此折半插入排序的时间复杂度仍为O(n^2)。

折半插入排序是一个稳定的排序方法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

聊聊base62与tinyURL

base64大家肯定是很熟悉了,那base62是什么东东,它常被用来做短url的映射。

1392
来自专栏谈补锅

C语言之冒泡排序、选择排序、折半查询、进制查表

2073
来自专栏星汉技术

HIVE内置函数

6846
来自专栏拭心的安卓进阶之路

Java 常用工具类 Collections 源码分析

文章出处 文章出自:安卓进阶学习指南 作者:shixinzhang 完稿日期:2017.10.25 Collections 和 Arrays 是 JDK...

3457
来自专栏lgp20151222

MySql 模糊查询

SQL模糊查询,使用like比较关键字,加上SQL里的通配符,请参考以下:  1、LIKE'Mc%' 将搜索以字母 Mc 开头的所有字符串(如 McBadden...

881
来自专栏互联网大杂烩

二分查找

在对线性表的操作中,经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L,输出为x在L中的位置或者x不在L中的信息。

763
来自专栏专注研发

归并排序(Merge Sort)

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序...

2433
来自专栏自学笔记

Data Structure_数组_栈_队列_链表_霍夫曼数组栈队列链表哈夫曼

这就表示一个数组,这个数组有八个元素存放。对于元素的获取,主要就是通过下标获取,所以索引对于数组是很重要的,这个索引可以是有意义的,也可以是没有意义的。比如ar...

782
来自专栏专注研发

JAVA中Sql时间格式与util时间格式转换

  pst.setDate(1, ;//这里的Date是sql中的::得到的是日期

2555
来自专栏wym

Codeforces Round #483 (Div. 2) D. XOR-pyramid

For an array bb of length mm we define the function ff as

1261

扫码关注云+社区

领取腾讯云代金券