1#include<iostream>
2#include<algorithm>
3#include<vector>
4#include "stdio.h"
5#include "time.h"
6using namespace std;
7
8int a[10000005] = {0};
9
10// 该函数用于将数组a的一个段[a[left], a[right]]按照基准值base进行划分
11int partition(int a[], int left, int right) {
12    int base = a[left]; // 选择基准值为当前段的第一个元素
13    while (left < right) {
14        // 从右向左扫描，找到第一个小于基准值的元素
15        while (left < right && a[right] >= base) {
16            right--;
17        }
18        a[left] = a[right]; // 将找到的小于基准值的元素移动到左边
19        
20        // 从左向右扫描，找到第一个大于等于基准值的元素
21        while (left < right && a[left] < base) {
22            left++;
23        }
24        a[right] = a[left]; // 将找到的大于等于基准值的元素移动到右边
25    }
26    a[left] = base; // 将基准值放到最终的位置
27    return left; // 返回基准值最终的索引
28}
29
30// 快速排序函数，递归地对数组的一段进行排序
31void quick_sort(int a[], int left, int right) {
32    if (left >= right) {
33        return; // 如果当前段的长度为1或为空，则不需要排序
34    }
35    int mid = partition(a, left, right); // 对当前段进行划分，获得基准值的索引
36
37    quick_sort(a, left, mid - 1); // 递归地对基准值左边的子段进行快速排序
38    quick_sort(a, mid + 1, right); // 递归地对基准值右边的子段进行快速排序
39}
40
41int main() {
42        int n = 0;
43        cin >> n;
44        for (int i = 0; i < n; i++) {
45                cin >> a[i];
46        }
47        quick_sort(a, 0, n - 1);  
48        for (int i = 0; i < n; i++) {
49                cout << a[i] << ' ';
50        }
51        cout << endl;
52        return 0;
53}