快速排序

快速排序是从冒泡排序演变而来的算法，但是比冒泡排序要高效得多，所以叫做快速排序。

快速排序之所以快速，是因为它使用了分治法，同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。

不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。

基本思想

• 先从数列中取出一个数作为基准数。

• 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

• 再对左右区间重复第二步，直到各区间只有一个数。

性能

时间复杂度为O(nlgn)，与归并排序不同，该算法占用常数级额外存储，在大规模序列排序应用中性能较好。

基准元素如何选择呢？

基准元素，英文pivot，用于在分治过程中以此为中心，把其他元素移动到基准元素的左右两边。

那么基准元素如何选择呢？

最简单的方式是选择数列的第一个元素，但是如果有一个原本逆序的数列，期望排序成顺序数列，那么会出现什么情况：这种极端情况下，快速排序需要进行n轮，时间复杂度退化成了n^2。

递归实现

void quick_sort(vector<int>& nums, int l, int r)
{
    if(l+1 > = r)
    {
        return;
    }

    int first = l, last = r - 1, key = nums[first];
    while(first < last)
    {
        while(first < last && nums[last] >= key)
        {
            --last;
        }
        nums[first] = nums[last];

        while(first < last && num[first] <= key)
        {
            ++first;
        }
        num[last] = num[first];
    }
    nums[first] = key;
    quick_sort(nums, l, first);
    quick_sort(nums, first+1, r);
}

非递归实现

#include<iostream>
#include<stack>
#include<stdlib.h>
using namespace std;
int Partition(int *data, int low, int high)
{
    int temp = data[low];
     while(low < high)
     {
        while(data[j] > temp)
        {
            high--;
        }
        if(low < high)
        {
            data[low] = data[high];
        }
        while(data[i] < temp)
        {
            low++;
        }
        if(low < high)
        {
           data[j] = data[i];
        }       
    }
    data[low] = temp;    //low == high
    return low;
}

void QuickSort(int *data, int len)
{
    if(data == NULL || len <= 0)
    {
        return;
    }
    stack<int> st;
    int low = 0;
    int high = len -1;
    st.push(low);
    st.push(high);
    while(!st.empty())
    {
        high = st.top();st.pop();
        low = st.top();st.pop();
        int par = Partition(data, low, high);
        if(low < par - 1)
        {
            st.push(low);
            st.push(par - 1);
        }
        if(high > par + 1)
        {
            st.push(par + 1);
            st.push(high);   
        }
    }
}