1045 快速排序 (25 分)
著名的快速排序算法有一个经典的分割过程。 我们通常用某种方法取要素作为主元，通过交换，将小于主元的要素配置在其左侧，将大于主元的要素配置在其右侧。 给定分割后的n个互不相同的正整数数组，有多少因素可能是分割前选择的主元？
例如，给定N=5 N=5 N=5，则排列为1、3、2、4、5。 如果是：
1的左侧没有元素，右侧的元素都比它大，所以它可能是主元；
3左边的元素都比它小，但右边的2比它小，所以它不是主元；
2右边的元素都比它大，但是左边的3比它大，所以它不是主元；
出于同样的理由，4和5也可能是主元。
因此，三种元素可能是主元。
输入格式：
在第一行中输入正整数N(10 5)。 第二行是由空格分隔的n个不同的正整数，每个整数的数量小于或等于109。
输出格式：
在第1行输出可能是主元的要素的个数； 第二行按升序输出这些元素。 其间用一个空格隔开，在行前后不要加入多余的空格。
输入示例：
51 3 2 4 5输出样本：
31 4 5
这个问题总的来说应该有两种想法((根据快速排序的原理) ) ) ) ) ) )。
1 .只要主元数大于左边的所有数且小于右边的所有数(考虑非主元不移动的情况) )。
2 .除非主元在快速队列中不动，且右边有比它大的(考虑了非主元移动的情况) ) )。
开始了构想的话题。 最初的构想是我首先想到的，只是在一次循环对中实现了大于左的情况，没有想到右的情况。 这也是大气烟草和旭神的想法。
左边的最大值小于当前主元，且与此主元的位置满足排序后的同一条件，或者右边的最小值大于此主元即可。
第二种想法，我真正实现的想法，
在数组内移动的数据的位置和排序后的位置之间都不是主元。 由于不满足条件，所以可以将开始移动的次数规定为移动到最大次数的位置。
我使用的第二种想法
请先快点排列排列(请参阅我的博客)。 数组内移动的数据位置和排序后的位置之间都不是主元。 因为不满足条件，所以只要规定开始移动的数量在最大移动的数量的位置上不是主元即可。 [快速排序的c语言] 653359 blog.csdn.net/QQ _ 53269459/article/details/113856208 ]
【测试点3、5】(可以在以下测试点检测到) )。
1 11 3 4 10 14 5 8 6 101 3 4 5 6 8 10 11 14 100
输出21 100
11的位置从第2个到第8个，2 - 8之间的数据都表示不是主元。 另外，2 - 8有大于11的公式14，表示从原始数组的14个位置到排序后14个位置之间的元素都不是主元。 因此，右边只剩下100，左边只剩下1
# include stdio.h # include stdlib.hint CMP (const void * a，const void *b ) /快速通道(return*(int* ) a-* ) int* ) (}int main ) ) {int n，a[100001]，b[100001]，c[100001]； scanf('%d '，n )； for(intI=0； i n； I ) Scanf('%d '，a[i]； b[i]=a[i]； }qsort(b，n，sizeof ) b[0]，cmp )； //快速排序int sign=0，s=0，flag=0； for(intI=0； i n； I () if ) a[I]b[I]a[I]a[sign] ) {sign=i； flag=0； }if(a(sign )==b (I ) ) flag=1； if(a(I )==b ) I ) flag ) c ) s )=a(I )； }printf('%d(n )，s )； for(intI=0； i s； I () if ) I！=0) printf (' )； printf('%d '，c[i] )； //if(I！=s-1 ) printf (' )； }printf((n )； 返回0； }
c以下代码# include iostream # includealgorithmusingnamespacestd； int main () {int n，I，flag1=0，flag2=0，cnt=0，j； cinn； int a[n]、b[n]、c[n]； for(I=0； in； I({c} )
in>>a[i];b[i]=a[i];}sort(b,b+n);int max=0;for(i=0;i<n;i++){if(max<a[i])max=a[i];if(max==a[i]&&a[i]==b[i])c[cnt++]=b[i];}cout<<cnt<<endl;for(i=0;i<cnt;i++){cout<<c[i];if(i<cnt-1)cout<<" ";}cout<<endl;return 0;}大气的香烟的分析
分析：对原序列sort排序，逐个比较，当当前元素没有变化并且它左边的所有值的最大值都比它小的时候就可以认为它一定是主元（很容易证明正确性）～
如果硬编码就直接运行超时了…后来才想到这种方法～ 一开始有一个测试点段错误，后来才想到因为输出时候v[0]是非法内存，改正后发现格式错误（好像可以说明那个第2个测试点是0个主元？…）然后加了最后一句printf("n");才正确（难道是当没有主元的时候必须要输出空行吗…）
#include <iostream>#include <algorithm>#include <vector>int a[100000], b[100000], v[100000];using namespace std;int main() { int n, max = 0, cnt = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); b[i] = a[i]; } sort(a, a + n); for (int i = 0; i < n; i++) { if(a[i] == b[i] && b[i] > max) v[cnt++] = b[i]; if (b[i] > max) max = b[i]; } printf("%dn", cnt); for(int i = 0; i < cnt; i++) { if (i != 0) printf(" "); printf("%d", v[i]); } printf("n");//不加这句会有一个测试点没法通过。. return 0;
意思就是主元位置和排序后的位置相同，并且大于前面最大的元素，别忘记加 printf(" ");
旭神的分析
第一次写的原生代码，活生生写了三次for循环，可以简化掉,输入进来，正反各循环一次，记录i个数据左边最大值，和i右边最小值，只要 第i个数据比最大值大，最小值小就是关键元素
#include<iostream>#include<vector>#include<algorithm>using namespace std;int main(){int n;cin>>n;vector<int>num(n);vector<int>numax(n);vector<int>numin(n);int max=-1,min=1000000009;for(int i=0;i<n;i++){cin>>num[i];if(num[i]>max)max=num[i];numax[i]=max;}for(int i=n-1;i>=0;i--){if(num[i]<min)min=num[i];numin[i]=min;}int count=0;for(int i=0;i<n;i++){if(num[i]<=numin[i]&&num[i]>=numax[i]){count++;}}cout<<count<<endl;int flag=0;int cou=count;vector<int>num3(count);for(int i=0;i<n;i++){if(num[i]<=numin[i]&&num[i]>=numax[i]){num3[count-1]=num[i];count--;//cout<<num3[count];}}sort(num3.begin(),num3.end());for(int i=0;i<cou;i++){if(flag){cout<<" ";}flag=1;cout<<num3[i];} cout<<endl;return 0;}
就是利用多次 for 循环来记下主元左边的数和主元右边的数，然后用一层最大次数为 n 的 for 循环来实现大于左边最大值和小于右边最小值。
喜欢的小伙伴可以点赞哟！！！！