Algorithm -- Insertion Sort

爱被打了一巴掌 2022-06-02 11:22 147阅读 0赞

InsertionSort.h

#ifndef INSERTIONSORT_SELECTIONSORT_H
    #define INSERTIONSORT_SELECTIONSORT_H
    
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    
    template<typename T>
    void selectionSort(T arr[], int n){
    
        for(int i = 0 ; i < n ; i ++){
    
            int minIndex = i;
            for( int j = i + 1 ; j < n ; j ++ )
                if( arr[j] < arr[minIndex] )
                    minIndex = j;
    
            swap( arr[i] , arr[minIndex] );
        }
    }
    
    #endif //INSERTIONSORT_SELECTIONSORT_H

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