希尔排序算法C/C++代码图文讲解

希尔排序又称“缩小增量排序”，是插入排序的一种。直接插人排序，当待排序的记录个数较少且待排序序列的关键字基本有序时，效率较高。希尔排序基于以上两点，从“减少记录个数”和“序列基本有序”两个方面对直接插入排序进行了改进。

（1）步骤：

1. 先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重复上述操作…

2. 当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。

（2）特点：

1. 缩小增量

2. 多遍插入排序

3. 时间复杂度：O(n 1.3 n^{1.3}n 1.3 )

4. 空间复杂度：O(1)

5. 稳定性：不稳定

（3）动图演示：

这里重要的是理解分组思想，每一个组其实就是一个插入排序，相当于进行多次插入排序。

（4）C语言代码实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int shell_sort(int arr[],int n)
{
    register int i, j, tmp;
    int step;

    for(step = n/2; step > 0;step /= 2)/*增量步长*/
    {
        /*step = 4 2 1*/
        for(i = step; i < n; i++)
        {
            tmp = arr[i];
            j = i - step;
            for(;j >= 0 && tmp < arr[j];)
            {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = tmp;

        }
    }
}

#define LENGTH 8

int main( int argc, int *argv[])
{
    int i;
    int arr[LENGTH] = {6,5,3,1,8,7,2,4};

    for(i=0;i<LENGTH;i++)
    printf("%d ",arr[i]);printf("\n");

    shell_sort(arr,LENGTH);

    for(i = 0;i < LENGTH;i++)
    printf("%d ", arr[i]);printf("\n");
}

如果我们编译并运行上述程序，那么它应该产生以下结果：

6 5 3 1 8 7 2 4 
1 2 3 4 5 6 7 8