4 希尔排序

4.1 描述
先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；
然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。

4.2 复杂程度
时间复杂度O(n^1.3)                 
空间复杂度O(1)

4.3 代码

void ShellSort(int *arr, int size)  
{  
    int i, j, tmp, increment;  
    for (increment = size/ 2; increment > 0; increment /= 2) 
    {    
        for (i = increment; i < size; i++) 
        {  
            tmp = arr[i];  
            for (j = i - increment; j >= 0 && tmp < arr[j]; j -= increment) 
            {  
                arr[j + increment] = arr[j];  
            }  
            arr[j + increment] = tmp;
        }  
    }  
} 
int main() 
{
    int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    ShellSort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    return 0;
}

4.4 运行时间
0.02275s