Algorithm -- Shell Sort

╰+哭是因爲堅強的太久メ 2022-06-02 11:25 127阅读 0赞

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;
    }