1045 快速排序 (25 分)

左手的ㄟ右手 2023-06-04 15:57 28阅读 0赞

## 题目：[1045 快速排序 (25 分)][1045_25] ##

> 著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的 N 个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？
> 
> 例如给定 $N = 5$, 排列是1、3、2、4、5。则：
> 
>  *  1 的左边没有元素，右边的元素都比它大，所以它可能是主元；
>  *  尽管 3 的左边元素都比它小，但其右边的 2 比它小，所以它不能是主元；
>  *  尽管 2 的右边元素都比它大，但其左边的 3 比它大，所以它不能是主元；
>  *  类似原因，4 和 5 都可能是主元。
> 
> 因此，有 3 个元素可能是主元。
> 
> ### 输入格式： ###
> 
> 输入在第 1 行中给出一个正整数 N（≤）； 第 2 行是空格分隔的 N 个不同的正整数，每个数不超过 1。
> 
> ### 输出格式： ###
> 
> 在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。
> 
> ### 输入样例： ###
> 
>     5
>     1 3 2 4 5
> 
> ### 输出样例： ###
> 
>     3
>     1 4 5

--------------------

## 思路： ##

*  此题必须抓住快速排序的特点，硬算的话一定会超时，因为最坏情况都是105，硬算两个循环就1010了。上万的循环其实都很慢了。
 *  快速排序中选择的主元排序后位置是不变的， 但是满足这个条件不一定是主元。例如：3 2 1 4 5中的2在排序前后位置不变，但明显不是主元。  
    针对这种情况需要加以另外的判断：它还必须是当前序列此位置之前的序列的最大值。
 *  另外需要注意测试点二，在主元输出完成后，最后要来个换行\\n，不然会出现测试点2的格式错误，测试点二的数据就是最坏情况，递减排序5、4、3、2、1这样的。这时没有一个数符合主元的条件，即使这样也要有换行符，否则就会格式错误，测试点二就会过不了。
 *  一般程序全部输出完后来个换行都不影响，为了简便起见可以养成习惯。

## 代码： ##

1 #include <cstdio>
     2 #include <cstring>
     3 #include <cctype>
     4 #include <iostream>
     5 #include <sstream>
     6 #include <cmath>
     7 #include <algorithm>
     8 #include <string>
     9 #include <stack>
    10 #include <queue>
    11 #include <vector>
    12 #include <map>
    13 using namespace std;
    14 
    15 int main()
    16 {
    17     int n;
    18     int num[100005], nst[100005];
    19     scanf("%d", &n);
    20     for(int i = 0; i < n; i++)
    21     {
    22         scanf("%d", &num[i]);
    23         nst[i] = num[i];
    24     }
    25     sort(nst, nst + n);
    26     int cnt = 0, maxx = 0;
    27     int zy[100005];
    28     for(int i = 0; i < n; i++)
    29     {
    30         if(num[i] > maxx)
    31             maxx = num[i];
    32         if(num[i] == nst[i] && num[i] == maxx)    //如果排序后位置没变，而且是初位到当前位置的最大值，则确定是主元
    33             zy[cnt++] = num[i];        
    34     }
    35     printf("%d\n", cnt);
    36     for(int i = 0; i < cnt; i++)
    37     {
    38         printf("%d", zy[i]);
    39         if(i != cnt-1)
    40             printf(" ");
    41     }
    42     printf("\n");
    43     return 0;
    44 }

## 总结： ##

凡是碰到有关的概念，出现过的，要好好想想其定义和原理以及特点。比如1045的快排，和前面题目出现过的插入和归并排序。  
　　此类题型要抓住特点解题。  
　　养成输出完成后换行的习惯，避免不必要的麻烦。

转载于:https://www.cnblogs.com/Anber82/p/11353212.html

[1045_25]: https://pintia.cn/problem-sets/994805260223102976/problems/994805278589960192