include
include
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
//从小到大
//插入排序
//第一个元素默认有序，然后从第二个元素开始与前面所有元素比较
//若第二个元素小，则将大于它的所有元素统一右移，将这个元素放在其左边空出的地方
//第3，4，···依次插入直至数组有序
//核心：保存当前元素→向前比较并后移→插入到正确位置
void insert_sort(){
for(int i = 2; i <= n; i++){
int key = a[i];//保存当前元素
int j = i - 1;
while(j > 0 && a[j] > key){
a[j+1] = a[j];//统一右移
j--;
}
a[j + 1] = key;//插入到正确位置
}
}
//选择排序
//数组分为已排序区和未排序区，每一轮在未排序区中找到最小的元素
//将其与未排序区中第一个元素交换位置，逐步扩大已排序区，直至数组有序
//核心：选最值+交换
void select_sort(){
for(int i = 1; i < n; i++){
int pos = i;// 初始化最小值下标为未排序区第一个元素下标
for(int j = i + 1; j <= n; j++){ //从下一个元素开始
if(a[j] < a[pos]){
pos = j; // 更新最小值下标
}
}
swap(a[i], a[pos]); // 将最小值交换到未排序区第一个位置
}
}
//冒泡排序
//从头到尾依次比较相邻的两个元素，如果顺序错误就交换
//每一轮会把未排序区的最大值“冒泡”到未排序区的末尾，逐步缩小未排序区，直至数组有序
//核心：相邻比较+交换
void bubble_sort(){
// 外层循环：控制未排序区的末尾（每轮把最大值冒泡到末尾）
for(int i = 1; i < n; i++){
// 标记本轮是否发生交换
bool flag = false;
// 内层循环：遍历未排序区，相邻比较交换
// 未排序区范围：[1, n-i]（因为后i个元素已排序）
for(int j = 1; j < n - i + 1; j++){
if(a[j] > a[j + 1]){
swap(a[j], a[j + 1]);
flag = true;
}
}
// 优化：如果本轮无交换，说明数组已有序，直接退出循环
if(flag == false) return;
}
}
//堆排序
//建堆 + 排序，向下调整算法
//先将数组整理成一个大顶堆，即第一个元素一定是最大的；
//接着将这个元素与末尾元素进行交换，除去末尾元素的剩下元素继续整理成大顶堆，即将堆顶元素向下调整
//反复进行，直到堆中剩余一个元素，即数组有序
//核心：堆排序的本质是利用大顶堆快速找最大值，通过 “建堆→取最大值→重调堆” 三步实现排序；
void down(int parent, int len){ //向下调整算法
int child = parent * 2;
while(child <= len){
if(child + 1 <= len && a[child] < a[child + 1]) child++; //比较左右孩子哪个权重大
if(a[parent] >= a[child]) return; //父节点比孩子节点的权重大，结束
swap(a[parent], a[child]); //否则交换节点权重
parent = child; //向下调整
child = parent * 2;
}
}
void heap_sort(){
//1.建堆
for(int i = n / 2; i >= 1; i--){ // 从最后一个非叶子节点向前遍历
down(i, n); // 将以i为根的子树调整为大顶堆（逐步构建全局大顶堆）
}
//2.排序
for(int i = n; i > 1; i--){
swap(a[1], a[i]); // 将堆顶最大值交换到未排序区最后一个位置
down(1, i - 1); // 对剩余未排序区（长度i-1）重新调整为大顶堆
}
}
//快速排序
//找一个基准值，然后将数组分成两个部分，一个部分所有元素大于基准值，另一个小于基准值；
//然后对左右部分重复操作，直至数组有序
//两个优化：1.三路划分，将所有元素分成三个区间，中间是相等元素，（解决过多元素相等问题）
//2.随机选择基准元素（解决原数组元素有序问题）
//核心：选基准，分三区，递归排
int get_random(int left, int right){ //随机数
return a[rand() % (right - left + 1) +left];
}
void quick_sort(int left, int right){
if(left >= right) return; //递归跳出条件
int p = get_random(left, right); //随机数
int l = left - 1, i = left, r = right + 1; //l = 左区间 的右边界， i = 遍历数组， r = 右区间的左边界
while(i < r){
if(a[i] < p) swap(a[++l], a[i++]); //左区间，l 和 i 均++
else if(a[i] == p) i++; //中区间，相等元素区间， i要++
else swap(a[--r], a[i]); //右区间， r 要--， i 不动（因为从右区间交换的数不清楚， 需要继续进行检验）
}
quick_sort(left, l); //递归处理<p的左区间（子数组长度≤1时终止）
quick_sort(r, right); //递归处理>p的右区间（同上）
}
int tmp[N];
//归并排序
//将数组拆分成一个个长度为1的“最小有序数组”，
//然后不断将两个有序数组合并成一个更大的有序数组，直至合并成整个有序数组
//核心：分而治之+合并有序数组；先拆分后合并，合并依赖临时数组
void merge_sort(int left, int right){
if(left >= right) return; //递归跳出条件
int mid = (left + right) / 2; //中间值
merge_sort(left, mid); // 递归拆分左区间，直到子数组长度为1（天然有序）
merge_sort(mid + 1, right); // 递归拆分右区间，直到子数组长度为1（天然有序）
int cur1 = left, cur2 = mid + 1, i = left; //cur1 = 左区间数组的遍历指针， cur2 = 右区间数组的遍历指针， i = 临时数组的遍历指针
while(cur1 <= mid && cur2 <= right){ //将两个有序数组合并成一个有序数组
if(a[cur1] <= a[cur2]) tmp[i++] = a[cur1++];
else tmp[i++] = a[cur2++];
}
while(cur1 <= mid) tmp[i++] = a[cur1++]; //处理左区间剩余元素
while(cur2 <= right) tmp[i++] = a[cur2++]; //处理右区间剩余元素
for(int j = left; j <= right; j++){
a[j] = tmp[j]; // 将临时数组中的有序元素复制回原数组
}
}
int main(){
srand(time(0));//种下时间种子
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
//insert_sort();
//select_sort();
//bubble_sort();
//heap_sort();
quick_sort(1, n);
for(int i = 1; i <= n; i++) cout << a[i] << " ";
return 0;
}