希尔排序（含监视哨）

希尔排序（含监视哨）

希尔排序（含监视哨）
原理希尔排序称为缩小增量排序，就是将一串数字分为若干子序列分别进行直接插入排序。希尔排序需要取一间隔值，一般为输入数字的一半，然后每趟变为之前间隔值的一半。
如输入8个数字，那间隔值为8/2第二趟就为4/2如此类推。
安装监视哨方法设置一个为r[9]大小的数组，而输入数字从r[1]开始，这样r[0],就空出来没有用，就可以作为监视哨了。不用担心监视哨的值是否丢失的问题，因为我们是从r[1]开始数的。
以下为代码：
#include<stdio.h>
#define key 9
void main()
{
int n=key-1,i, r[key];
int j,d=n/2;
for (i = 1; i <key; i++)//输入八个数字
scanf_s(“%d”, &r[i]);
while (d > 0)
{
for (i = d; i < key; i++)
{
r[0] = r[i];//存入监视哨
j = i - d;//前面的一个数字是间隔d注意
while (j>0&&r[0] < r[j])
{
r[j + d] = r[j];
j = j - d;//往前比较与直接插入排序一样
}
r[j + d] = r[0];//将值放到正确位置
}
d = d / 2;
}
for (i = 1; i < key; i++)
printf(“%4d”, r[i]);
}
输出的结果

-1 25 45 96 58 -36 -789 96
-789 -36 -1 25 45 58 96 96
D:数据结构希尔排序Debug希尔排序.exe (进程 11028)已退出，代码为 0。
按任意键关闭此窗口. . .