The following programs are the comparision of between selectionSort and insertionSort.

//SortTestHelper.h file
#ifndef SELECTIONSORT_SORTTESTHELPER_H
#define SELECTIONSORT_SORTTESTHELPER_H

#include <iostream>
#include <cassert>
#include <ctime>
#include <string>
using namespace std;

namespace SortTestHelper {

//produce an random array
    int * generateRandomArray(int n,int rangL, int rangR) {
        assert(rangR >= rangL);//judge the boundary of the array

        int *arr = new int[n];
        srand(time(NULL));//the seed of random

        for (int i = 0; i < n; i++)
        {
            arr[i] = rand() % (rangR - rangL) + rangL;//value the array
        }

        return arr;
    }

//print the elements of the array
    template <typename T>
    void printArr(T arr[], int n) {
        for (int i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << endl;
        return;
    }

//judge the array is a sorted array or not
    template <typename T>
    bool is_Sorted(T arr[], int n) {
        for (int i = 0; i < n - 1; i++)
        {
            if (arr[i] > arr[i + 1])
                return false;
        }

        return true;
    }

//a test function to calculate the using time
    template <typename T>
    void testSort(string sortName, void(*sort)(T[], int n), T arr[], int n) {
        clock_t startTime = clock();
        sort(arr, n);
        clock_t endTime = clock();

        assert(is_Sorted(arr, n));

        cout << sortName << ":" << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
        return;
    }
//a function to copy an integer array
    int * copyIntArray(int a[], int n) {
        int * arr = new int[n];
        copy(a, a + n, arr);//三個參數(shù)分別是頭指針，尾指針和目標(biāo)屬組
        return arr;
    }

}

#endif // !SELECTIONSORT_SORTTESTHELPER_H

//main driver program
#include <iostream>
#include <algorithm>
#include "SortTestHelper.h"
using namespace std;

//選擇排序
template <typename T>
void selectionSort(T arr[], int n) {

    for (int i = 0; i < n; i++)
    {
        //尋找[i,n)區(qū)間里的最小值
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;

        swap(arr[i], arr[minIndex]);
    }
}

//插入排序
template <typename T>
void insertionSort(T arr[], int n) {
    for (int i = 1; i < n; i++)
    {   //尋找元素arr[i]合適的插入位置
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            swap(arr[j], arr[j - 1]);
        }
                
    }
}

int main()
{
    int n = 10000;
    int *arr = SortTestHelper::generateRandomArray(n, 0, n);
    int *arr2 = SortTestHelper::copyIntArray(arr, n);
    //selectionSort(arr, n);
    //SortTestHelper::printArr(arr, n);
    SortTestHelper::testSort("SelectionSort", selectionSort, arr2, n);
    SortTestHelper::testSort("InsertionSort", insertionSort, arr, n);
    delete[] arr;
    delete[] arr2;
    getchar();
    return 0;
}

//the improvement of the insertionSort
#include <iostream>
#include <algorithm>
#include "SortTestHelper.h"
using namespace std;

//選擇排序
template <typename T>
void selectionSort(T arr[], int n) {

    for (int i = 0; i < n; i++)
    {
        //尋找[i,n)區(qū)間里的最小值
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;

        swap(arr[i], arr[minIndex]);
    }
}

//插入排序
template <typename T>
void insertionSort(T arr[], int n) {
    for (int i = 1; i < n; i++)
    {   //尋找元素arr[i]合適的插入位置
        T e = arr[i];
        int j;
        for (j = i; j > 0 && arr[j-1] > e; j--) {
            arr[j] = arr[j - 1];//判斷當(dāng)前元素是否要待到當(dāng)前位置，判斷條件是當(dāng)前元素與前一個元素進行比較
        }
        arr[j] = e;
                
    }
}

int main()
{
    int n = 10000;
    int *arr = SortTestHelper::generateRandomArray(n, 0, n);
    int *arr2 = SortTestHelper::copyIntArray(arr, n);
    //selectionSort(arr, n);
    //SortTestHelper::printArr(arr, n);
    SortTestHelper::testSort("SelectionSort", selectionSort, arr2, n);
    SortTestHelper::testSort("InsertionSort", insertionSort, arr, n);
    delete[] arr;
    delete[] arr2;
    getchar();
    return 0;
}

//生成一個近乎有序的數(shù)組
    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 j = 0; j < swaptimes; j++) {
            int posx = rand() % n;
            int posy = rand() % n;

            swap(arr[posx], arr[posy]);
        }
        return arr;
    }