题目

Luogu P1177
将读入的 N 个数从小到大排序后输出。

输入格式

第一行为一个正整数 N。
第二行包含 N 个空格隔开的正整数a~i~ 。

输出格式

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

对于 100% 的数据，有 1 ≤ N ≤ 10⁵ ，1 ≤ a_i ≤ 10⁹。

样例：

输入
8
9 1 7 6 6 3 2 8

输出
1 2 3 6 6 7 8 9

快速排序主要利用分治思想，时间复杂度O(nlogn)。

int n, a[100005];

void quicksort(int l, int r){
    if(l == r) return;
    int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
    while(i < j){
        do i++; while(q[i] < x);    // 向右查找 ≥x 的数
        do j--; while(q[j] > x);    // 向左查找 ≤x 的数
        if(i < j) swap(q[i], q[j]);
    }
    quicksort(l, j), quicksort(j + 1, r);
}

思路如下

1. 利用i（左指针）,j（右指针） 指向数列的区间外侧，数列的中值记为x。
2. 将数列中 ≤x 的数放左段，≥x 的数放右段。
3. 对于左右两段，再递归以上两个过程，直到每段只有一个数，即全部有序。
   

过程模拟

补充

即在中间值的左边找一个大于中间值的数m₁, 在中间值的右边找一个小于中间值的数m₂, 并且当m₁小于m₂时，才交换m₁和m₂，交换完成后再进行分割，再对分割的区域重复上述的操作。

STL实现

#include <iostream>
#include <algorithm>
using namespace std;

int n, a[100005];

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a + n);
    for(int i = 0; i < n; i++) printf("%d", &a[i]);
    return 0;
}

一般实现

#include <iostream>
using namespace std;

int n, a[100005];

void quicksort(int l, int r){
    if(l == r) return;
    int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
    while(i < j){
        do i++; while(q[i] < x);    // 向右查找 ≥x 的数
        do j--; while(q[j] > x);    // 向左查找 ≤x 的数
        if(i < j) swap(q[i], q[j]);
    }
    quicksort(l, j), quicksort(j + 1, r);
}

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