/*
4.希尔排序
最佳情况：T(n) = O(nlog2 n)
最坏情况：T(n) = O(nlog2 n)
平均情况：T(n) =O(nlog2n)
*/
void shellSort(int* arrays, int n) {
    int gap, k, j, t;
    for(gap = n / 2; gap > 0; gap = gap / 2) {
        for(k = gap; k < n; k++) {
            t = arrays[k];        //待插入的值
            j = k - gap;
            while(j >= 0 && t < arrays[j]) { //内部插入排序
                arrays[j + gap] = arrays[j];
                j = j - gap;
            }
            arrays[j + gap] = t;
        }
    }
}