排序——希尔排序

缺乏、安全感 2022-09-10 11:22 156阅读 0赞

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASeKAmG0gSmll_size_20_color_FFFFFF_t_70_g_se_x_16]

**希尔排序的基本思想**

希尔排序又称缩小增量排序，因  D L . S h e l l DL.Shell DL.Shell 于 1959 年提出而得名。先将待排序表按照一定的间隔分割成多个子表，对各个子表分别进行直接插入排序。缩小增量  d d d，重复上述过程，知道  d = 1 d=1 d=1 为止。

**步骤**

1.  初始选择增量  d = l e n g t h / 2 d=length/2 d=length/2
2.  根据增量  d d d 分组
3.  每个组内进行直接插入排序
4.  若  d > 1 d>1 d>1 则增量  d = d / 2 d=d/2 d=d/2 ，重复2，3，4步；若  d = 1 d=1 d=1，则直接插入排序后停止

**过程演示**

1.  初始序列
    
    ![image-20210907172428200][]
2.  第一趟，初始增量取  d = l e n g t h / 2 = 10 / 2 = 5 d=length/2=10/2=5 d=length/2=10/2=5
    
    ![image-20210907174743975][]
3.  第二趟，修改增量  d = d / 2 = 2 d=d/2=2 d=d/2=2
    
    ![image-20210907175802855][]
4.  第三趟，修改增量  d = d / 2 = 1 d=d/2=1 d=d/2=1，得到最终排序结果
    
    ![image-20210907180353493][]

**算法代码**

#include <iostream>
    using namespace std;
    
    //希尔排序 
    void ShellSort(int nums[],int n){
    	int d,i,j,temp;
    	for(d=n/2;d>=1;d/=2){							//初始增量：d/2，d=1结束 
    		for(i=d;i<n;i++){							//每一趟使用直接插入排序 
    			temp=nums[i];						
    			for(j=i;j>=d&&temp<nums[j-d];j-=d){
    				nums[j]=nums[j-d];
    			}
    			nums[j]=temp;
    		}
    	}
    }
    
    //打印数组 
    void printNum(int numbers[],int n){
    	for(int i=0;i<n;i++){
    		cout<<numbers[i]<<" ";
    	}
    }
    
    int main()
    {
    	int numbers[10]={3,44,38,5,47,15,36,26,1,2};
    	int n=sizeof(numbers)/sizeof(numbers[0]);	//数组长度 
    	ShellSort(numbers,n);		//调用 InsertSort 函数进行插入排序 
    	printNum(numbers,n);		//打印数组 
        return 0;
    }

> 注：当  d = 1 d=1 d=1 时，希尔排序会变成直接插入排序

**算法性能分析**

*  空间复杂度： O ( 1 ) O(1) O(1)
 *  算法稳定性1：不稳定

--------------------

1.  算法的稳定性：若待排序表中有两个元素  R i R\_i Ri 和  R j R\_j Rj，其对应的关键字相同即  k e y i = k e y j key\_i = key\_j keyi=keyj，且在排序前  R i R\_i Ri 在  R j R\_j Rj 的前面，若使用某一排序算法排序后，  R i R\_i Ri 仍在  R j R\_j Rj 的前面，则称这个排序算法是**稳定的**，否则称排序算法是**不稳定**的。 ↩︎

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASeKAmG0gSmll_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/f0ffe9972dc54ce6a63ab9c7e06b8de7.png
[image-20210907172428200]: /images/20220829/18e7c6a63e4140db856d1fef5e0d11ca.png
[image-20210907174743975]: /images/20220829/3a51094e276d4b8089e0325855aab5ef.png
[image-20210907175802855]: /images/20220829/c8deb6790f47493e8fd605cf69921ca6.png
[image-20210907180353493]: /images/20220829/8fb0080ea0454cbe902ca9f6e399c013.png