插入排序

写在前面的话:

首先,这次的博客发表于早上1:27,算是熬夜了吧,其实这次的文章是之前挖的坑,但是中间又是隔了好几天,才发表出来,又凸显出自己的效率问题。其主要原因即是因为周末两天又自己荒废掉,而我之前想到一个对自己的惩罚措施,就是熬夜学习,既为了让自己印象深刻,又希望能够稍微对自己内心的愧疚有些弥补,原本惩罚是应该放于昨天的,可是昨天熬到12点的时候就完全不行了,真的可以说是心力交瘁,所以就睡下了,而今天就来接受这次的惩罚吧。

可能自己会意识到一个问题,总结的博客中,有关自己思想的东西不是特别多,基本上都是按照教材上的知识点自己敲了一遍,我承认这是自己所存在的一个问题,我意识到自己海绵式思维运用的不错,但淘金式思维,亦或者是想象力不足,我不明白这是智商的问题,还是自己思维的问题,但是前期的话,我还是希望自己先坚持下去,在这个过程中去寻找改变的突破口,去努力,去成长。

正文部分:

排序在日常生活中运用很广泛,而且也是数据结构中比较重要的知识,在接下来的一些内容中,我将整理总结最常见、也是我们必须要掌握的几类算法。

排序是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。其目的是便于我们的查找,可以通过排序算法的时间效率、空间效率、稳定性来衡量一个算法的好坏。

排序可分为内部排序外部排序,又可以将内部排序大致分为插入类、交换类、选择类、归并类、分配类,这一小节中,我主要介绍几类常见的插入排序算法

插入排序

基本思想:

每一趟将一个待排序的记录,按其关键字的大小插入到已经排好序的一组记录的适当位置上,直到所有待排序记录全部插入为止。

三种常见的插入排序算法:直接插入排序、折半插入排序、希尔排序。

直接插入排序

基本操作:

将一条记录插入到已排好序的有序表中,从而得到一个新的、记录数量增1的有序表。

数据类型定义:

1
2
3
4
5
6
7
8
9
10
11
12
#define MAXSIZE 20				//顺序表的最大长度
typedef int KeyType; //定义关键字为整数型

typedef struct { //定义每个数据元素的结构
KeyType key; //关键字项
InfoType otherinfo; //其他数据项
}RedType;

typedef struct { //定义顺序表结构
RedType r[MAXSIZE+1]; //存储顺序表的向量
int length; //顺序表长度
}SqList;

算法实现:

1
2
3
4
5
6
7
8
9
10
11
void InsertSort(SqList &L)	{
int i,j;
for (i=2;i<=L.length;++i)
if (L.r[i].key<L.r[i-1].key) {
L.r[0]=L.r[i]; //复制为哨兵
L.r[i]=L.r[i-1];
for (j=i-2;L.r[0].key<L.r[j].key;--j)
L.r[j+1]=L.r[j]; //记录后移
L.r[j+1]=L.r[0];
}
}

性能分析:

  • 时间复杂度为$O(n^2)$
  • 空间复杂度为$O(1)$
  • 适用于初始记录基本有序的情况,稳定排序

折半插入排序

算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void BInsertSort(SqList &L)	{
for (i=2;i<=L.length;++i) {
L.r[0]=L.r[i];
low=1;high=i-1; //置查找区间初值
while (low<=high) { //折半查找插入位置
m=(low+high)/2;
if (L.r[0].key<L.r[m].key)
high=m-1;
else
low=m+1;
} //循环结束后,插入位置已确认
for (j=i-1;j>=high+1;--j)
L.r[j+1]=L.r[j]; //记录后移,空出插入位置
L.r[high+1]=L.r[0]; //插入数据
}
}

性能分析:

  • 时间复杂度为$O(n^2)$
  • 空间复杂度为$O(1)$
  • 适用于初始记录无序,n较大的情况,稳定排序

希尔排序

算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void ShellInsert(SqList &L,int dk)	{
//对顺序表L做一趟增量为dk的希尔插入排序
for (i=dk+1;i<=L.length;++i)
if (L.r[i].key<L.r[i-dk].key) {
L.r[0]=L.r[i];
for (j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)
L.r[j+dk]=L.r[j];
L.r[j+dk]=L.r[0];
}
}

void ShellSort(SqList &L,int dt[],int t) {
//按增量序列dt[0,t-1]对顺序表L作t趟希尔排序
for (k=0;k<t;++k)
ShellInsert(L,dt[k]);
}

性能分析:

  • 时间复杂度大致范围是$O(n^{1.25})-O(1.6n^{1.25})$
  • 空间复杂度为$O(1)$
  • 适用于初始记录无序,n较大的情况,不稳定排序
-------------The End-------------