Title

Luogu. P1177
The N number that will be read will be followed by the output from small to large.

Input Format

The first act is a positive integer N.
The second line contains a positive integer of N-spaces separated a~i~.

Output Format

Splits the given number of N from small to large output, with spaces separated between numbers, lines unsigned and spaceless.

For 100% data, there is 1 ≤N ≤10⁵ One._I ≤ 10⁹。

Example:

输入
8
9 1 7 6 6 3 2 8

输出
1 2 3 6 6 7 8 9

Quick Sort Main UseThe idea of partition.Time complexityO(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);
}

Here's the idea.

1. Utilizationi (left pointer),j (right pointer) Point to the outside of the column, the median of the column is asx。
2. Counting X The number is left.X the number drops right.
3. For both the left and the left paragraphs, the two processes are re-introduced until only one number, i.e., all in order.
   

Process Simulation

Supplementary

That is, to the left of the median, to find a number greater than the median m₁, find a number smaller than the middle value on the right of the middle valuem₂, and when₁less than m₂It's the time.₁and m₂, after the exchange has been completed, divide and repeat the above-mentioned operation in the divided area.

STL Achieved

#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;
}

General

#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; 
}