排序算法之希尔排序

希尔排序

基本思想

先将整个待排序的记录序列按照指定增量分割成为若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

这里的增量选取目前还是一个数学难题，迄今为止没有人找到一种最好的增量序列。

其中的基本有序是指：小的关键字基本在前面，大的基本在后面， 不大不小的基本在中间，例如{2,13,,6,4,7,5,8,9}可以称得上基本有序了。而{1,5,9,3,7,8,2,4,6}这样的9在第三位，2在倒数第三位就谈不上基本有序了。
原理图

代码如下：

/**希尔排序*/
void shellSort(int a[],int aLength)
{
    int i,j,k,temp;
    k = aLength/2;    //k为增量
    while (k>0) {
        for (i=k; i<aLength; i++) {
            temp = a[i];
            for (j=i-k; j>=0; j = j-k) {
                if (a[j]>temp) {
                    a[j+k] = a[j];
                }else
                {
                    break;
                }
            }
            a[j+k] = temp;
        }
        k = k/2;

    }
}

以上就是希尔排序的简单介绍了，希望能够帮助到大家。