快速排序（Quicksort一）

快速排序是实践中最快的已知排序方法，平均性能在O(NlogN)，最快在O(N^2)
基本算法是采用分治法
1.将数组根据枢纽或卫兵x，划分成两个子数组，前面的子数组的所有元素<=x，后面的>=x；
2.递归处理两个子数组，递归边界是有0个元素时；
3.合并，无意义，已经排好序了。

以下是最简单的快排实现

function quicksort (A,s,e) {
    if(s==undefined||e==undefined){
        s=0;
        e=A.length-1;
    }
    if(s<e){
        var pivot = partition(s,e);
        quicksort(A,0,pivot-1);
        quicksort(A,pivot+1,e);
    }
    return A;
  
    function partition(p,q){
        var x = A[p];
        var i = p;
        for(var j=p+1;j<=q;j++){
            if(A[j]<=x){
                i++;
                var temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            }
        }
        A[p] = A[i];
        A[i] = x;
        return i;
    }
}
初始调用为quicksort([6,10,13,5,8,3,2,11],0,7)或quicksort([6,10,13,5,8,3,2,11])

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

int partition(int arr[],int p,int q){
    int x = arr[p];
    int i = p;
    for (int j = p+1; j <= q; ++j)
    {
        if(arr[j]<=x){
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[p] = arr[i];
    arr[i] = x;
    return i;
}

void quicksort(int arr[],int p,int q){
    if(p<q){
        int piv = partition(arr,p,q);
        quicksort(arr,p,piv-1);
        quicksort(arr,piv+1,q);
    }
}
int partition2(int arr[],int p,int q){
    int x = arr[p];
    int i = p+1,j = q;
    while(i<j){
        while(arr[i]<=x){
            i++;
        }
        while(arr[j]>x){
            j--;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    arr[p] = arr[j];
    arr[j] = x;
}
void quicksort2(int arr[],int p,int q){
    if(p<q){
        int piv = partition2(arr,p,q);
        quicksort(arr,p,piv-1);
        quicksort(arr,piv+1,q);
    }
}

int main(int argc, char const *argv[])
{
    int arr[] = {6,10,13,5,8,3,2,11};
    // quicksort(arr,0,7);
    quicksort2(arr,0,7);
    for (int i = 0; i < 8; ++i)
    {
        cout<<arr[i]<<"\t";
    }
    return 0;
}