/*****************************
*quickSort.h
******************************/
#include "stdafx.h"
#include <vector>
 
using namespace std;
template <typename T>
void quickSort(vector<T>& vec)
{
    quickSort(vec, 0, vec.size()-1);
}
 
template <typename T>
void quickSort(vector<T>& vec, int left, int right)
{
    while (left >= right)
    {
        return;
    }
    int low        = left;
    int high   = right;
    T   pivot    = vec[left];
    while(low < high)         // 循环，交换pivot左边和右边的数，直至所有左边的数小于pivot，所有右边的数大于pivot
    {
        while (low < high && pivot <= vec[high])
            high--;
        vec[low] = vec[high];   //一次交换中把小的数放到左边
        while(low < high && pivot >= vec[low])
            low ++;
        vec[high] = vec[low];   //一次交换中把大的数放到右边
    }
    vec[low] = pivot;    // 循环结束，此时low = high ，
 
    //将pivot两边的数组继续递归排序
    quickSort(vec, left, low -1);    
    quickSort(vec, high+1, right);
}