【Algorithm】希尔排序

一. 算法描述

　　希尔排序：将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行插入排序；然后再选择一个更小的增量，再将数组分割为多个子序列进行排序......最后选择增量为1，即使用直接插入排序，使最终数组成为有序。

　　增量的选择：在每趟的排序过程都有一个增量，至少满足一个规则 增量关系 d[1] > d[2] > d[3] >..> d[t] = 1 (t趟排序)；根据增量序列的选取其时间复杂度也会有变化。

　　下图详细讲解了一次希尔排序的过程（本例采用首选增量为n/2,以此递推，每次增量为原先的1/2，直到增量为1）：

二.算法实现

#include <stdio.h>
 
int main(){
    int i, j, temp; 
    int gap = 0;
    int a[] = {592,401,874,141,348,72,911,887,820,283};
    int n = sizeof(a)/sizeof(a[0]);
    // 设定增量
    while (gap<=n){
        gap = gap * 3 + 1;
    }
    // 希尔排序
    while (gap > 0) {
        for ( i = gap; i < n; i++ ){
            j = i - gap;
            temp = a[i];             
            while (( j >= 0 ) && ( a[j] > temp )){
                a[j + gap] = a[j];
                j = j - gap;
            }
            a[j + gap] = temp;
        }
        gap = ( gap - 1 ) / 3;
    }
    // 打印输出
    for(i = 0; i < n; i++){
        printf("%d ",a[i]);
    }
    printf("
");

 }

三.算法分析

• 平均时间复杂度：希尔排序的时间复杂度和其增量序列有关系，这涉及到数学上尚未解决的难题；不过在某些序列中复杂度可以为O(n1.3);
• 空间复杂度：O(1)  
• 稳定性：不稳定

参考资料

　　[1] http://blog.csdn.net/cjf_iceking/article/details/7951481

　　[2] http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F