希尔排序(C++)

template<typename T>
void shellSort(T arr[], int n) {
    
    // 有很多论文研究各种不同的递增序列，但都无法证明某个递增序列是最好的
    // 该递增序列的计算和使用都比较简单，和复杂递增序列的性能接近
    // 相当于把插入排序的代码将移动元素的距离由1改为h即可
    int h = 1;
    while (h < n / 3) {
        h = h * 3 + 1;
    }
    
    while (h >= 1) {
        for (int i = h; i < n; i++) {
            T insertElement = arr[i];
            int j;
            for (j = i; j >= h && insertElement < arr[j - h]; j -= h) {
                arr[j] = arr[j - h];
            }
            arr[j] = insertElement;
        }
        
        h = h / 3;
    }
    
}