Algorithm -- Shell Sort-蒲公英云

Algorithm -- Shell Sort

SortTestHelper.h

#ifndef SELECTIONSORT_SORTTESTHELPER_H
#define SELECTIONSORT_SORTTESTHELPER_H
#include <iostream>
#include <ctime>
#include <cassert>
using namespace std;
namespace SortTestHelper {
    // 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
    int *generateRandomArray(int n, int rangeL, int rangeR) {
        assert(rangeL <= rangeR);
        int *arr = new int[n];
        srand(time(NULL));
        for (int i = 0; i < n; i++)
            arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
        return arr;
    }
    int *generateNearlyOrderedArray(int n, int swapTimes) {
        int *arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = i;
        }
        srand(time(NULL));
        for (int i = 0; i < swapTimes; ++i) {
            int posx = rand() % n;
            int posy = rand() % n;
            swap(arr[posx], arr[posy]);
        }
        return arr;
    }
    // 打印arr数组的所有内容
    template<typename T>
    void printArray(T arr[], int n) {
        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;
        return;
    }
    template<typename T>
    bool isSorted(T arr[], int N) {
        for (int i = 0; i < N - 1; ++i) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
    template<typename T>
    void testSort(string sortName, void(*sort)(T[], int), T arr[], int N) {
        clock_t startTime = clock();
        sort(arr, N);
        clock_t endTime = clock();
        assert(isSorted(arr, N));
        cout << sortName << ":" << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
        return;
    }
    int *copyIntArray(int a[], int n) {
        int *arr = new int[n];
        copy(a, a + n, arr);
        return arr;
    }
};
#endif //SELECTIONSORT_SORTTESTHELPER_H

main.cpp

#include <iostream>
#include "SortTestHelper.h"
using namespace std;
template<typename T>
void shellSort(T arr[], int n) {
    // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
    int h = 1;
    while (h < n / 3)
        h = 3 * h + 1;
    while (h >= 1) {
        // h-sort the array
        for (int i = h; i < n; i++) {
            // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
            T e = arr[i];
            int j;
            for (j = i; j >= h && e < arr[j - h]; j -= h)
                arr[j] = arr[j - h];
            arr[j] = e;
        }
        h /= 3;
    }
}
int main() {
    int n = 10000;
    /*int *arr = SortTestHelper::generateNearlyOrderedArray(n, 100);*/
    int *arr = SortTestHelper::generateRandomArray(n, 0, n);
    SortTestHelper::testSort("Shell Sort", shellSort, arr, n);
    delete[] arr;
    return 0;
}