排序算法之希尔排序

清疚 2022-09-25 15:23 202阅读 0赞

同样的先上这张图

![Center][]

下面分析希尔插入排序：

希尔排序将序列根据增量d分成几个子序列，对每个子序列作插入排序。然后把增量d变为d/2，重复这个过程直到d=1，这时的希尔排序其实就是插入排序。

希尔排序的算法效率与增量因子有关，目前还没有确定的最好因子，其时间复杂度可认为是O(nlogn)。

希尔排序不需要额外的辅助空间，其空间复杂度为O(1)。

希尔排序在对每个子序列作插入排序时，可能会破坏不同子序列中相同元素的相对关系，所以希尔排序是不稳定的。

AS代码：

/**
    		 * 有增量的插入排序
    		 * 外层循环选择待插入元素
    		 * 内层循环查找插入位置并将该位置后面元素后移
    		 */
    		private function ShellInstertSort(arr:Array,d:Number):void{
    			var x:Number,j:int;
    			for(var i:uint=d;i<arr.length;i+=d){
    				if(arr[i]<arr[i-d]){
    					x=arr[i];
    					j=i-d;
    					while(x<arr[j] && j>=0){
    						arr[j+d]=arr[j];
    						j-=d;
    					}
    					arr[j+d]=x;
    				}
    			}
    		}
    		
    		/**
    		 * 希尔排序
    		 * 以增量d作插入排序
    		 */
    		private function ShellSort(arr:Array):void{
    			var d:Number=arr.length/2;
    			while(d>=1){
    				ShellInstertSort(arr,d);
    				d=d/2;
    			}
    		}

C++代码

/*
    * 希尔排序
    * 即有增量的插入排序
    * O(nlogn)
    * O(n)
    * 不稳定
    */
    template<typename T>
    void SortHelp<T>::shellSort(T l[], int length)
    {
    	int d = length / 2;
    	while (d > 0)
    	{
    		shellInsertSort(l, length, d);
    		d /= 2;
    	}
    }
    
    template<class T>
    void SortHelp<T>::shellInsertSort(T l[], int length, int d)
    {
    	int temp, j;
    	for (int i = d; i < length; i += d)
    	{
    		if (l[i] < l[i - d])
    		{
    			j = i - d;
    			temp = l[i];
    			while (l[j] > temp && j >= 0)
    			{
    				l[j + d] = l[j];
    				j -= d;
    			}
    			l[j + d] = temp;
    		}
    	}
    }

总结，希尔排序时间复杂度为O(nlogn)，空间复杂度为O(1)，不稳定。

[Center]: /images/20220717/0e87ff2e2ffd466aa4261b4860cff6e5.png