眾所周知，最優(yōu)的排序算法的復(fù)雜度是O（nlogn）,但在學(xué)習(xí)最優(yōu)算法前，我們先來看看O（n^2）復(fù)雜度的算法，由簡(jiǎn)入難。

算法描述：首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序的代碼：

void selectionSort(int 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]);
    }
}

選擇排序的改進(jìn)

為了讓selectionSort（）能接受不同類型（float,string ,char,或自定義類型）的數(shù)組，使用模板函數(shù)對(duì)其進(jìn)行改進(jìn)：

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

隨機(jī)生成數(shù)組

當(dāng)采用的數(shù)組個(gè)數(shù)較大時(shí)，不可能一個(gè)一個(gè)的列舉出來，這里編寫一個(gè)隨機(jī)生成數(shù)組的程序，用來輔助數(shù)組的排序。此處建立一個(gè)命名空間SortTestHelper，用來放與排序測(cè)試相關(guān)的各種函數(shù)，包括生產(chǎn)隨機(jī)數(shù)組generateRandomArray（）、printArray()、testSort（）、isSorted（）等。
generateRandomArray（）的實(shí)現(xiàn)

 //生成有n個(gè)元素的隨機(jī)數(shù)組，每個(gè)元素的隨機(jī)范圍為[rangeL,rangeR]
    int *generateRandomArray(int n, int rangeL, int rangeR)
    {
        assert(rangeL <= rangeR);//#include<cassert>
        int *arr = new int[n];
        srand(time(NULL));//#include<ctime>
        for (int i = 0; i < n; i++)
        {
            arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
        }
        return arr;
    }

測(cè)試代碼如下：

#include<iostream>
#include"SortTestHelper.h"
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]);
    }
}
int main()
{
    int n = 1000;
    int *arr = SortTestHelper::generateRandomArray(n, 0, n);
    selectionSort(arr, n);
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << ",";
    }
    cout << endl;
    delete[] arr;//注意要釋放掉內(nèi)存空間，否則發(fā)生內(nèi)存泄漏
    system("pause");
    return 0;
}

上述打印過程也可放在SortTestHelper（）命名空間中：
printArray()

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

則測(cè)試代碼重新寫如下：

    int n = 1000;
    int *arr = SortTestHelper::generateRandomArray(n, 0, n);
    selectionSort(arr, n);
    SortTestHelper::printArray(arr, n);
    delete[] arr;

如何衡量一個(gè)排序算法的性能？

算法在某個(gè)數(shù)據(jù)集上的執(zhí)行時(shí)間可以衡量該算法的性能。接下來在SortTestHelper（）空間中寫一個(gè)衡量算法性能的函數(shù)testSort（）
testSort()

//測(cè)試算法性能，傳入的參數(shù)包括算法名稱、算法函數(shù)本身，測(cè)試用例及用例長(zhǎng)度
    template<typename T>
    void testSort(string sortName, void(*sort)(T[], int),T arr[],int n)
    {
        //clock_t表示時(shí)鐘周期的數(shù)據(jù)
        clock_t startTime = clock();
        sort(arr, n);
        clock_t endTime = clock();
        assert(isSorted(arr, n));
        //兩次時(shí)鐘周期差表示算法真正執(zhí)行的時(shí)鐘周期，CLOCKS_PER_SEC每秒時(shí)鐘周期個(gè)數(shù)
        cout << sortName << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
        return;
    }

如何衡量排序算法的正確性？

代碼如下：
isSorted()

//測(cè)試排序算法執(zhí)行的正確性
    template<typename T>
    bool isSorted(T arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                return false;
            }
            return true;
        }
    }

測(cè)試排序算法的性能

#include<iostream>
#include"SortTestHelper.h"
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]);
    }
}
int main()
{
    int n = 10000;
    int *arr = SortTestHelper::generateRandomArray(n, 0, n);
    SortTestHelper::testSort("selectionSort:", selectionSort, arr, n);
    delete[] arr;
    system("pause");
    return 0;
}

整個(gè)SortTestHelper（）空間的代碼如下：

#ifndef SELECTIONSORT_SORTTESTHELPER_H
#define SELECTIONSORT_SORTTESTHELPER_H
#include<iostream>
#include<string>
#include<ctime>
#include<cassert>
using namespace std;
namespace SortTestHelper
{
    //生成有n個(gè)元素的隨機(jī)數(shù)組，每個(gè)元素的隨機(jī)范圍為[rangeL,rangeR]
    int *generateRandomArray(int n, int rangeL, int rangeR)
    {
        assert(rangeL <= rangeR);//#include<cassert>
        int *arr = new int[n];
        srand(time(NULL));//#include<ctime>
        for (int i = 0; i < n; i++)
        {
            arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;
        }
        return arr;
    }
    template<typename T>
    void printArray(T arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            cout << arr[i] << " ,";
        }
        cout << endl;
        return;
    }
    //測(cè)試算法執(zhí)行的正確性
    template<typename T>
    bool isSorted(T arr[], int n)
    {
        for (int i = 0; i < n; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                return false;
            }
            return true;
        }
    }
    //測(cè)試算法性能，傳入的參數(shù)包括算法名稱、算法函數(shù)本身，測(cè)試用例及用例長(zhǎng)度
    template<typename T>
    void testSort(string sortName, void(*sort)(T[], int),T arr[],int n)
    {
        //clock_t表示時(shí)鐘周期的數(shù)據(jù)
        clock_t startTime = clock();
        sort(arr, n);
        clock_t endTime = clock();
        assert(isSorted(arr, n));
        //兩次時(shí)鐘周期差表示算法真正執(zhí)行的時(shí)鐘周期，CLOCKS_PER_SEC每秒時(shí)鐘周期個(gè)數(shù)
        cout << sortName << double(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
        return;
    }
}
#endif  

說明：本文是在聽了波波老師的數(shù)據(jù)結(jié)構(gòu)算法課程后所做的筆記！