103-对希尔排序算法的实现和分析

- 日理万妓 2022-12-29 04:52 71阅读 0赞

## 希尔排序 ##

***希尔排序的思想***  
缩小增量(分组)排序，可以看成是对直接插入排序的优化  
按照分组的对每组内的数据进行直接插入  
使得整个数据序列趋于有序（小数据大部分在前半部分，大数据大部分在后半部分）  
先比较每个组内的前两个数据，接着是前三个，前四个…  
i的控制是++  
这个增量（分组）不断减小，然后按照新的分组重复上面过程。直到分组为1个的时候  
***希尔排序的分析***  
时间复杂度： O(n1.3)–O(n1.5)  
空间复杂度： O(1)  
稳定性： 不稳定（有跳跃性交换数字）

首先先书写需要用到的辅助函数

#include<stdio.h>
    
    /*辅助函数：
        1.打印数据
    	2.判断整个数据序列是否已经有序
    	3.交互两个数据swap方法
    */
    
    void Show(int *arr,int len)//打印数据
    {
        
    	for(int i=0;i<len;++i)
    	{
        
    		printf("%d  ",arr[i]);
    	}
    	printf("\n");
    }
    
    bool IsSort(int *arr,int len)//判断整个数据序列是否已经有序
    {
        
    	for(int i=0;i<len-1;++i)
    	{
        
    		if(arr[i]>arr[i+1])
    		{
        
    			return false;
    		}
    	}
    	return true;
    }
    
    void SwapValue(int *a,int *b)//交互两个数据swap方法
    {
        
    	int tmp=*a;
    	*a=*b;
    	*b=tmp; 
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
接下来实现希尔排序算法的函数

void Shell(int *arr,int len,int group)
    {
        
    	for(int i=group;i<len;++i)
    	{
        
    		int tmp=arr[i];
    		int j=i;
    		for(;j>0&&arr[j-group]>tmp;j-=group)
    		{
        
    			arr[j]=arr[j-group];
    		}
    		arr[j]=tmp;
    	}
    }
    
    void ShellSort(int *arr,int len)
    {
           
        //group数组的元素是互质的，并且最后一个分组值为1 
    	int group[]={
        5,3,1};
        for(int i=0;i<sizeof(group)/sizeof(group[0]);++i)
        {
        
        	Shell(arr,len,group[i]);
    	}
    }

最后完成主函数

int main()
    {
        
    	int arr[]={
        7,87,29,75,41,50,62,92,69,22,76,77,35};
    	Show(arr,sizeof(arr)/sizeof(arr[0]));
    	ShellSort(arr,sizeof(arr)/sizeof(arr[0]));
    	Show(arr,sizeof(arr)/sizeof(arr[0])); 
    	return 0;
    	
    }

运行结果如图所示  
![在这里插入图片描述][20201220133203177.png_pic_center]  
应如何分组？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/7eb780a3612d46d3aea568fba1ae7e99.png
[20201220133203177.png_pic_center]: https://img-blog.csdnimg.cn/20201220133203177.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201220133227202.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center