关于不同排序算法的性能比较

一个排序算法性能测试的c++实现，用于测试不同排序算法的耗时，代码如下：

//
// Created by  Maksim on 2017/5/15.
//

#ifndef SELECTIONSORT_SORTTESTHELPER_H
#define SELECTIONSORT_SORTTESTHELPER_H

#include <iostream>
#include <ctime>
#include <cassert>


using namespace std;

namespace SortTestHelper{

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

    /**
     * 生成一个近乎有序的随机数组,非常适合用插入排序算法
     * @param n
     * @param swapTimes
     * @return
     */
    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;
    }

    template<typename T>
    void printArray(T arr[],int n){
        for (int i = 0; i < n; ++i) {
            cout<< arr[i]<<" ";
        }
        cout<<endl;
    }

    template <typename T>
    void selectionSort(T arr[], int n){

        for(int i = 0 ; i < n ; i ++){
            // 寻找[i, n)区间里的最小值
            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 insertSort(T arr[],int n){
        for (int i = 1; i < n; ++i) {
            T e=arr[i];  //临时容器存放当前需要进行排序的数字
            int j;
            //寻找arr[i]合适的插入位置
            for (j = i ; j > 0 && arr[j-1] > e  ; j--) {  //如果前面一个比e还大 那还需要往前看，直到找到比e小的停止，或者找到了数组的第一个元素
                arr[j]=arr[j-1]; //将前面那个大的赋值给j元素
            }
            arr[j]=e;  //将临时容器的元素赋值给j元素
        }
    }

    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

比较直接排序与选择排序示例：

#include <iostream>
#include <algorithm>
#include <string>

#include "Student.h"
#include "SortTestHelper.h"


using namespace std;

int main() {
    int n =100000;

    int *arr=SortTestHelper::generateNearlyOrderedArray(n,100);
    int *arr2=SortTestHelper::copyIntArray(arr,n);

    SortTestHelper::testSort("Insert Sort",SortTestHelper::insertSort,arr ,n);
    SortTestHelper::testSort("Select Sort",SortTestHelper::selectionSort,arr,n);

    delete[] arr;
    delete[] arr2;

    return 0;
}

测试结果：

Insert Sort : 0.022083 s
Select Sort : 14.38 s