主要介紹選擇排序和插入排序。
冒泡排序和希爾排序簡單過過。
另外希爾排序時間復(fù)雜度不能確定，要看d的取值

所以排序算法中，只有冒泡排序、插入排序、基數(shù)排序、歸并排序是穩(wěn)定的，其它都不穩(wěn)定。

選擇排序

#include <iostream>
#include <algorithm>

using namespace std;

void selectionSort(int 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] );     //在c++11標(biāo)準(zhǔn)中，swap是在標(biāo)準(zhǔn)庫里
    }

}

int main() {

    int a[10] = {10,9,8,7,6,5,4,3,2,1};
    selectionSort(a,10);
    for( int i = 0 ; i < 10 ; i ++ )
        cout<<a[i]<<" ";
    cout<<endl;

    return 0;
}

當(dāng)然這里也可以用模版來寫這個排序算法，即泛型編程。
需要注意的是如果參與排序的是結(jié)構(gòu)體，需要對結(jié)構(gòu)體進行運算符重載，一個是<(或>,看情況決定)，還有<<,重載<< 為了符合規(guī)范，需要寫友元函數(shù)。
順便記錄一個生成偽隨機數(shù)數(shù)組的函數(shù)和一個計算算法時間效率的函數(shù)

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

struct Student{

    string name;
    int score;

    // 重載小于運算法,定義Student之間的比較方式
    // 如果分?jǐn)?shù)相等，則按照名字的字母序排序
    // 如果分?jǐn)?shù)不等，則分?jǐn)?shù)高的靠前
    bool operator<(const Student& otherStudent){
        return score != otherStudent.score ?score > otherStudent.score : name < otherStudent.name;
//這里的三目運算符用法需要注意下，看上去讓代碼簡潔很多
    }

    // 重載<<符號, 定義Student實例的打印輸出方式
    friend ostream& operator<<(ostream &os, const Student &student){

        os<<"Student: "<<student.name<<" "<<student.score<<endl;
        return os;
    }
};

/*
聲明結(jié)構(gòu)體數(shù)組時可以這樣
Student d[4] = { {"D",90} , {"C",100} , {"B",95} , {"A",95} };
*/



// 生成有n個元素的隨機數(shù)組,每個元素的隨機范圍為[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;
    }

template<typename T>
    void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {
//第二個參數(shù)是函數(shù)指針
        clock_t startTime = clock();    //頭文件是ctime/time.h
        sort(arr, n);
        clock_t endTime = clock();

        cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;

        return;
    }

選擇排序的優(yōu)化算法

// 在每一輪中, 可以同時找到當(dāng)前未處理元素的最大值和最小值
template<typename T>
void selectionSort(T arr[], int n){

    int left = 0, right = n - 1;
    while(left < right){
        int minIndex = left;
        int maxIndex = right;

        // 在每一輪查找時, 要保證arr[minIndex] <= arr[maxIndex]
        if(arr[minIndex] > arr[maxIndex])
            swap(arr[minIndex], arr[maxIndex]);

        for(int i = left + 1 ; i < right; i ++)
            if(arr[i] < arr[minIndex])
                minIndex = i;
            else if(arr[i] > arr[maxIndex])
                maxIndex = i;

        swap(arr[left], arr[minIndex]);
        swap(arr[right], arr[maxIndex]);

        left ++;
        right --;
    }

    return;
}

插入排序

兩種寫法,優(yōu)先選第二種，較為優(yōu)美

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

    for( int i = 1 ; i < n ; i ++ ) {

        // 尋找元素arr[i]合適的插入位置
        // 寫法1
//        for( int j = i ; j > 0 ; j-- )
//            if( arr[j] < arr[j-1] )
//                swap( arr[j] , arr[j-1] );
//            else
//                break;

        // 寫法2
        for( int j = i ; j > 0 && arr[j] < arr[j-1] ; j -- )
            swap( arr[j] , arr[j-1] );

    }

    return;
}

上面的算法，在序列無序時，插入排序是比選擇排序性能略低的。
但當(dāng)序列是接近有序時，插入排序是比選擇排序性能高的，即便優(yōu)化后的選擇排序依舊如此。
除此之外，上面的插入排序還可以優(yōu)化，如下：

插入排序的優(yōu)化

void insertionSort(T arr[], int n){

    for( int i = 1 ; i < n ; i ++ ) {

        T e = arr[i];
        int j;                        // j保存元素e應(yīng)該插入的位置
        for (j = i; j > 0 && arr[j-1] > e; j--)
            arr[j] = arr[j-1];
        arr[j] = e;
    }

    return;
}

冒泡排序

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

    bool swapped;

    do{
        swapped = false;
        for( int i = 1 ; i < n ; i ++ )
            if( arr[i-1] > arr[i] ){
                swap( arr[i-1] , arr[i] );
                swapped = true;

            }

        // 優(yōu)化, 每一趟Bubble Sort都將最大的元素放在了最后的位置
        // 所以下一次排序, 最后的元素可以不再考慮
        n --;

    }while(swapped);
}

冒泡排序的優(yōu)化

//使用newn進行優(yōu)化
template<typename T>
void bubbleSort2( T arr[] , int n){

    int newn; // 使用newn進行優(yōu)化

    do{
        newn = 0;
        for( int i = 1 ; i < n ; i ++ )
            if( arr[i-1] > arr[i] ){
                swap( arr[i-1] , arr[i] );

                // 記錄最后一次的交換位置,在此之后的元素在下一輪掃描中均不考慮
                newn = i;
            }
        n = newn;
    }while(newn > 0);
}

希爾排序

希爾排序可以看作是插入排序的升級版
時間復(fù)雜度：O(n^(1.3—2))

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

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

// ShellSort是這四種排序算法中性能最優(yōu)的排序算法