排序——快速排序

#include <iostream>
#include <vector>
using namespace std;

//插入排序的实现，在数据量较小时效率优于快排
template<class T>
void insertSort(vector<T> &a)
{
    int k;
    T tmp;

    for(int j = 1; j < a.size(); ++j){
        tmp = a[j];
        for(k = j - 1; tmp < a[k] && k >=0; --k){
            a[k+1] = a[k];    
        }
        a[k+1] = tmp;
    }
}

// 返回left, center,right三项中的中值
// 将他们排序并隐匿枢纽元
template<class T>
const T &median(vector<T> &a, int left, int right)
{
    int center = (left + right) / 2;

    if(a[center] < a[left])
        swap(a[left], a[center]);
    if(a[right] < a[left])
        swap(a[left], a[right]);
    if(a[right] < a[center])
        swap(a[center], a[right]);

    swap(a[center], a[right - 1]);

    return a[right - 1];
}

// a为数组，left为子数组最左元素下标，right为最右元素的下标
template<class T>
void quickSort(vector<T> &a, int left, int right)
{
    //判断数组规模
    if(left + 10 <= right){
        const T &pivot = median(a, left, right);
        //开始分割
        int i = left, j = right - 1;
        for( ; ; ){
            while(a[++i] < pivot){}
            while(pivot < a[--j]){}
            if(i < j) swap(a[i], a[j]);
            else break;
        }

        swap(a[i], a[right - 1]); //恢复枢纽元

        quickSort(a, left, i - 1); //将小于等于枢纽元的元素排序
        quickSort(a, i + 1, right); //将大于等于枢纽元的元素排序
    }
    else{
        insertSort(a);
    }
}

// 快速排序算法的驱动程序
template<class T>
void quickSort(vector<T> &a)
{
    quickSort(a, 0, a.size() - 1);
}

int main()
{
    vector<int> a = {9,8,7,6,5,4,3,2,1};

    quickSort(a);

    for(int i = 0; i < a.size(); ++i)
        cout << a[i] << '\t' ;

    return 0;
}