排序之希尔排序

╰+攻爆jí腚メ 2022-04-22 00:02 107阅读 0赞

> # 希尔排序简介 #

**希尔排序**(Shell's Sort)是[插入排序][Link 1]的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，[算法][Link 2]便终止

> # 希尔排序基本思想 #

先取一个小于n的整数d1作为第一个[增量][Link 3]，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行[直接插入排序][Link 4]；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量![https://gss1.bdstatic.com/9vo3dSag\_xI4khGkpoWK1HF6hhy/baike/s%3D16/sign=5b37a5ba18d5ad6eaef960ec81cb742d/3c6d55fbb2fb4316e40ee40423a4462309f7d3bf.jpg][https_gss1.bdstatic.com_9vo3dSag_xI4khGkpoWK1HF6hhy_baike_s_3D16_sign_5b37a5ba18d5ad6eaef960ec81cb742d_3c6d55fbb2fb4316e40ee40423a4462309f7d3bf.jpg] =1(![https://gss0.bdstatic.com/-4o3dSag\_xI4khGkpoWK1HF6hhy/baike/s%3D16/sign=dd8c7c646359252da7171902359bf9f4/32fa828ba61ea8d3f96aea7a940a304e251f5807.jpg][https_gss0.bdstatic.com_-4o3dSag_xI4khGkpoWK1HF6hhy_baike_s_3D16_sign_dd8c7c646359252da7171902359bf9f4_32fa828ba61ea8d3f96aea7a940a304e251f5807.jpg] <![https://gss2.bdstatic.com/-fo3dSag\_xI4khGkpoWK1HF6hhy/baike/s%3D28/sign=5261265e02e9390152028a367aec2ebf/80cb39dbb6fd5266feaea26aa818972bd50736c2.jpg][https_gss2.bdstatic.com_-fo3dSag_xI4khGkpoWK1HF6hhy_baike_s_3D28_sign_5261265e02e9390152028a367aec2ebf_80cb39dbb6fd5266feaea26aa818972bd50736c2.jpg] …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

**该方法实质上是一种分组插入方法**

比较相隔较远距离（称为[增量][Link 3]）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。算法先将要排序的一组数按某个[增量][Link 3]d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当[增量][Link 3]减到1时，整个要排序的数被分成一组，排序完成。

一般的初次取序列的一半为[增量][Link 3]，以后每次减半，直到增量为1。

**给定实例的****shell****排序的排序过程**

假设待排序文件有10个记录，其关键字分别是：

49，38，65，97，76，13，27，49，55，04。

[增量][Link 3]序列的取值依次为：

5，2，1

![20181101223534798.jpeg][]

#  #

> # 稳定性 #

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的

时间复杂度: O(n^（1.3—2）)

空间复杂度: O(1)

#include <iostream>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    void PrintArray(int num[],int N)
    {
    	for(int i = 0; i < N; i++)
    	{
    		cout << num[i] << " ";
    	}
    	cout << endl;
    }
    
    void Shell(int num[],int d,int N)
    {
    	for(int i = d; i < N; i ++)
    	{
    		int j = i - d;
    		int temp = num[i];
    		while( j >= 0 && num[j] > temp)
    		{
    			num[j+d] = num[j];
    			j = j - d;
    		}
    		if(j != i - d)
    		{
    			num[j+d] = temp;
    		}
    	}
    }
    
    void ShellSort(int num[],int N)
    {
    	int d = N / 2;
    	while(d >= 1)
    	{
    		Shell(num, d, N);
    		d = d / 2;
    	}
    }
    
    int main()
    {
    	int N;
    	while( cin >> N)
    	{
    		srand(time(0));
    		int num[N];
    		for(int i = 0; i < N; i++)
    		{
    			num[i] = rand() % 65536;
    		}
    		ShellSort(num,N);
    		
    		
    		PrintArray(num , N);
    	}
    	
    	
    	return 0;
    }

[Link 1]: https://baike.baidu.com/item/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
[Link 2]: https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025
[Link 3]: https://baike.baidu.com/item/%E5%A2%9E%E9%87%8F
[Link 4]: https://baike.baidu.com/item/%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
[https_gss1.bdstatic.com_9vo3dSag_xI4khGkpoWK1HF6hhy_baike_s_3D16_sign_5b37a5ba18d5ad6eaef960ec81cb742d_3c6d55fbb2fb4316e40ee40423a4462309f7d3bf.jpg]: https://gss1.bdstatic.com/9vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D16/sign=5b37a5ba18d5ad6eaef960ec81cb742d/3c6d55fbb2fb4316e40ee40423a4462309f7d3bf.jpg
[https_gss0.bdstatic.com_-4o3dSag_xI4khGkpoWK1HF6hhy_baike_s_3D16_sign_dd8c7c646359252da7171902359bf9f4_32fa828ba61ea8d3f96aea7a940a304e251f5807.jpg]: https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D16/sign=dd8c7c646359252da7171902359bf9f4/32fa828ba61ea8d3f96aea7a940a304e251f5807.jpg
[https_gss2.bdstatic.com_-fo3dSag_xI4khGkpoWK1HF6hhy_baike_s_3D28_sign_5261265e02e9390152028a367aec2ebf_80cb39dbb6fd5266feaea26aa818972bd50736c2.jpg]: https://gss2.bdstatic.com/-fo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D28/sign=5261265e02e9390152028a367aec2ebf/80cb39dbb6fd5266feaea26aa818972bd50736c2.jpg
[20181101223534798.jpeg]: /images/20220422/cec9c2f84fae4823b33b6914bd4c6144.png