排序算法详解（一）(二)

49 49 97

二趟排序结果 13 04 49 38 27 49 55 65 97 76 第二趟排序增量为3

第三趟排序 04 13 27 38 49 49 55 65 76 97

下面我们来看运用希尔排序的一个小例子，更加有助于大家对于希尔排序的理解：

[cpp]
#include

#define N 100
int L[N];

void ShellInsert(int n,int dk)
{
int i,j;
for(i=dk+1;i<=n;i++)
{
if(L[i] L[0] = L[i];
for(j=i-dk;j>0&&L[0] L[j+dk] = L[j];
L[j] = L[0];
}
}

void Shellsort(int n,int dlta[],int t)
{
int k,i;
for(k=0;k ShellInsert(n,dlta[k]);
for(i=1;i<=n;i++)
printf("L[%d]=%d\n",i,L[i]);
}

int main()
{
int i,n,t,dlta[5]={5,3,1};
scanf("%d",&n);
scanf("%d",&t);
for(i=1;i<=n;i++)
scanf("%d",&L[i]);
Shellsort(n,dlta,t);
return 0;
}
希尔排序的时间复杂度为O(n*ln n)。
由上面的算法可以看出，直接插入排序是稳定的排序算法，而希尔排序是不稳定的排序算法。

上面就是插入排序的一个大概的讲解，下面我们还将进行余下排序算法的讲解。