【题目来源】
洛谷：P1177 【模板】排序 - 洛谷 (luogu.com.cn)
【题目描述】
将读入的 \(N\) 个数从小到大排序后输出。
【输入】
第一行为一个正整数 \(N\)。
第二行包含 \(N\) 个空格隔开的正整数 \(a_i\)，为你需要进行排序的数。
【输出】
将给定的 \(N\) 个数从小到大输出，数之间空格隔开，行末换行且无空格。
【输入样例】
5
4 2 4 5 1
【输出样例】
1 2 4 4 5
【算法标签】
《洛谷 P1177 排序》 #排序#
【代码详解】
#include <bits/stdc++.h> // 包含标准库中的所有头文件
using namespace std; // 使用标准命名空间const int N = 100020; // 定义常量N，表示数组的最大长度
int a[N]; // 定义一个全局数组a，用于存储待排序的数据// 快速排序函数
void quick_sort(int a[], int l, int r) {if (l >= r) return; // 如果左边界大于等于右边界，说明区间已经有序，直接返回int i = l - 1, j = r + 1; // 初始化两个指针i和j，分别指向区间外的位置int x = a[l + (r - l) / 2]; // 选取区间中间位置的元素作为基准值（pivot）// 分区操作while (i < j) {do i++; while (a[i] < x); // 从左向右找到第一个大于等于基准值的元素do j--; while (a[j] > x); // 从右向左找到第一个小于等于基准值的元素if (i < j) swap(a[i], a[j]); // 如果i<j，交换这两个元素}// 递归排序左半部分和右半部分quick_sort(a, l, j); // 排序左半部分 [l, j]quick_sort(a, j + 1, r); // 排序右半部分 [j+1, r]
}int main() {int n;cin >> n; // 输入数组的长度nfor (int i = 0; i < n; i++) cin >> a[i]; // 输入数组的n个元素quick_sort(a, 0, n - 1); // 调用快速排序函数对数组进行排序for (int i = 0; i < n; i++) cout << a[i] << " "; // 输出排序后的数组return 0; // 程序正常结束
}
【运行结果】
5
4 2 4 5 1
1 2 4 4 5