一. 算法描述

　　

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

　　

增量的选择

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

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

二.算法实现

#include 
     
       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("\n"); }
     

三.算法分析

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

参考资料

　　[1] 

　　[2]