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

希尔排序思想不难理解，不过题目难点在于，要设计D1（5）个监视哨，为了先实现一下希尔排序算法，首先采用了课本上无监视哨的版本，因此把题目的代码稍改了一下，仅用第一个R【0】作为暂存单元。
有监视哨的版本稍后更新（如果想出来的话）

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

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

int main()
{
    rectype r[N+1];//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[i+1].key);
}

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

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

  

 

  
 
 

  
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
 

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

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