C++排序算法之希尔排序

超、凢脫俗 2022-06-12 02:58 204阅读 0赞

**希尔排序**

**（1）算法介绍**

希尔排序又叫做缩小增量排序，其本质还是插入排序，只不过是将待排序的序列按照某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。这个规则就是增量。

例如，先以增量5来分割序列，即将下标为1，6，11，16........的记录分成一组，将下标为2，7，12，17，........的记录分成另外一组等，然后分别对这些组进行直接插入排序，这就是一趟希尔排序。将上面排列好序的整个序列，按照同样的方式再以增量3分割，在进行一趟希尔排序，最后以增量1分割整个序列，其实就是对整个序列进行一趟直接插入排序。，从而完成整个希尔排序。

注意到增量5、3、1是逐渐缩小的，这就是缩小增量排序的由来。而我们知道，直接插入排序适合于序列基本有序的情况，希尔排序的每趟排序，都会使整个序列变得更加有序，等整个序列基本有序了，再来一趟直接插入排序，这样会使排序效率更高，这就是希尔排序的意思。

关于直接插入排序可参考：[点击打开链接][Link 1]

**（2）执行流程**

下面举例说明希尔排序的执行过程

原始序列：3 5 2 9 7 8 4 1 6 10

1）以增量5分割序列，得到以下几个子序列：

子序列1：3 8

子序列2： 5 4

子序列3： 2 1

子序列4： 9 6

子序列5： 7 10

分别对这5个子序列进行直接插入排序，得到：

子序列1：3 8

子序列2： 4 5

子序列3： 1 2

子序列4： 6 9

子序列5： 7 10

一趟希尔排序结束，结果为：3 4 1 6 7 8 5 2 9 10

2）再以增量3分割序列，得到以下几个子序列：

子序列1：3 6 5 10

子序列2： 4 7 2

子序列3： 1 8 9

分别对这3个子序列进行直接插入排序，得到：

子序列1：3 5 6 10

子序列2： 2 4 7

子序列3： 1 8 9

一趟希尔排序结束，结果为：3 2 1 5 4 8 6 7 9 10

3）最后以增量1分割，即对上面的结果全体进行一次直接插入排序，从而完成整个希尔排序。

最后希尔排序的结果为：1 2 3 4 5 6 7 8 9 10

代码实现如下：

#include <iostream>
    #include <vector>
    using namespace std;
    
    /*希尔排序算法：平均时间复杂度为 O(1)；空间复杂度为 O(1) 
    注意：希尔排序的增量序列的最后一个值一定是1，其次增量序列中的值每一除1之外的公因子*/
    
    void shellSort(vector<int>& R)
    {
    	int gap;                                                                //用来设置增量
    	for (gap = 5; gap > 0; gap=gap-2)                              	        //设置增量
    	{
    		for (int i = 0; i < gap; i++)                                   //对增量之间的值循环进行直接插入排序
    		{
    			for (int j = i + gap; j < R.size(); j = j + gap)        //对每一组元素进行直接插入排序
    			{
    				int temp = R[j];                                //相当于无序序列中的第一个数
    				int k = j - gap;                                //想当于有序序列中的数
    				while (k >= 0 && R[k] > temp)
    				{
    					R[k + gap] = R[k];
    					k = k - gap;
    				}
    				R[k + gap] = temp;
    			}
    		}
    	}
    }
    
    void main()
    {
    	vector<int> R = { 3,  5,  2,  9,  7,  8,  4,  1,  6,  10 };
    	cout << "排序前：";
    	for (auto x:R)
    		cout << x << " ";
    	cout << endl;
    	shellSort(R);
    	cout << "排序后：";
    	for (auto x:R)
    		cout << x << " ";
    	cout << endl;
    }

运行结果：

![Center][]

**复杂度分析：**

**（1）时间复杂度**

**平均时间复杂度为O(nlogn)**

**（2）空间复杂度**

**希尔排序的空间复杂度同直接插入排序一样，为O(1)。**

（3）希尔排序模板

/*shell排序模板*/
    /*一种较好的增量选取方式为{1,5,19,41,109，...}，该序列中的项或者是9*4i（4的i次方，后同）-9*2i+1的形式，或者是4i-3*2i+1的形式*/
    template <typename Comparable>
    void shellsort(vector<Comparable> & a)
    {
    	for (int gap = a.size() / 2; gap > 0; gap /= 2)           //增量选取方式（不理想）采用Shell建议的 h(t)=N/2、h(t-1) = h(t)/2、.......
    	{
    		for (int i = gap; i < a.size(); ++i)
    		{
    			Comparable tem = std::move(a[i]);
    			int j = i;
    			for (; j >= gap&&tem < a[j - gap]; j -= gap)   // j 为什么要>=gap？因为最前面一个元素为j-gap，所以j最小为gap
    				a[j] = std::move(a[j - gap]);
    			a[j] = std::move(tem);
    		}
    	}
    }

[Link 1]: http://blog.csdn.net/yf_li123/article/details/75043730
[Center]: /images/20220612/b81aeb3791e343fb8aa0cfee7bc3e475.png