（简单）快速排序

关键在于找一个基准（一般选第一个元素）

• 小于基准的放左边，大于的放右边
• 递归

//quickSort.h

#ifndef _QUICK_SORT_H_
#define _QUICK_SORT_H_

#include <vector>

using std::vector;
using std::swap;

void quickSort(vector<int> &nums, int begin, int end);

#endif //_QUICK_SORT_H_

//quickSort.cc

#include "quickSort.h"
void quickSort(vector<int> &nums, int begin, int end) {
    if(begin >= end) {	//递归结束的条件
        return;
    }
    
    int left = begin;	
    int right = end;
    int key = nums[left];
    while(left < right) {
        while(left < right && nums[right] >= key) {
            --right;
        }
        if( left < right) {
            nums[left] = nums[right];
            ++left;
        }
        while(left < right && nums[left] <= key) {
            ++left;
        }
        if(left < right) {
            nums[right--] = nums[left];
        }
    }

    nums[left] = key;
    
    quickSortCore(nums, begin,left - 1);
    quickSortCore(nums,left + 1, end);
}

性能提升：采用随机化选择基准值

//quickSort.cc

#include "quickSort.h"
void quickSort(vector<int> &nums, int begin, int end) {
    if(begin >= end) {	//递归结束的条件
        return;
    }
    
    int left = begin;	
    int right = end;
    swap(nums[left], nums[rand()%(end - high + 1)]);//随机选择基准值
    int key = nums[left];
	...
}

• 当输入数组已经有序或接近有序时，选择第一个元素作为基准通常会导致非常不均匀的分割，从而退化为冒泡排序的时间复杂度O(n^2)。

• 实际上，随机化快速排序得到理论最坏情况的可能性仅为1/(2^n)，这使得对于绝大多数输入数据，快速排序都能达到O(n log n)的期望时间复杂度。