快速排序分析

题目描述

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

样例

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n个整数（所有整数均在 1∼1e9范围内），表示整个数列。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

1 2	5 3 1 2 4 5

输出样例：

1 2 3 4 5

主要思想

快排属于分治算法，分治算法都有三步：

分成子问题
递归处理子问题
子问题合并

寻找一个哨兵，将小于这个哨兵的元素放于其左边，大于他的元素放于其右；递归的排序其左区间和右区间即可完成排序

think point

如何选取哨兵的位置？

哨兵的位置应该随机选取，或是取中间：若是取左边作为哨兵，若数组本身就是有序的，每次分划的时间为O(n)，之后的子问题规模即为0和n-1，总共的复杂度即为，而取中间作为哨兵可以保证每次可以把区间分为长度近似相等的两部分，因而复杂度为递归深度*O(n)即为
每次划分两部分后，最终哨兵的位置是否需要获知？

根据每次分划后是否需要知道哨兵的位置，可以有两种思路来进行快排：

哨兵最终位置未知

第一种思路是acwing的模板思路，缺点是有一些坑，不好理解(i,j位置不能互换，不然可能陷入死循环等)但是代码较为整洁，适合笔试用

void quicksort(int q[], int l, int r) {
    if (l>=r) return;
    // 使用区间中点作为哨兵
    int mid = l+r >>1;
//    swap(q[mid],q[l]);
    int x = q[mid], i = l-1, j= r+1;
    //忽略了哨兵的位置，我不在乎哨兵的位置具体在哪里
    //我只知道，j右边的数都大于等于哨兵，j左边的数都小于等于哨兵
    //之所以不取等于是防止数组越界，还有可以更好地划分子问题
    //缺点是可能会有很多次无效交换
    while(i<j) {
        do i++; while (q[i] < x);
        do j--; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quicksort(q,l,j);
    quicksort(q,j+1,r);
}

算法证明：

明显地，j右边的数大于等于x,i左边的数小于等于x。现需证明while结束时，q[l..j]均<=x，若成立，即可证明j这个端点可以划分整个区间。因为i>=j，所以q[1..j-1]均<=x。因为退出循环前的i<j判断为false，所以最后一次交换不执行，所以q[j]必然<=x。综上可以证明q[l..j]均<=x，所以j这个端点可以划分整个区间。

哨兵最终位置已知

第二种是数据结构教材的官方思路，优点是步骤明确，方便理解，较少坑，缺点是代码冗长

void quicksort2(int q[], int l, int r) {
    if (l>=r) return;
    // 首先保存哨兵的值
    int pio = q[l];
    int i = l;
    int j = r;
    while(i<j){
        // 之所以可以取=，是因为之前有判断，一定不会越界
        while(i<j && q[j]>=pio) j--;
        if(i<j) q[i] = q[j];
        else break;
        while(i<j && q[i]<=pio) i++;
        if(i<j) q[j] = q[i];
    }
    //哨兵的位置是确定的=i=j，所以只需要对其左边和右边分别进行排序即可
    q[i] = pio;
    quicksort2(q,l,i-1);
    quicksort2(q,i+1,r);
}

算法改进

实际上是对于某类特殊数据的算法增强

如果数组的每个数据都相同时，上面的第一种思路可以pass，但是第二种思路会超过时限，究其原因为：分化后的子问题规模即为0和n-1，总共的复杂度即为，所以对于这种情况需要特殊处理，而且不能简单地将中点与左端点交换（实际上没有改变算法流程），第二种思路地修改点如下：

while(i<j){
        // 之所以可以取=，是因为之前有判断，一定不会越界
        while(i<j && q[j]>pio) j--;
        if(i<j) q[i++] = q[j];
        else break;
        while(i<j && q[i]<pio) i++;
        if(i<j) q[j--] = q[i];
    }

经测试，第二种思路改进后速度较第一种思路能快上一点点