数据结构笔记 - 排序算法希尔排序算法

发布于 2011-09-21 | 更新于 2020-09-20

希尔排序：

将相距一个增量单位的元素集组成一个子集，然后通过以子集为单位对数据进行比较，最后得到子集间的数据是有序的，但是子集内德数据还未排序。这样继续缩小增量循环比较进行互换位置处理，直到增量变为1时为最后一次循环比较。

希尔排序算法突破了O(n^2)的时间复杂度。

#include <stdio.h>

#define MAXSIZE 100  /* 待排序数组的大小 */

typedef struct
{
	int r[MAXSIZE+1];	/* 待排序数组r，r[0]为哨兵或临时变量 */
	int length;			/* 待排序数组的长度，为了方便理解，不包含r[0]元素 */
}SortList;

/* 希尔排序算法 */
void ShellSort(SortList *L)
{
	int i,j,k=0;
	/* 初始化增量为待排序数组的长度 */
	int increment=L->length;
	do
	{
		/* 设置增量 */
		increment=increment/3+1;
		for(i=increment+1; i<=L->length; i++)
		{
			/* 比较r[i]与r[i-increment]的值，即相差一个增量的元素相互比较 */
			if (L->r[i]<L->r[i-increment])
			{
				/* r[i]记录暂存到r[0]中 */
				L->r[0]=L->r[i];
				for(j=i-increment; j>0 && L->r[0]<L->r[j]; j-=increment) {
					L->r[j+increment]=L->r[j];
				}
				L->r[j+increment]=L->r[0];	/* 插入到相应位置 */
			}
		}
	}
	while(increment>1);
}