c语言实现希尔排序算法

1.算法简介

   希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。希尔排序实质上是一种分组插入方法。它的基本思想是：对于n个待排序的数列，取一个小于n的整数gap(gap被称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中；然后，对各组内的元素进行直接插入排序。 这一趟排序完成之后，每一个组的元素都是有序的。然后减小gap的值，并重复执行上述的分组和排序。重复这样的操作，当gap=1时，整个数列就是有序的。

2.源码实现

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

//希尔排序算法
void shell_sort(int n, int *u)
{
        int gap;
        int tmp;
        int i;
        int j;

        for(gap=n/2 ; gap>0; gap/=2)
        {
                for(i=gap; i<n; i++)
                {
                        tmp = u[i];

                        for(j = i; j >= gap && tmp < u[j-gap]; j -= gap)
                        {
                                u[j] = u[j-gap];
                        }

                        u[j] = tmp;
                }
        }
}

int main()
{
        int u[] = {1, 9, 7, 0, 6};
        int n = 5;
        int i = 0;

        shell_sort(n, (int *)u);

        for(i=0; i<n; i++)
        {
                printf("%d ", u[i]);
        }

        putchar('\n');

        return 0;
}

3.编译源码

$ gcc -o test test.c

4.运行及结果

$ ./test
0 1 6 7 9