洛谷 P1177 【模板】快速排序

题目所在网址：https://www.luogu.com.cn/problem/P1177

题面说是快排的板子题，可将纯纯快排的板子扔上去之后 T 的一塌糊涂...看来没这么简单。

对于快排，我的理解，一趟快排所做的事（从结果上来看）就是：把标准值扔到它最终该待的地方并且使它左边的值都小于它，右边的值都大于它。把这个过程扔到递归中去做足够多的的次数，就能够使一串数字排好顺序。

我们知道，快排的时间效率会随给定的数列特征不同而变化：

• 假如，我们每次选定的标准值，它最终待的地方都是中间位置，这样我们的快排每次都能从中间位置分割进而递归，第一趟确定一个数的位置，第二趟确定两个数的位置，第三趟确定四个数的位置......这样的话，一共排序的趟数是 logn，每趟的时间是 O(n) ，就达到了快排的最好时间复杂度：O(nlogn)
• 假如，这串数字本来就是有序的，我们每次选定的标准值，它最终待的地方都是最边上的位置，这就意味着我们做完一趟快排，把标准值放在该放的位置之后，第二趟快排要对剩下的 n - 1 个数做，第三趟快排要对剩下的 n - 2 个数做......这样的话，一共排序的趟数是 n ，它的时间复杂度是 n + n-1 + n-2 + ... + 2 + 1 = n(n + 1) / 2，显然，为 O(n²)，这便是快排最不拿手的情况。

如何让我们的快排小兄弟不再怕这种情况？有两种思路：

　　1、数据虽然很不友好，但我们设法在选取标准值的时候尽量随机。

参考如下代码：

int key = arr[(rand() % (high - low + 1)) + low];

对于本题，你甚至可以这么写：

int key = arr[(low + high) / 2];

　　2，让数据变得友好

拿到数据之后，我们可以人为的将其打乱，这个过程花费 O(n)，但由于 打乱数据 和 快排 是顺序的关系，不会影响到整体的时间效率。

参考如下代码：

void disrupt(int arr[], int n){//O(n)打乱数组，提升快排效率
    int temp, t_rand;
    for(int i = 0; i < n; i++){
        temp = arr[i];
        t_rand = rand() % n;
        arr[i] = arr[t_rand];
        arr[t_rand] = temp;
    }
}

这样的快排板子，便能够顺利的通过本题。

附上完整AC代码：

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;

void disrupt(int arr[], int n){//O(n)打乱数组，提升快排效率
    int temp, t_rand;
    for(int i = 0; i < n; i++){
        temp = arr[i];
        t_rand = rand() % n;
        arr[i] = arr[t_rand];
        arr[t_rand] = temp;
    }
}

void Quick_sort(int arr[], int low, int high){
    if(high <= low)return;
    int i = low - 1, j = high + 1;
    int key = arr[low];
    while(true){
        do{
            j--;
        }
        while(arr[j] > key);
        do{
            i++;
        }
        while(arr[i] < key);
        if(i < j)swap(arr[i], arr[j]);
        else break;
    }
    Quick_sort(arr, low, i - 1);
    Quick_sort(arr, j + 1, high);
}

int num[100000 + 5];

int main(){
//  ifstream cin("data.txt");
    srand((unsigned)time(NULL));
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> num[i];
    }
    disrupt(num, n);
    Quick_sort(num, 0, n - 1);
    for(int i = 0; i < n; i++){
        cout << num[i] << " ";
    }
    return 0;
}