【计算机考研408】快速排序的趟数问题 + PAT 甲级 7-2 The Second Run of Quicksort

前言

该题还未加入PAT甲级题库中，可以通过购买2022年秋季甲级考试进行答题，纯考研题改编

快速排序

常考的知识点

1. 快速排序是基于分治法
2. 快速排序是所有内部排序算法中平均性能最优的排序算法
3. 快速排序是一种不稳定的排序算法
4. 快速排序算法中，不产生有序子序列，但每趟排序后会将枢轴元素放到其最终位置上

基于分治的思想，主要由两个步
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. 若出现两个或者两个以上的元素位于最终位置上，那么起码有一个元素要位于序列的第一个位置或者是最后一个位置

注意题目中的提示，两种类型的题目，（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

//判断是不是快速排序的第二轮
#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';}}}
}