希尔排序

希尔排序

基本原理：

根据步长将元素分为若干个数组，并对每一个数组进行排序。缩小步长，随着步长逐渐减小，所分成的组包含的元素越来越多，当步长的值减小到 1 时，所有元素都在一个数组中，构成一组有序记录，则完成排序。

要点：每次分组后，由该组的最后一个元素向前比较，如果满足条件则交换（因为除最后一个元素都已经排序，故不必比较该分组的每一个元素）

代码

#include <iostream>
int main()
{
    int arry[] = {5,3,2,4,6,1,8,9,0,7};
    printf("原始数组: ");
    for (int i = 0; i < 10;++i)
    {
        printf("%d ",arry[i]);
    }
    // shell法排序
    //根据步长分成若干组
    for (int increment = 10/2/*初始步长*/; increment > 0/*步长为1时完成排序*/; increment /= 2/*缩小步长*/)
    {
        printf("

步长为 %d 时分组
",increment);
        for (int i = increment; i < 10; i++) //遍历每个小组
        {
            printf("
第 %d 组
",i - increment + 1);
            printf("排序前: ");
            for (int k = i - increment; k < 10; k += increment )//打印结果
            {
                printf("%d ",arry[k]);
            }
            for (int j = i; j >= increment; j -= increment) //对每个小组排序
            {
                if (arry[j] < arry[j - increment])
                {
                    int temp = arry[j];
                    arry[j] = arry[j - increment];
                    arry[j - increment] = temp;
                }
            }
            printf("
排序后: ");
            for (int k = i - increment; k < 10; k += increment )//打印结果
            {
                printf("%d ",arry[k]);
            }
        }
        printf("
步长为 %d 排序结果: ",increment);//打印结果
        for (int i = 0; i < 10;++i)
        {
            printf("%d ",arry[i]);
        }
    }
    return 0;
}

结果