希尔排序 C语言实现

深藏阁楼爱情的钟 2022-12-22 09:53 125阅读 0赞

### 希尔排序 ###

希尔排序( Shell’s Sort)又称“缩小增量排序”( Diminishing Increment Sort)，是插入排序的一种， 因D.L.Shell 于1959 年提出而得名。  
直接插人排序，当待排序的记录个数较少且待排序序列的关键字基本有序时，效率较高。希尔排序基于以上两点，从“减少记录个数”和“序列基本有序”两个方面对直接插入排序进行了改进。

**基本思想：**

先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

**希尔排序算法，特点:**

1)缩小增量  
2)多遍插入排序

**算法步骤：**

希尔排序实质上是采用分组插人的方法。先将整个待排序记录序列分割成几组，从而减少参与直接插入排序的数据量，对每组分别进行直接插人排序，然后增加每组的数据量，重新分组。这样当经过几次分组排序后，整个序列中的记录“基本有序”时，再对全体记录进行一次直接插人排序。  
希尔对记录的分组，不是简单地“逐段分割”，而是将相隔某个“增量”的记录分成一组。

（1）第一趟取增量 d 1 d\_1 d1 ( d 1 d\_1 d1<n)把全部记录分成 d 1 d\_1 d1个组，所有间隔为 d 1 d\_1 d1的记录分在同一组，在各个组中进行直接插人排序。  
（2）第二趟取增量 d 2 d\_2 d2 ( d 2 d\_2 d2< d 1 d\_1 d1), 重复上述的分组和排序。  
（3）依次类推，直到所取的增量 d t d\_t dt=1 ( d t d\_t dt< d t − 1 d\_\{t-1\} dt−1<…< d 2 d\_2 d2< d 1 d\_1 d1)， 所有记录在同一组中进行直接插入排序为止。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
**时间复杂度**

O( n 1.3 n^\{1.3\} n1.3)

**空间复杂度**

O(1)

**稳定性**

不稳定 *（如图中“上划线49”和“49”的相对位置在排序前后变了，故不稳定）*

**完整代码如下：**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 100 //顺序表最大容量，可以自行加大 
    
    typedef struct 
    { 
    	int key;//关键字项 
    	char *otherinfo;//其他数据项 
    }ElemType;//记录类型 
    typedef struct
    { 
    	ElemType Data[MAXSIZE+1];//静态顺序表的数据域，这里Data[0]为空闲或者为哨兵单元 
    	int length;//顺序表的长度 
    }SqList;//顺序表 
    
    void InitList(SqList &L)//顺序表的初始化 
    { 
    	L.length = 0;//使顺序表长度归0，便是顺序表的初始化 
    }
    
    void CreateList(SqList &L)//顺序表的创建 
    { 
    	printf("请输入："); 
    	while(1)//建立一个死循环，循环终止条件是按了enter键 
    	{ 
    		L.length++;//顺序表长度加一 
    		if(L.length>MAXSIZE)//判断是否超出最大容纳量 
    		{ 
    			printf("顺序表已满！\n");
    			return ;
    		}
    		scanf("%d",&L.Data[L.length].key);//顺序表数据的输入 
    		if(getchar() == '\n')//循环终止条件 
    			break;
    	}
    }
    
    void InputList(SqList L)//顺序表的输出 
    { 
    	int i;//记录次数 
    	if(L.length == 0)//判断顺序表是否为空 ，若为空结束该函数 
    	{ 
    		printf("顺序表是空的！\n");
    		return ;
    	}
    	printf("打印为：");
    	for(i=1;i<=L.length;i++)//利用循环打印顺序表中的数据 
    		printf("%d ",L.Data[i].key);	
    }
    
    void ShellInsert(SqList &L,int dk)//对顺序表L做一趟增量是dk的希尔插入排序 ,当dk==1时为直接插入排序 
    { 
    	int i,j;//i和j为数据位置 
    	for(i=dk+1;i<=L.length;i=i+dk)//利用循环将Data[i]逐个插入到有序子表 
    	{ 
    		if(L.Data[i].key < L.Data[i-dk].key)//判断第i个和i-dk个数据的大小，若小于，需将Data[i]插入有序子表中 
    		{ 
    			L.Data[0] = L.Data[i];//将待插入的记录在监视哨中 
    			L.Data[i] = L.Data[i-dk];//Data[i-dk]后移 
    			for(j=i-2*dk;j>0&&L.Data[0].key<L.Data[j].key;j=j-dk)//从后往前寻找插入位置
    				L.Data[j+dk] = L.Data[j];//记录逐个后移，直到找到插入位置 
    			L.Data[j+dk] = L.Data[0];//将Data[0]即Data[i],插入到正确位置 
    		}
    	}
    }
    void SSort(SqList &L,int dt[],int t)//按增量序列dt[0…t-1]对顺序表L作t趟希尔排序 
    { 
    	int k;//次数 
    	for(k=0;k<t;k++)//共t趟，t次循环 
    		ShellInsert(L,dt[k]);//一趟增量为dt[k]的希尔排序 
    }
    void ShellSort(SqList &L)//对顺序表做希尔排序 
    { 
    	int t = 3,//排序的趟数，可更改 
    		dt[] = { 5,3,1};//各趟排序的增量序列，可更改 
    	SSort(L,dt,t);//进入增量序列dt[0…t-1]对顺序表L作t趟希尔排序 
    } 
    
    int main()
    { 
    	SqList L;
    	InitList(L);//初始化顺序表 
    	CreateList(L);//创建顺序表 
    	ShellSort(L);//希尔排序 
    	InputList(L);//打印排序后结果 
    	return 0;
    }

![在这里插入图片描述][20201119183319168.png_pic_center]  
（完）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/aa5bada6dd6544f9845dc201ace08eec.png
[20201119183319168.png_pic_center]: /images/20221120/400d82fa3060477c9494cda582cf7eee.png