今天刚参加了华中师范大学的ACM新生杯,趁着还保持着对算法的敏感度(虽然今天A的题没有几道是真正的算法题),来写一篇关于插入排序及其升级版算法希尔排序的介绍
部分内容取自于知乎用户彭湖湾的文章
概念
插入排序即将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据。一般此算法时间复杂度较高,故适用于少量数据的排序
插入排序(1.0)
插入排序1.0即直接插入排序,将已知有序序列遍历一遍,以找到插入元素的位置,将该位置面的元素全部向后移动一位。
具体实现步骤:(对待插入元素)
- 和相邻的左边元素的值比较大小
- 如果左边元素大于待排序元素,则交换两者的值,左边元素的值“右移”一位。
- 如果左边元素小于等于待排序元素,说明已经插入到“合适位置”了,一趟插入结束。
示例如下图:
时间复杂度:
实现代码如下:
//a[0]中存的是a数组的长度
void insertsort(int *a)
{
n = a[0];
for(int i=2;i<=n;i++)
{
int t = a[i];
int j = i;
while(j>0&&t<a[j-1])
{
a[j]=a[j-1];
j--;
}
a[j]=t;
}
}
插入排序(2.0)
插入排序2.0即对待插入元素在已知有序序列中找到位置的过程进行了优化。
既然序列是已知的、有序的,那么我们自然可以想到在这过程中使用二分法。
代码如下:
//x是待插入元素的值
void binaryq(int *a,int l,int r,int x)
{
int mid;
while(l<=r)
{
mid = (l+r)/2;
if(x>a[mid])
{
l = mid+1;
}else{
r = mid-1;
}
}
return l;
}
void insertsearch2(int *a)
{
int n = a[0];
for(int i=2;i<=n;i++)
{
int t = a[i];
int l = binaryq(a,0,i-1,a[i]);
for(int j=i;j>l;j--)
{
a[j]=a[j-1];
}
a[l]=t;
}
}
希尔排序(插入排序 3.0)
希尔排序又被称为步长递减插入排序或增量递减插入排序。
设h为步长,那么希尔排序的基本步骤为:
- 选择一个递增序列。并在递增序列中,选择小于数组长度的最大值,作为初始步长 h。
- 开始的时候,将数组分为h个独立的子数组(1中h), 每个子数组中每个元素等距离分布,各个元素距离都是h。
- 对2中分割出的子数组分别进行插入排序
- 第一轮分组的插入排序完成后,根据递增序列(逆向看)减少h的值并进行第二轮分组, 同样对各个子数组分别插入排序。 不断循环1、2、4, 直到h减少到1时候, 进行最后一轮插入排序,也就是针对整个数组的直接插入排序(这个时候分组只有1个,即整个数组本身)
- 一开始的时候h的值是比较大的(例如可以占到整个数组长度的一半),所以一开始的时候子数组的数量很多,而每个子数组长度很小。 随着h的减小,子数组的数量越来越少,而单个子数组的长度越来越大。
代码如下:
void shellsort(int *a)
{
int n = a[0];
int h = 1;
while(h<n/3)h=3*h+1;//选择步长
while(h>=1)
{
for(int i=h;i<=n;i++)
for(int j=i;j>=h;j-=h)
if(a[j]<a[j-h])
{
int t=a[j];
a[j]=a[j-h];
a[j-h]=t;
}
h/=3;
}
}
希尔排序图示
时间复杂度:
本文章到此为止,谢谢阅读