算法课程笔记——盘点排序7*希尔排序

类比插入排序

#include<iostream>#include<vector>usingnamespacestd;

voidshellSort(vector<int>& arr){
    intn = arr.size();
    // 初始增量为数组长度的一半for(intgap = n / 2; gap > 0; gap /= 2) {
        // 从gap开始进行插入排序for(inti = gap; i < n; i++) {
            int temp = arr[i];
            intj;
            // 插入排序核心代码for(j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp           / 临时变量
        }
    }
}

intmain(){
    intn;
    cin >> n;
    vector<int> arr(n);
    for(inti = 0; i < n; i++) {
        cin >> arr[i];
    }
    shellSort(arr);
    for(inti = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return0;
}