【计算机考研408】快速排序的趟数问题 + PAT 甲级 7-2 The Second Run of Quicksort
前言
该题还未加入PAT甲级题库中,可以通过购买2022年秋季甲级考试进行答题,纯考研题改编
快速排序
常考的知识点
- 快速排序是基于分治法
- 快速排序是所有内部排序算法中平均性能最优的排序算法
- 快速排序是一种不稳定的排序算法
- 快速排序算法中,不产生有序子序列,但每趟排序后会将枢轴元素放到其最终位置上
基于分治的思想,主要由两个步
1)划分
2)排序
代码
void QSort(int A[], int L, int R){
if(L >= R) return;
int key = A[L + R >> 1]; //选取L,R中间的元素作为基准
int i = L - 1, j = R + 1;
whiLe(i < j){
do i ++; whiLe(A[i] < key); //左指针右移,找到比基准大的数
do j --; whiLe(A[j] > key); //右指针左移,找到比基准小的数
if(i < j) swap(A,i,j); //交换A[i]和A[j]
}
QSort(A, L ,j);
QSort(A, j + 1, R);
}
void quicksort(int a[], int low, int high){
if (low < high){
int pos = partition(a, low, high);
quicksort(a, low, pos-1);
quicksort(a, pos+1, high);
}
}
//partition是一趟排序
int partition(int a[], int low, int high){
int pos = a[low];//将表中第一个元素设置位枢轴
while(low < high){
//从右边找到第一个比枢轴值小的
while(low < high && a[high] >= pos) --high;
a[low] = a[high];
while(low < high && a[low] >= pos) ++low;
a[high] = a[low];
}
a[low] = pos;
return low;
}
题源-2019年考研选择题
分析
- 两次排序,说明起码有两个中枢元素在最终的位置上,若小于两个元素在最终位置上,那么一定不是两趟快速排序
- 若出现两个或者两个以上的元素位于最终位置上,那么起码有一个元素要位于序列的第一个位置或者是最后一个位置
注意题目中的提示,两种类型的题目,(1)分类讨论直接有结果的(2)模拟流程进行解答
测试数据
输入
4
8
5 2 16 12 28 60 32 72
8
2 16 5 28 12 60 32 72
8
2 12 16 5 28 32 72 60
8
5 2 12 28 16 32 72 60
输出
Yes
Yes
Yes
No
- 错误代码,错误在于判读快速排序主元pivot的错误,并不能直接因为他与最后所在元素位置一致则判断其是pivot,应该根据左边最大的比他小右边最小的比他大进行判断
//判断是不是快速排序的第二轮
#include <bits/stdc++.h>
using namespace std;
int main(){
int T; cin >> T;
for(int t = 1; t <= T; t++){
int n; cin >> n;
vector<int> arr(n), tmp(n);
for(int i = 0; i < n; i++){
cin >> arr[i];
tmp[i] = arr[i];
}
sort(tmp.begin(), tmp.end());
vector<int> p;
for(int i = 0; i < n; i++){
if (arr[i] == tmp[i]) {
p.push_back(i);
}
}
if (p.size() < 2){
cout << "No" << '\n'; //continue;
}
else {
if (p[0] == 0 || p[p.size() - 1] == n - 1) {
cout << "Yes" << '\n';
}
else {
cout << "No" << '\n';
}
}
}
}
- 下列改代码书写正确,但会出现超时情况,在于寻找pivot的时间复杂度过高
//判断是不是快速排序的第二轮
//2 5 12 16 28 32 60 72
//5 2 12 28 16 32 72 60
#include <bits/stdc++.h>
using namespace std;
int main(){
int T; cin >> T;
for(int t = 1; t <= T; t++){
int n; cin >> n;
vector<int> arr(n);
for(int i = 0; i < n; i++){
cin >> arr[i];
}
vector<int> p; p.clear();
//左边最大的比其小,右边最小的比其大,则为一个privot,将其index压入p中
for(int i = 0; i < n; i++){
bool flag = true;
for(int j = 0; j < i; j++){
if (arr[j] > arr[i]){
flag = false;
break;
}
}
if (flag == false){
continue;
}
for(int j = i+1; j < n; j++){
if (arr[j] < arr[i]){
flag = false;
break;
}
}
if (flag == false){
continue;
}
else {
p.push_back(i);
}
}
if (p.size() < 2){
cout << "No" << '\n'; //continue;
}
else if(p.size() == 2){
if (p[0] == 0 || p[1] == n - 1) {
cout << "Yes" << '\n';
}
else {
cout << "No" << '\n';
}
}
else {
cout << "Yes" << '\n';
}
}
}
- 超时问题出现在输入上,可以关闭输入流,也可以更改为scanf
//判断是不是快速排序的第二轮
//2 5 12 16 28 32 60 72
//5 2 12 28 16 32 72 60
#include <bits/stdc++.h>
using namespace std;
int main(){
int T; scanf("%d",&T);
for(int t = 1; t <= T; t++){
int n; scanf("%d",&n);
vector<int> arr(n), tmp(n);
//左边最大的比其小,右边最小的比其大,则为一个privot
vector<int> lmax(n), rmin(n);
for(int i = 0; i < n; i++){
scanf("%d",&arr[i]);
tmp[i] = arr[i];
if (i == 0){lmax[0] = arr[0];}
else { lmax[i] = max(lmax[i - 1], arr[i]);}
}
for(int i = n - 1; i >= 0; i--){
if (i == n - 1) rmin[n - 1] = arr[n - 1];
else {
rmin[i] = min(rmin[i + 1], arr[i]);
}
}
vector<int> p;
sort(tmp.begin(), tmp.end());
//找出所有的pivot
for(int i = 0; i < n; i++){
if (tmp[i] == arr[i] && arr[i] == lmax[i] && arr[i] == rmin[i]){
p.push_back(i);
}
}
if (p.size() < 2){
cout << "No" << '\n'; //continue;
}
else if(p.size() == 2){
if (p[0] == 0 || p[1] == n - 1) {
cout << "Yes" << '\n';
}
else {
cout << "No" << '\n';
}
}
else {
cout << "Yes" << '\n';
}
}
}