八大排序算法--希尔排序

1、算法思想

希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。

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

如下图所示为算法模拟过程：

2、代码

#include <iostream>

using namespace std;

//希尔排序
void shellSort(int iarr[],int length)
{
    int dt[3] = {5,3,1},i =0 ,j,k,temp;
    for(j = 0; j < 3; ++j)
    {
        for(i = dt[j]; i < length; ++i)
        {
            temp = iarr[i];
            k = i - dt[j];
            while(temp < iarr[k] && k >= 0)
            {
                iarr[k + dt[j]] = iarr[k];
                k -= dt[j];
            }
            iarr[k + dt[j]] =  temp;
        }
    }
}
int main()
{
    int a[25]={4,1,3,2,16,9,10,14,8,7,7,10,7,28,30,3,12,0,1,3,9,12,11,4,19};
    shellSort(a,25);
    for(int i=0;i < 25; ++i)
        cout << a[i] << " ";
    return 0;
}