希尔排序－Shell Sort

　　希尔排序又称”缩小增量排序”，我们知道插入排序，插入排序的时间复杂度为Ｏ(n^2)。对于插入排序，当ｎ值较小时，效率会提升；当待排序列为＂基本有序1＂时，效率会提高，接近于Ｏ(n)。希尔排序正是对插入排序在这两点上做出优化的一种排序方法。
　　它的基本思想就是，将整个待排序列分割成若干个小的序列（由一个增量相隔）将其分别进行插入排序，然后缩小增量再次分割排序，直到整个元素基本有序时，在对全体进行排序（增量为１）。

　　对于数组arr[] = {5,6,7,3,2,4,1,3,1,4};
　　
　　第一趟，增量为sz/2 = 5
　　
　　
　　第二趟，增量为5/2 = 2
　　
　　
　　第三趟，增量为2/2 = 1，即将第二趟结果进行插入排序
　　

排序完成

代码如下：

#include<stdio.h>

//sz数组总长度,n为组的起始位置,gap为的步长
void insertion_sort(int *arr,int sz,int n,int gap)
{
    int i,j,temp;
    for(i=n+gap; i<sz; i+=gap)
    {
        if(arr[i] < arr[i-gap])//每个元素与组内元素插入排序
        {
            temp = arr[i];
            j = i-gap;
            while(j>=0 && temp<arr[j])
            {
                arr[j+gap] = arr[j];
                j -= gap;
            }
            arr[j+gap] = temp;
        }
    }
}


void shell_sort(int *arr,int sz)//sz为待排数组长度
{
    int n,gap;

    //gap为步长,每次减少一半
    for(gap=sz/2; gap>0; gap/=2)
    {
        for(n=0; n<gap; n++)//共gap个组,对每组进行插入排序
          insertion_sort(arr,sz,n,gap);
    }
}

int main()
{
    int i;
    int arr[] = {5,6,7,3,2,4,1,3,1,4};
    int sz = sizeof(arr)/sizeof(arr[0]);

    shell_sort(arr,sz);

    for(i=0; i<sz; i++)
        printf("%d ",arr[i]);
    return 0;
}

---

1. 基本有序的意思就是，待排序列中大多数小的元素在前面，大的元素在后面 ↩