希尔排序

希尔排序是插入排序的一种. 是针对直接插入排序算法的改进. 也称为"缩小增量排序"
DL.Shell于1959年提出.
方式: 比较相距一定间隔的元素, 随排序的进行, 逐渐缩小间隔. 直到只比较相领元素的最后一次排序为止.
时间复杂度为 O(n log n);

#include <iotream>
#include <vector>
#include <random>

// 打印数组
void printArr(std::vector<int>& arr) {
    std::cout << "{" ;
    for(int num: arr) {
        std::cout << num << ", ";
    }
    std::cout << "}" << std::endl;
}

// 生成随机数组
std::vector<int> generateRandomArr(int length, int minVal, int maxVal) {
    // 定义随机种子接口
    std::random_device rd;
    // 构造依随机数生成器
    std::mt19937 gen(rd());
    // 定义均匀分布的随机数生成器
    std::uniform_int_distribution<int> dis(minVal, maxVal);
    
    // 定义数组
    std::vector<int> arr(length);
    
    for(int i = 0; i < length; i++) {
        arr[i] = dis(gen);
    }
    return arr;
}

// 希尔排序
void shellSort(std::vector<int>& arr) {
    int len = arr.size();
    for(int gap = len/2; gap > 0; gap /= 2) {
        for(int i = gap; i < len; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j > gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

int main() {
    int length = 20;
    int min_val = 1;
    int max_val = 100;
    
    std::vector<Int> arr = generateRandomArr(length, min_val, max_val);
    std::cout << "The Origin: ";
    printArr(arr);
    shellSort(arr);
    std::cout << "After Sorted: ";
    printArr(arr);
    
    return 0;
}