希尔排序
希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
1.排序原理
主要是通过增量的步长来进行分组,然后对每一组进行直接插入排序
<mark>排序过程</mark>
简单示例,例如:
[4 7 3 8 2 6 5 1]
第一趟排序:
步长:step=4 分组:[4 2]、[7,6]、[3 5]、[8 1]
对每一组进行直接插入排序得:[2 4]、[6,7]、[3 5]、[1 8]
整体排序后:[2 6 3 1 4 7 5 8]
第二趟排序:
步长:step=2 分组:[2 3 4 5]、[6 1 7 8]
对每一组进行直接插入排序得:[2 3 4 5]、[1 6 7 8]
整体排序后:[2 1 3 6 4 7 5 8]
第三趟排序:
步长:step=1 分组:[2 1 3 6 4 7 5 8]
对每一组进行直接插入排序得:[1 2 3 4 5 6 7 8]
整体排序后:[1 2 3 4 5 6 7 8]
排序结束
<mark>图示</mark>
2.源代码:
#include<stdio.h>
#define N 10
void ShellSort(int num[],int len)
{
int i,j,temp,step;
for(step=len/2;step>=1;step/=2)//步长间隔每次减半
for(i=step;i<len;i+=step)//按步长遍历数组
{
//插入排序过程
if(num[i]<num[i-step])
{
temp=num[i];
for(j=i-step;num[j]>temp;j-=step)
num[j+step]=num[j];
num[j+step]=temp;
}
}
}
int main()
{
int num[N]={9,8,7,6,5,4,3,2,1,0};
ShellSort(num,N);
for(int i=0;i<N;i++)
printf("%d ",num[i]);
printf("\n");
return 0;
}