【数据结构】：希尔排序（c++实现）

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

二、希尔排序的基本思想

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

（1）初始增量为3，该数组分为三组分别进行排序。 （2）将增量改为2，该数组分为2组分别进行排序。 （3）将增量改为1，该数组整体进行排序。

三、C++代码

#include<iostream>
 
using namespace std;
const int increment = 3;
void shellSort(int a[],int len)
{
    int temp = 0;
    unsigned gap = len/increment; // 步长初始化
    while(gap) // while gap>=1
    {
        for (unsigned i = gap; i < len; ++i) // 分组，在每个子序列中进行插入排序
        {
            temp = a[i];//将当前的元素值先存起来方便后面插入
            unsigned j = i;
            while (j >= gap && temp < a[j-gap])//寻找插入位置
            {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = temp;
        }
        gap = gap/increment;
    }
}
int main()
{
    int array[10] = {4,2,3,1,7,8,6,9,5,10};
    cout<<"排序前的元素："<<endl; 
    for(int num=0;num<10;num++)
    { 
    	cout<<array[num]<<" ";
	}
	cout<<endl; 
    shellSort(array,10);
    cout<<"排序后的元素："<<endl; 
    for(int num=0;num<10;num++)
    {    	
    	cout<<array[num]<<" ";
	}
    return 0;
}

代码执行结果：