【算法】希尔排序算法Shell Sort

- 日理万妓 2022-11-01 04:26 78阅读 0赞

## 原理 ##

**基本思想：希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法便终止。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70 1]

## 代码 ##

#include <bits/stdc++.h>
    using namespace std;
    void print_sort(int arr[],int n)
    {
        
    	int i;
    	for(i=0;i<n;i++)
    	{
        
    		cout<<arr[i]<<" ";
     	}
    }
    void shell_sort(int arr[],int n)
    {
        
    	int i,j,inc,key;//inc初始增量 
    	//初始增量是n/2，每一趟之后除以2
    	for(inc=n/2;inc>0;inc/=2) 
    	{
        
    		//每一趟采用插入排序
    		for(i=inc;i<n;i++)
    		{
        
    			key=arr[i];
    			for(j=i;j>=inc&&key<arr[j-inc];j-=inc)
    			{
        
    				arr[j]=arr[j-inc];
    			}
    			arr[j]=key;
    		} 
    	}
    } 
    int main()
    {
        
    	int arr[]={
        15,5,2,7,12,6,1,4,3,9,8,10};
    	shell_sort(arr,12);
    	print_sort(arr,12);
    	return 0;
    }

基本都是插入排序，只不过变成了缩小增量来排序

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70]: /images/20221024/cfe6fca087c349c5956ff81f49035285.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUxNjMxNjM5_size_16_color_FFFFFF_t_70 1]: /images/20221024/f2d42affb5ce4b53a5b0bfffe74fe88d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，78人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法】希尔排序算法Shell Sort

原理基本思想：希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组

- 日理万妓/ 2022年11月01日 04:26/ 0 赞/ 79 阅读

相关排序——希尔排序（Shell Sort）

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对

ゞ浴缸里的玫瑰/ 2022年08月20日 11:18/ 0 赞/ 83 阅读

相关算法——希尔排序

强烈推荐一个大神的人工智能的教程：[http://www.captainbed.net/zhanghan][http_www.captainbed.net_zhanghan]

￡神魔★判官ぃ/ 2022年07月16日 06:48/ 0 赞/ 149 阅读

相关希尔排序算法

希尔排序算法到达是什么呢？希尔其实一个人的名字，是这个人发明了这个算法。其实希尔排序算法还有个名字叫缩小增量排序算法。如果我们要谈希尔排序算法必须要先谈直接插入排序，因为我们的

偏执的太偏执、/ 2022年06月03日 02:19/ 0 赞/ 165 阅读

相关【算法】希尔排序

希尔排序(Shell's Sort)是插入排序的一种，又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希

╰+哭是因爲堅強的太久メ/ 2022年05月15日 06:42/ 0 赞/ 159 阅读

相关图解排序算法及实现——希尔排序（Shell Sort）

希尔排序（ShellSort）也称增量递减排序算法，即跨多步版的InsertionSort，是InsertionSort基础上的改进版。InsertionSort可以看作She

红太狼/ 2022年05月14日 05:39/ 0 赞/ 153 阅读

相关算法—希尔排序

希尔排序希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：

分手后的思念是犯贱/ 2021年12月03日 04:11/ 0 赞/ 260 阅读

相关算法——希尔排序

文章目录前言介绍特点基本思想实现总结代码实现拓展：克努特序列前言为了学习面试中常常要考察到的希

柔光的暖阳◎/ 2021年11月05日 06:56/ 0 赞/ 291 阅读

相关算法排序-4、希尔排序（Shell Sort）

希尔排序（Shell Sort） 1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素

妖狐艹你老母/ 2021年09月28日 09:24/ 0 赞/ 221 阅读

相关 Java 希尔排序（Shell Sort）

文章目录 * 算法描述过程演示代码实现算法分析希尔排序是希尔（Donald Shell）于1959...

你的名字/ 2020年06月14日 02:30/ 0 赞/ 724 阅读