[数据结构与算法]P1177快速排序

题目描述

利用快速排序算法将读入的 $N$ 个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++ 选手请不要试图使用 STL，虽然你可以使用 sort 一遍过，但是你并没有掌握快速排序算法的精髓。）

输入输出格式

输入格式

第 $1$ 行为一个正整数 $N$，第 $2$ 行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数，数据保证了 $A_i$ 不超过 $10^9$。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例

输入样例

5 4 2 4 5 1

输出样例 #1

1 2 4 4 5

说明

对于 $100\%$ 的数据，有 $N\le 10^5$。
提交的时候要开输入输出优化，不然后三个点超时。快排要用到递归，就是把大问题转成小问题。每趟排序要解决的是，找到一个中枢元素（这默认是序列第一个元素），一趟过后把大于中枢的元素放到中枢右边，小于的放左边（升序）。然后以中枢位置为分界，递归处理左右序列。
快排在序列越乱时效率越高$O(nlogn)$，而序列趋近于有序，效率会变差，趋近于$O(n^2)$

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100010;
int num[maxn];
int n;
// 一趟排序下了，返回中枢位置，升序
int Partition(int num[],int low,int heigh)
{
    // 第一个数当中枢
    int pivotkey=num[low];
    while (low<heigh)
    {
        // 从右向左找到第一个不大于等于中枢的数
        while (low<heigh&&num[heigh]>=pivotkey)
        {
            heigh--;
        }
        // 把这个数换到中枢左边
        num[low]=num[heigh];
        // 同理，处理完左边一个数，再处理右边
        // 找到第一个不小于等于中枢的数，换到中枢右边
        while (low<heigh&&num[low]<=pivotkey)
        {
            low++;
        }
        // 把这个数换到中枢右边
        num[heigh]=num[low];
    }
    // 中枢赋值到中间
    num[low]=pivotkey;
    // 返回中枢位置
    return low;
}
// 递归一趟趟排下去
void qsort(int num[],int low,int heigh)
{
    int pivotloc;
    if(low<heigh)
    {
        pivotloc=Partition(num,low,heigh);
        qsort(num,low,pivotloc-1);
        qsort(num,pivotloc+1,heigh);
    }
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&num[i]);
    qsort(num,0,n-1);
    printf("%d",num[0]);
    for(int i=1;i<n;i++)
        printf(" %d",num[i]);
    return 0;
}