学步园

谢尔排序又称缩小增量排序法，是由D.L.Shell在1959年提出的。

算法描述：

首先确定一个元素间隔数gap，然后将参加排序的序列按此间隔数从第一个元素开始依次分成若干个子序列，即分别将所有位置相隔为gap的元素视为一个子序列，在各个子序列中采用某种排序算法进行排序，然后减小间隔数，并重新将整个序列采用新的间隔数分成若干个子序列，再对子序列进行排序，然后再减小间隔数gap，直到gap = 1. 如：

输入数据：

a0 = 5. a1 = 12, a2 = 3, a3 = 45, a4 = 76, a5 = 98, a6 = 90, a7 = 12, a8 = 9, a9 = 66, a10 = 35, a11 = 99, a12 = 10;

第一趟排序的gap = 5，用插入排序算法排序由gap分隔而成的子数组：(a0, a5, a10), (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9)

排序结果：

a0 = 5, a1 = 12,  a2 = 3,  a3 = 9, a4 = 76, a5 = 35,  a6 = 90,  a7 = 10,  a8 = 45, a9 = 66, a10 = 98,  a11 = 99,  a12 = 12

第二趟排序的gap = 3，用插入排序算法排序由gap分隔而成的子数组：(a0, a3, a6, a9, a12), (a1, a4, a7, a10), (a2, a5, a8, a11)

排序结果：

a0 = 5, a1 = 10,  a2 = 3,  a3 = 9, a4 = 12, a5 = 35,  a6 = 12,  a7 = 76,  a8 = 45, a9 = 66, a10 = 98,  a11 = 99,  a12 = 90

第三趟排序的gap = 1， 对整个数组进行插入排序

由以上的分析可以知道：

1. 设定gap的值为 x，则由gap分隔而成的子数组就会有gap个，我们需要对这些子数组用插入排序算法排序。

2. 由于对子序列的排序导致元素之间的交换间隔很大，所以该排序方法是不稳定的排序方法。

先看伪代码：

//gaps中存储的是划分的间隔数gap，依次减小到1
for gap in gaps
    for (i = 0; i < gap; ++i)      //i 控制对所有的由gap分隔成的子序列进行排序
        //以下的代码就是对每个子序列进行插入排序
        for(j = i + gap; j < n; ++j)    //j 控制对每个子序列进行插入排序的趟数
            k = j - gap;
            temp = array[j];
            if(k >= i and temp < array[k])
                array[k + gap] = array[k]
                k -= gap
            array[k + gap] = temp

下面的代码是我用C语言写的，我这里取的gap = n，然后 gap /= 2, 直到gap = 1

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

void print_array(int array[], int size)
{
    int i;
    for( i = 0 ; i < size ; ++i )
    {
        printf("%d ", array[i]);
    }
    printf("\n");
}

void insertSort(int array[], int first, int n, int gap)
{
    int i, j, temp;
    for( i = first + gap ; i < n ; i += gap )
    {
        j = i - gap;
        temp = array[i];
        while( j >= first && temp < array[j] )
        {
            array[j + gap] = array[j];
            j -= gap;
        }
        array[j + gap] = temp;
    } 
}

void shellSort(int array[], int n)
{
    int i, j, gap = n;
    while( gap > 1 )
    {
        gap = gap / 2;
        for( i = 0 ; i < gap ; ++i )
        {
            insertSort(array, i, n, gap);
        }
        //print_array(array, n);
    }
}

int main()
{
    int array[] = {5, 12, 3, 45, 76, 98, 90, 12, 9, 66, 35, 99, 10};
    int size = sizeof(array) / sizeof(int);
    shellSort(array, size);
    print_array(array, size);
}

上面的shell排序编码是严格按照算法思路来编写的，其实可以直接用如下的编码代替，具体不再阐述。

void shellSort(int array[], int n)
{
    for(int gap = n/2; gap > 0; gap /= 2)
        for(int i = gap; i < n; ++i)
        {
            int temp = array[i];
            int j = i - gap;
            while(j >= 0 && temp < array[j])
            {
                array[j+gap] = array[j];
                j -= gap;
            }
            array[j+gap] = temp;
        }
}