插入排序
void insert_sort()
{
for(int i = 1;i < n;i ++)
for(int j = i; j >= 1 && q[j] < q[j - 1];j --)
swap(q[j],q[j - 1]);
}
测试代码效果,请移步快速排序
希尔排序1(439ms)
先上代码模板
void shell_sort()
{
int gap = n / 2;
while(gap)
{
for(int i = gap;i < n;i ++)
for(int j = i;j >= gap && q[j] < q[j - gap];j -= gap)
swap(q[j],q[j - gap]);
gap /= 2;
}
}
上述模板使用的递减序列为
$$
\lceil \frac{N}{2} \rceil,\lceil \frac{N}{4} \rceil,\lceil \frac{N}{8} \rceil,\cdots,1\tag{1}
$$
此时最坏情况下时间复杂度为$\Theta(N^2)$
解释
具体而言,$N=2^p$,我们可以构造两个长度皆为$2^{p-1}$的序列
$$
\begin{align}
&a_1,a_2,\cdots,a_{2^{p-1}}\\\\
&b_1,b_2,\cdots,b_{2^{p-1}}
\end{align}
$$
满足两端序列皆递增,且$a_{2^{p-1}}<b_1$,考虑使用shell_sort排序以下序列
$$
a_1,b_1,a_2,b_2,\cdots,a_{2^{p-1}},b_{2^{p-1}}
$$
我们可以看到仅gap=1时才进行排序,所有仅仅只是做了一次插入排序,所以为$\Theta(N^2)$
希尔排序2(413ms)
采用增量序列
$$
1,4,13,40,121,\cdots,
$$
注意上述序列最大值不大于$\lceil \frac{N}{3}\rceil$,最坏时间复杂度$\Theta(N^{\frac{3}{2}})$
void shell_sort()
{
int gap = 1;
while(gap < n / 3) gap = 3 * gap + 1;
while(gap)
{
for(int i = gap;i < n;i ++)
for(int j = i;j >= gap && q[j] < q[j - gap];j -= gap)
swap(q[j],q[j - gap]);
gap /= 3;
}
}
希尔排序3(465ms)
最坏情况下$\Theta(n\log^2n)$
使用序列
$$
1,2,3,4,6,8,12,\cdots
$$
对于推导上述序列,这里给出代码(枚举),不过,(╯°□°)╯︵ ┻━┻,为啥跑出的效果没有第一个希尔排序代码好
void shell_sort()
{
g[1] = 1;// g存储2^p3^q序列,空间需要开大一点
int k = 1,p1 = 1,p2 = 1;
while(g[k] <= n)
{
int f1 = 2 * g[p1],f2 = 3 * g[p2];
if(f1 < f2) g[++ k] = f1,p1 ++;
else if(f1 > f2) g[++ k] = f2,p2 ++;
else g[++ k] = (f1,f2),p1 ++,p2 ++;
}
while(k >= 1)
{
int gap = g[k];
for(int i = gap;i < n;i ++)
for(int j = i;j >= gap && q[j] < q[j - gap];j -= gap)
swap(q[j],q[j - gap]);
k--;
}
}
总之第3个序列的表现我是没想通(┬┬﹏┬┬)