经典排序算法：快速排序（Quick Sort）

快速排序算法

快速排序算法被称为20世纪十大算法之一，是最重要的算法之一，是一定要掌握和熟练的！
快速排序的基本思想是：（分治法）
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。

案例分析

假如现在我们要对这个序列，{50,10,90,30,70,40,80,60,20}进行快速排序，序列的原始状态是这样的：

关键代码

//算出中间值关键代码 
int partition(SqList *L, int low, int high){
    int pivotkey = L->r[low];
    while(low < high){
        while(low<high&&L->r[high] >= pivotkey){
            high--;
        }
        swap(L, low, high);
        while(low<high&&L->r[low] <= pivotkey){
            low++;
        }
        swap(L, low, high);
    }
    return low;
}

//对无序序列进行排序 
void qSort(SqList *L, int low, int high){
    int mid;
    if(low < high){
        mid = partition(L, low, high);//算出中间值 
        qSort(L, low, mid-1);//对左边的表递归排序 
        qSort(L, mid+1, high);//对右边的表递归排序 
    }
}

方法qSort表现了我们的算法思想，首先通过partition算出中间值，然后再对两边的值进行递归排序。

partition方法，初始时pivotkey 为50，然后进行逻辑判断。
当high指针所指向的值大于pivotkey，则一直让high指针递减，直到high指向一个比pivotkey小的数时，然后让high指针和low指针的值交换，目的就是为了把较小的值移到左边。图中20会与50交换。
当low指针指向的值小于pivotkey时，则一直让low递增，直到low指向一个比pivotkey大的数时，然后让high指针和low指针的值交换，目的就是为了把较大的值移到右边。图中low指针会移到90，然后90和50交换。

完整代码

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10

typedef struct
{
    int r[MAXSIZE];
    int length;
}SqList;

void swap(SqList *L, int i, int j){
    int temp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = temp;
}

void initSort(SqList *L){
    L->length = 9;
    L->r[0] = 0;
    int a[9] = {50,10,90,30,70,40,80,60,20} ;
    for(int i = 1; i<MAXSIZE; i++){
        L->r[i] = a[i-1];
    }
}

//算出中间值关键代码 
int partition(SqList *L, int low, int high){
    int pivotkey = L->r[low];
    while(low < high){
        while(low<high&&L->r[high] >= pivotkey){
            high--;
        }
        swap(L, low, high);
        while(low<high&&L->r[low] <= pivotkey){
            low++;
        }
        swap(L, low, high);
    }
    return low;
}

//对无序序列进行排序 
void qSort(SqList *L, int low, int high){
    int mid;
    if(low < high){
        mid = partition(L, low, high);//算出中间值 
        qSort(L, low, mid-1);//对左边的表递归排序 
        qSort(L, mid+1, high);//对右边的表递归排序 
    }
}

void quickSort(SqList *L){
    qSort(L, 1, L->length);
}

void searchSort(SqList *L){
    for(int i = 1; i < MAXSIZE; i++){
        printf("%d ", L->r[i]);
    }
}

int main(){
    SqList *L = new SqList;
    initSort(L);
    searchSort(L);
    printf("\n");
    quickSort(L);
    searchSort(L);
    return 0;
}

结果如下：

算法时间复杂度分析

在最好的情况下，第一次partition会扫描n个关键字，做n次比较，因此此时的时间复杂度为n，记为T（n）。然后，获得的中间值将数组一分为二，那么各自需要T(n/2)，此时的总时间为：2 T（n/2）+n
如下：
T(n) <= 2T(n / 2) + n
T(n) <= 2(2T(n / 4) + n/2) + n = 4T(n/4) + 2n
T(n) <= 4(2T(n / 8) + n/4) + 2n = 8T(n/8) + 3n
….
T(n) <= nT(1) + (logn) * n = O(nlogn)

所以，最优情况下，快速排序的算法时间复杂度为O（nlogn）

优化

1、 发现一个问题，partition函数中，中间值pivotkey的取值是一个很值得商榷的问题，我们一开始设它为L->r[low]，只是刚好L->r[low]为50，因此pivotkey的值是比较接近中间值的。但是假如在有这样一个序列，{9,1,4,8,6,5,2,3,7}，那么此时pivotkey的值为9，但是9是整个序列最大值，这样我们的无用比较会做多少次啊！
我们可以用三数取中法，取三个关键字排序，再将中间值作为序列的中间值，一般取左端，中间，右端三个数。

//算出中间值关键代码 
int partition(SqList *L, int low, int high){
    int pivotkey;

    //增加了优化代码 
    int m = low + (high - low) / 2;//中间元素的下标 
    if(L->r[low] > L->r[high]){
        swap(L, low, high);//保证左端较小 
    }
    if(L->r[m] > L->r[high]){
        swap(L, m, high);//保证中间值较小
    }
    if(L->r[m] > L->r[low]){
        swap(L, low, m);//保证low位置的值为low，mid，high中第二大的
    } 
    pivotkey = L->r[low];

    while(low < high){
        while(low<high&&L->r[high] >= pivotkey){
            high--;
        }
        swap(L, low, high);
        while(low<high&&L->r[low] <= pivotkey){
            low++;
        }
        swap(L, low, high);
    }
    return low;
}

2、pivotekey的交换次数不必要，因为他最终都会到达中间（low

    public static int partition(int low, int high){
        int privoteKey = array[low];
        int back = privoteKey;
        while(low < high){
            while(low<high && array[high] >= privoteKey){
                high--;
            }
            //直到发现了有半部分有小于privotekey的数
            //采用替换
            array[low] = array[high];
            while(low<high && array[low] <= privoteKey){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = back;
        return low;
    }

3、快排和插入排序结合使用
当数组非常小的时候，使用快速排序反而有些大材小用了，因此递归其实也会影响性能的，所以我们可以定义一个阀值，当数组长度低于这个阀值时，就选择插入排序
经验表明，最好的组合方式是当n（子数组的长度）小于等于16时就使用插入排序

//对无序序列进行排序 
void qSort(SqList *L, int low, int high){
    int mid;
    if(high - low > MAX_LENGTH_INSERT_SORT){
        mid = partition(L, low, high);//算出中间值 
        qSort(L, low, mid-1);//对左边的表递归排序 
        qSort(L, mid+1, high);//对右边的表递归排序 
    } else {
        insertSort(L);
    }
}