希尔排序

希尔排序(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;
}