排序算法三之快速排序

今天，我们要讲最后一个排序内容——快速排序，快速排序目前是用的最多的排序方法，在排序算法一

中我们有一张图，上面记录了快速排序的时间复杂度为O（NlogN），并且快速排序和归并排序一样是一种分治的递归算法。

快速排序算法其实总的来说由四个步骤组成：

1. 判断元素个数，个数为0 or 1 直接返回；
2. 从元素数组中取出一个数作为枢纽元；
3. 讲初枢纽元外的元素进行分类，枢纽元左边的为小于枢纽元的数，枢纽元右边为大于枢纽元的数，如果等于枢纽元呢？左右两边都可以；
4. 对枢纽元两边的元素数组分别执行3步骤，这样递归下去。
   这里在第三步中，我们有一个选取枢纽元的步骤，那么我们是怎么选取枢纽元的呢？选取枢纽元的方法采用了三数中值取法；所谓三数中值取法就是我们取元素数组的第一个元素，最后一个元素和处于数组中间的元素[（left + right）/ 2]，然后，我们对这三个进行排序，选择三个数中大小处于中间的数，假设我们有：8、1、4、9、6、3、5、2、7、0，第一个元素和最后一个元素分别是8和0，数组中间的元素是6，我们对这三个数排序=>0<6<8，因此我们选择6作为枢纽元

用一张图来描述下快速排序的步骤：

接下来就是快速排序的代码：

ElementType Median3(ElementType A[], int left, int right) {
    int center =(left + right)/2
    if(A[left]> A[center])
        Swap(&A[left],&A[center]);
    if(A[left]> A[right])
        Swap(&A[left],&A[right]);
    if(A[center]> A[right])
        Swap(&A[center],&A[right]);
    Swap(&A[center],&A[right -1])
    return A[right -1];
}

void Qsort(ElementType A[], int left, int right) {
    int i, j;
    ElementType pivot;
    pivot = Median3(A, left, right);
    i = left;
    j = right - 1;
    while(true) {
        while(A[++i]< pivot){}
        while(A[--j]> pivot){}
        if(i < j)
            Swap(&A[i],&A[j])
        else
            break;
    }
    Swap(&A[i],&A[right -1]);
    Qsort(A, left, i -1)
    Qsort(A, i +1, right)
}