生活中时常需要用到排序:对班上成绩的高低排序,人的身高排序,对不同餐饮商家根据好评的高度进行排序...
接下来我会分两期介绍排序算法,不同的排序算法的时间和空间复杂度都有不同,我会在最后进行统一的计算。
1、插入排序
当我们在玩斗地主的时候,就会使用到插入排序,每次我们抽到一张牌,都需要在已有的牌中找到前一张牌比抽到牌小,且后一张牌比抽到的牌大的位置进行插入。
基本的思想就是,我们假设现在抽到第i张牌,并且前i-1张牌已经有序了,按照前面的思路。在前i-1个数中找到前一个数比第i个数小,并且后一个数比第i个数小的位置,插入第i个数。
这样就能保证i个数有序,不断归纳下去,最后抽到的牌总是有序的。
具体代码的实现是:定义一个tmp为第i个位置,End为第i-1个,将前i-1个数逐一和tmp比较,如果比tmp来的大,就往后移一位,然后End减-1往前走,这样就能比较完前i-1个数。
我们不妨先写一个单次的排序,再考虑整体排序。
void InsertSort(int* a, int n)
{
//单趟的排序
int End = n - 2;
int tmp = a[n-1];
while (End >= 0)
{
if (a[End] > tmp)
{
a[End + 1] = a[End];
End--;
}
else
{
a[End+1] = tmp;//不满足条件就在End 后面插入tmp
break;
}
}
}
这样还有一点小问题,就是End等于0如果进到第一个循环内部,那么End减一以后小于0,跳出循环后,数并没有插入。
我们可以这样修改,不管是循环跳出,还是进入else条件,都要在End后面插入,不妨直接在while循环后面插入。
void InsertSort(int* a, int n)
{
//单趟的排序
int End = n - 2;
int tmp = a[n-1];
while (End >= 0)
{
if (a[End] > tmp)
{
a[End + 1] = a[End];
End--;
}
else
{
break;
}
}
a[End+1] = tmp;//不满足条件就在End 后面插入tmp
}
整体的循环我们不能从最后一个开始,因为我们排第i个数的前提是前i-1个数需要有序,所以必须从头排序,保证前面的数有序。
void InsertSort(int* a, int n)
{
for(int i = 1;i= 0)
{
if (a[End] > tmp)
{
a[End + 1] = a[End];
End--;
}
else
{
break;
}
}
a[End+1] = tmp;//不满足条件就在End 后面插入tmp
}
}
我们拿一个数组来测试一下:
我们浅计算一下它的时间复杂度,考虑最坏的情况,如果数组是逆序,那么第i个数都要比较i-1次,加和后的时间复杂度是O(N^2)。如果数组已经是有序,或者是部分有序,那么这种情况下的插入排序效率很高,是O(N)。
所以我们如果想要提高插入排序的效率,要做的就是让数组部分有序。
2.希尔排序(Shell Sort)
希尔排序是在插入排序的基础上进行了一步预处理,而预处理的目的,就是为了达到数组的部分有序。
预排序的步骤就是把一个数组分成gap组,下面我们先假设gap = 3,对这gap个组的数据分别进行插入排序。
如果gap比较大,就可以让大的数据很快的到后面,当我们的数据个数不断加大,开始的时候需要gap很大,后面逐渐让gap变小,最后可以达到基本有序。
单趟排序的思路和上面的插入排序一样——
for (int i = 0;i < n - gap;++i)
{
int End = i;
int tmp = a[End + gap];
while (End >= 0)
{
if (a[End] > tmp)
{
a[End + gap] = a[End];
End -= gap;
}
else
{
break;
}
}
a[End + gap] = tmp;
}
实际上gap的取法很多样,这导致了希尔排序的时间复杂度十分难计算。我们每次循环都让gap模3加1——这样能保证最后一次gap必定是1,从而是插入排序。
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap/3 +1;
for (int i = 0;i < n - gap;++i)
{
int End = i;
int tmp = a[End + gap];
while (End >= 0)
{
if (a[End] > tmp)
{
a[End + gap] = a[End];
End -= gap;
}
else
{
break;
}
}
a[End + gap] = tmp;
}
}
接下来引用殷人昆老师的数据结构书中的一段分析:
我们对gap的取法和Knuth一样,所以时间复杂度大概在O(N^1.25)~O(1.6*O^1.25)。这相对插入排序已经优化了很多。



