快速排序

快速排序算法和合并排序算法一样，也是基于分治模式。对子数组A[p...r]快速排序的分治过程的三个步骤为：
分解：把数组A[p...r]分为A[p...q-1]与A[q+1...r]两部分，其中A[p...q-1]中的每个元素都小于等于A[q]而A[q+1...r]中的每个元素都大于等于A[q]；
解决：通过递归调用快速排序，对子数组A[p...q-1]和A[q+1...r]进行排序；
合并：因为两个子数组是就地排序的，所以不需要额外的操作。

快速排序算法的伪代码：

 

1. QUICKSORT(A, p < r) {
2. 1 if p < r {
3. 2 q = PARTITION(A, p, r);
4. 3 QUICKSORT(a, p, q-1);
5. 4 QUICKSORT(a, q+1, r);
6. 5 }
7. }

这个算法的关键在于数组的划分，即PARTITION：

1. PARTITION(A, p, r) {
2. 1 x = A[r];
3. 2 i = p-1;
4. 3 for j = p to r-1 {
5. 4   if A[j] ≤ x {
6. 5      i = i + 1;
7. 6      exchange(A[i], A[j]);
8. 7     }
9. 8 }
10. 9  exchange(A[i+1], A[r]);
11. 10 return i+1;
12. }

#include<iostream>

using std::cout;
using std::endl;
using std::cin;


int Partition(int data[],int start,int end)
{
    if (data==NULL||start<0||end<0||end<=start)
    {
        throw std::exception("Invalid parameters");
    }
    int pnum = data[end];
    int i = start - 1;

    for (int j = start; j < end;++j)
    {
        if (data[j]<=pnum)
        {
            ++i;
            std::swap(data[i], data[j]);
        }
    }

    std::swap(data[++i], data[end]);

    return i;
}

void quicksort(int data[],int start,int end)
{
    if (data==NULL||end<start)
    {
        throw std::exception("Invalid parameters");
    }
    if (end==start)
    {
        return;
    }
    int q = Partition(data,start,end);
    if (q>start)
    {
        quicksort(data, start, q - 1);
    }
    if (q<end)
    {
        quicksort(data, q + 1, end);
    }
                                                                                       
}

int main()
{
    int a[10] = {2,4,6,5,8,9,2,10,8,1};
    

    quicksort(a, 0, 9);

    for (int i = 0; i < 10;++i)
    {
        cout << a[i] << " ";
    }

    return 0;
}