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

ゞ浴缸里的玫瑰 2022-08-20 11:18 83阅读 0赞

**希尔排序**(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

**该方法的基本思想是**：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比O(n^2)有较大提高

**时间复杂度** ：增量h1 = 1, h(i+1) = 3hi + 1,O(n^1.25);

**稳定性**：不是稳定的排序

实例

对希尔算法完整描述如下

template<class T>
    void Shellsort(T data[], int n)
    {
    	for (int div = n / 2; div > 0; div /= 2)
    	{
    		for (int i = 0; i < div; i++)
    		{
    			for (int j = i + div; j < n; j += div)
    			{
    				int k = 0;
    				T temp = data[j];
    				for (k = j; k > 0 && temp < data[k - div]; k -= div)
    				{
    					data[k] = data[k - div];
    				}
    				data[k] = temp;
    			}
     		}
     	}
    }

希尔算法简洁版

template<class T>
    void Shellsort(T data[], int n)
    {
    	for (int div = n / 2; div >= 1; div /= 2)
    	{
    		for (int i = div, j = 0; i < n; i++)
    		{
    			T temp = data[i];
    			for (j = i; j > 0 && (temp < data[j - div]); j -= div)
    			{
    				data[j] = data[j - div];
    			}
    			data[j] = temp;
    		}
    	}
    }

例子

// Shellsort.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    using namespace std;
    
    
    /*
    //希尔算法简洁版
    template<class T>
    void Shellsort(T data[], int n)
    {
    	for (int div = n / 2; div >= 1; div /= 2)
    	{
    		for (int i = div, j = 0; i < n; i++)
    		{
    			T temp = data[i];
    			for (j = i; j > 0 && (temp < data[j - div]); j -= div)
    			{
    				data[j] = data[j - div];
    			}
    			data[j] = temp;
    		}
    	}
    }
    */
    
    //希尔算法完整描述
    template<class T>
    void Shellsort(T data[], int n)
    {
    	for (int div = n / 2; div > 0; div /= 2)
    	{
    		for (int i = 0; i < div; i++)
    		{
    			for (int j = i + div; j < n; j += div)
    			{
    				int k = 0;
    				T temp = data[j];
    				for (k = j; k > 0 && temp < data[k - div]; k -= div)
    				{
    					data[k] = data[k - div];
    				}
    				data[k] = temp;
    			}
     		}
     	}
    }
    
    
    template<class T>
    void Sprint(T data[], int n)
    {
    	for (int i = 0; i < n; i++)
    	{
    		cout << data[i] << " ";
    	}
    
    	cout << endl;
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int arr[] = { 3, 5, 1, 4, 6, 2};
    //	int arr[] = { 3, 1, 2 };
    
    	int n = sizeof(arr) / sizeof(int);
    	Shellsort(arr, n);
    	Sprint(arr, n);
    	return 0;
    }