题目描述

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

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

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

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

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

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

数据范围
1≤n≤100000

样例

输入样例：
5
3 1 2 4 5
输出样例：
1 2 3 4 5

时间复杂度

nlogn

Java 代码

1、需要注意边界：（选择距离更远的）
分界点x取值l或(l+r)>>1时，递归的边界应使用j,j+1;
分界点x取值r或(l+r+1)>>1时，递归的边界应使用i-1,i;
2、需要注意分界点应使用x，不能使用q[mid]，因为q数组的值会因i,j的交换而产生变化，q[mid]也会产生变化。快排实际上是通过值来划分边界，该值可大可小，当每次取的值恰好是中值时，性能最高，nlogn，当每次取的值是边界值时，性能最差，n^2。而归并实际上是通过位置来划分边界的，每次都选择中间位置，因此位置固定，性能固定，nlogn。

void quick_sort(int q[], int l, int r){
    if(l>=r)return;
    int i=l-1,j=r+1,x=q[l];
    while(i<j){
        do i++;while(q[i]<x);
        do j--;while(q[j]>x);
        if(i<j){
            int tmp = q[i];
            q[i] = q[j];
            q[j] = tmp;
        }
    }
    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}