【ACM】算法题-数列排序 (C++)（快速排序基本思想）


<>数列排序

<>题目

<>数列排序

<>
快速排序排序的划分模拟：将一正整数序列{K1,K2,…,K9}重新排列成一个新的序列。新序列中，比K1小的数都在K1的前面(左面)，比K1大的数都在K1的后面(右面)。

<>输入

<>输入有多行,第一行为N表示行数,每行9个整数.

<>输出

<>输出N行(不超过100行),按要求进行排序的结果.

<>样例输入
2 6 8 9 1 2 5 4 7 3 3 5 8 9 1 2 6 4 7
<>样例输出
3 4 5 2 1 6 8 9 7 2 1 3 5 8 9 6 4 7
<>解析

<>
这是一道难度为二级的普通排序算法题，本题中的要求不高，但背后体现出了快速排序这种高级排序算法的基本思想，那就是分治的思想，通过一趟排序将待排序列分割成两部分,其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

<>进行解题时，我们知道快排首先要找出基准，本题给出是K1，再进行分割操作，很快达到题目要求，则如下：

<>代码流程
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n;
while (n--) {//n行整数序列 int a[9]; for (int i = 0; i < 9; i++)cin >> a[i]; int piv
= a[0];//K1 for (int i = 8; i >= 0; i--) { if (a[i] < piv)cout << a[i] << " ";
}//依次把比K1小的数都在K1的前面 cout << a[0] << " "; for (int i = 0; i <= 8; i++) { if
(a[i] > piv)cout << a[i] << " "; }//依次把比K1大的数都在K1的后面 cout << endl; } return 0; }
<>总结

<>1.快速排序的基本思想

<>2.排序算法的基础

技术
下载桌面版
GitHub
Microsoft Store
SourceForge
Gitee
百度网盘（提取码：draw）
云服务器优惠
华为云优惠券
京东云优惠券
腾讯云优惠券
阿里云优惠券
Vultr优惠券
站点信息
问题反馈
邮箱：[email protected]
吐槽一下
QQ群：766591547
关注微信
©2020-2025 ioDraw All rights reserved, Privacy Policy