数据结构上机——希尔排序（含监视哨版本）

首先要明确一下什么是监视哨
这个词很容易望文生义
错误地认为是监视比较的值
查阅资料才发现
监视哨的意义是防止下标越界，提高速度
在插入排序中，
取用r[0]作为监视哨，就可以在循环中减少一次判断j>0的条件，从而提高速度
而在本题之中，采取五个监视哨的目的在于
希尔排序是跳跃的，最大的区间d[0]是5，所以只要防止j-5<0即可，不过还是存在bug！！
网上也找不到多监视哨的希尔排序，着实烧脑。
经过我半小时+的秃头思考后，发现问题在于监视哨的key值，每个监视哨都必须初始化0，当然作为R[0]的监视哨还担任存储单元的双重使命，也可以不初始化。
自此，程序顺利完成

//希尔排序的程序代码
#include<stdio.h>
//顺序表结构类型定义
typedef int datatype;
typedef struct{
	int key;
	datatype data;
}rectype;
const int N=10;
const int D1=5;

void create(rectype[],int);
void print(rectype[],int);
void shellsort(rectype[],int[]);

int main()
{
    rectype r[N+D1];//D1个元素存放监视哨，N个元素存放记录
    int d[3]={5,3,1};//设置3趟的增量	
	create(r,N);//建立存放记录的顺序表
	printf("排序前的数据：");
	print(r,N);//输出排序前的记录表
	shellsort(r,d);//希尔排序
	printf("排序后的数据：");
	print(r,N);//输出排序后的记录表
}

//建立顺序表
void create(rectype r[],int n)
{
	printf("输入10个整型数：");
	for(int i=0;i<n;i++)
		scanf("%d",&r[D1+i].key);
}

//输出顺序表
void print(rectype r[],int n)
{
	for(int i=0;i<n;i++)
		printf("%5d",r[D1+i].key);
	printf("\n");
}

//添加希尔排序算法
void shellsort(rectype r[],int d[])
{
	
	int i,j,k;
	//监视位置0
	for(i=0;i<D1;i++)
	{
		r[i].key=0;
	} 
	for(k=0;k<3;k++)
	{
		for(i=d[k]+1;i<=N;i++)
		{
			if(r[i+D1-1].key<r[i-d[k]+D1-1].key)
			{
				r[0].key=r[i+D1-1].key;
				j=i-d[k];
				while(r[0].key<r[j+D1-1].key)
				{
					r[j+d[k]+D1-1].key=r[j+D1-1].key;
					j=j-d[k];
				}
				r[j+d[k]+D1-1].key=r[0].key;
			}
		}
	}
}

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
 

文章来源: zstar.blog.csdn.net，作者：zstar-_，版权归原作者所有，如需转载，请联系作者。

原文链接：zstar.blog.csdn.net/article/details/111306307