给我们一个长度为n的数组，让我们输出排序后的数组

快速排序的应用

输入样例

5
3 1 2 4 5

输出结果

1 2 3 4 5

算法

(快速排序)

通过将数组分割成两部分，左边大于x，左边小于x，持续分割分类，最终得到结果

时间复杂度O(N)

C++ 代码

#include<iostream>

using namespace std;

const int N = 1e6+10;

int n;
int q[N];

void quick_sort(int q[] , int l ,int r){
    if(l >= r) return;
    int x  = q[(l+r)/2];
    int i = l-1,j = r+1;

    while(i < j){
        do i++;while(q[i] < x);
        do j--;while(q[j] > x);
        if(i < j) swap(q[i],q[j]);
    }

    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
}

int main(){
    scanf("%d",&n);
    for(int i = 0;i < n;i++)
        scanf("%d",&q[i]);

    quick_sort(q,0,n-1);

    for(int i = 0;i<n;i++)
        printf("%d ",q[i]);

    return 0;
} 

题目分析解决