排序之希尔（Shell）排序

一、数据结构
        约定排序均为升序排序，要排序的记录存储在线性表中，线性表由排序关键字和其它域组成，其定义如下：
        #define MAXITEM 100
        struct rec
        {
            KeyType key;        // 关键字域
            ElemType data;     // 其它数据域
        };
        struct rec sqlist[MAXITEM];
        这里的KeyType和ElemType可以是任何相应的数据类型，比如int，float或char等，在算法中，约定其为int类型。

二、算法思想
        希尔（Shell）排序的基本思想是：把记录按下标的一定增量分组，对每组记录使用插入排序，随着增量逐渐减小，所分成的组包含的记录越来越多，到增量的值减小到1时，整个数据合成为一组，构成一组有序记录，则完成排序。

三、程序实现
        实现希尔排序的函数如下：
        void shellsort(sqlist r, int n)        // 排序元素r[1]~r[n]
        {
            int i, j, gap;
            struct rec x;
            gap = n/2;
            while (gap > 0)
            {
                for (i=gap+1; i<=n; i++)
                {
                    j = i - gap;
                    while (j > 0)
                    {
                        if (r[j].key > r[j+gap].key)  
                        {
                            x = r[j];        // 将r[j]与r[j+gap]进行交换
                            r[j] = r[j+gap];
                            r[j+gap] = x;
                            j = j - gap;
                        }
                        else
                        {
                            j = 0;
                        }
                    }
                    gap = gap / 2;        // 减小增量
                }
            }
        }
        希尔排序的实质还是一种插入排序，但它是一种不稳定的排序方法。希尔排序算法的时间复杂度是O(nlog₂n)。