©2020-2024 ioDraw All rights reserved,
Privacy Policy
<>数列排序
<>题目
<>数列排序
<>
快速排序排序的划分模拟：将一正整数序列{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.排序算法的基础