希尔插入排序C/C++代码实现

╰半橙微兮° 2023-02-23 08:22 150阅读 0赞

## 举例： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]  
希尔排序是跨度大一点的直接插入排序，直接插入排序可以看成一趟增量是 1 的希尔排序。

## 算法属性： ##

时间复杂度取决于所选取的增量序列。  
空间复杂度为O(1)  
不稳定排序。  
只能用于顺序结构，并且最后 一个增量值必须等于1。  
适合初始记录无序、n较大时的情况。

## 代码实现： ##

#include<stdio.h>
    
    #define MAXSIZE 20
    typedef int KeyType;
    typedef int InfoType;
    //记录类型
    typedef struct {
        
    	KeyType key;
    	InfoType otherinfo;
    }RedType;
    //顺序表类型
    typedef struct {
        
    	RedType r[MAXSIZE + 1];  //r[0]闲置或作哨兵
    	int length;	  			 //顺序表长度
    }SqList;
    
    
    //希尔插入排序
    void ShellInsert(SqList &L, int dk) {
        
    	int i, j;
    	for (i = dk + 1; i <= L.length; ++i)
    	{
        
    		L.r[0] = L.r[i];
    		for (j = i - dk; L.r[0].key < L.r[j].key; j -= dk)
    		{
        
    			L.r[j + dk] = L.r[j];
    		}
    
    		L.r[j + dk] = L.r[0];
    	}
    }
    
    //按希尔增量进行排序
    void ShellSort(SqList &L, int dt[], int t)
    {
        
    	for (int k = 0; k < t; ++k)
    	{
        
    		ShellInsert(L, dt[k]);
    	}
    }
    
    //打印排序结果
    void println(SqList L)
    {
        
    	for (int i = 1; i <= L.length; i++)
    	{
        
    		printf("%d, ", L.r[i].key);
    	}
    	printf("\n");
    }
    
    
    int main()
    {
        
    	SqList L;
    	L.r[1].key = 5;
    	L.r[2].key = 8;
    	L.r[3].key = 1;
    	L.r[4].key = 4;
    	L.r[5].key = 3;
    	L.length = 5;
    
    	//创建增量数组dt[]和算法的执行次数t
    	int dt[] = {
         4,2,1 };
    	int t = 3;
    
    	ShellSort(L, dt, t);
    	println(L);
    }

## 运行结果： ##

![在这里插入图片描述][20200706142713679.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: /images/20230209/45e34d4905bf4ff599ac722e3f5b9a3d.png
[20200706142713679.png]: /images/20230209/b5ceb22019ea47e5be9f0cb0ed0fb9aa.png