题目
1045 快速排序 （25 分）
著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的 N 个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？
例如给定, 排列是1、3、2、4、5。则：
1 的左边没有元素，右边的元素都比它大，所以它可能是主元；
尽管 3 的左边元素都比它小，但其右边的 2 比它小，所以它不能是主元；
尽管 2 的右边元素都比它大，但其左边的 3 比它大，所以它不能是主元；
类似原因，4 和 5 都可能是主元。
因此，有 3 个元素可能是主元。
输入格式：
输入在第 1 行中给出一个正整数 N（≤10的5次方）；
第 2 行是空格分隔的 N 个不同的正整数，每个数不超过 10的9次方
输出格式：
在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
5
1 3 2 4 5
输出样例：
3
1 4 5
分析
这条题，按照我做题原则，先好好思考，整理逻辑，实在不行再参考别人。
一开始感觉应该挺简单，首先排除暴力分析，用步进分析法+双指针应该可以一次循环搞掂。
可是做着做着，我用一些测试用例通不过，发现这个逻辑有漏洞，这一分析，发现更多种情况要填要弥补，my god
对于我来说，思考太久一直是我弱项，可能没有写草稿的习惯，后来我尝试通过用例来弥补各种情况的逻辑编写
（请大家不吝赐教一些快速思路。）
最后也发现这样写完后也顺利一次通过。
然后再去看看别人写的，除了我们最后输出的思路一样，但在处理上他们基本上用STL封装好的排序sort，或者结合reverse。我才知道我们思考的区别，因为根据快速排序的主元特性，我一开始觉得没必要去排序或者再增加空间再来筛选，它已经就是按照原样进来。
主题思路
辅助空间：nums保存主元的数组，pre指针保存前一个主元，cur指针当前接收的值，minValue遇过的历史最小值，maxValue遇过的历史最大值
过程：（就是逻辑的暴解）
1.循环每一个进来的值
1.1判断 pre是否小于cur
当前值是否大于上一个主元的值，是就进入与历史最大值或最小值比较的判断
1.2如果pre==cur
与历史最大值，历史最小值比较
这就是我写的其中一些用例分析思路
一种情况
1 3 5 1000 //pre=2 cur =3,min =1,max =1000，只需要变化pre = cur,cur++
1 3 5 1000 7 //pre =3,cur =4,min =1 ,max=1000,明显nums[cur]<nums[pre],这两个不能要，MULength-=2，最后pre要退却一位即pre--,cur=pre+1;
1 3 5 1000(作废) 7(作废) 9 //pre =2 ,cur = 3,虽然符合nums[cur]>nums[pre]，但历史中出现过最大值1000，你的cur的值还是不能要，继续cur = pre+1，pre不变
1 3 5 1000(作废) 7(作废) 9(作废) 2. //pre =2 ,cur = 3,明显nums[cur]>nums[pre],这两个不能要,MULength-=2,最后pre要退却一位即pre--,cur=pre+1;
最后结果是1 3 5(作废) 1000(作废) 7(作废) 9(作废) 2(作废)，但是这个1和3结果明显不能接受，明显3不能要，需要改写，尝试用局部循环判断nums[cur]<nums[pre],直到把pre退却到适合的位置
另一种情况
2 3 5 1000 //pre=2 cur =3,min =2,max =1000，只需要变化pre = cur,cur++
2 3 5 1000 1//pre =3,cur =4,min =2 ,max=1000，明显nums[cur]<nums[pre]，再发现nums[cur]比历史最小值还要小，前面所有作废，这里就要pre与cur重置了，cur =pre=0,nums[0]=nums[cur],更新一下MULength-cur
2(作废) 3(作废) 5(作废) 1000(作废) 1(作废)
另一种情况
2 1 //pre =0,cur =1,min=2,max=2;明显nums[cur]<nums[pre],这两个不能要，MULength-=2,最后pre要退却一位即pre--, 若是pre退无可退，也就是负值，设置pre=cur = 0,否则cur=pre+1;
代码
#include <stdio.h>
#define MAX_NUM 100000
#define MAX_INT 0x7fffffff
unsigned int GetInputToInt();
int main()
{
//nums用来放入数据，N是输入个数， MULength是主元个数长度
int nums[MAX_NUM]={0},i=0,N,MULength =0;
//处理输入
//例子：2 4 3 1 5 ，只有5才是主元
//例子：4 5 6 2 1 8 7 9 3 10 只有10才是主元 用于这个测试点，发现我第一个版本错了，漏了判决
MULength = N = GetInputToInt();
//处理与控制：采用双指针控制
int prePos=0,curPos=0,curMinValue=MAX_INT,curMaxValue=0;
for(;i<N;i++)
{
nums[curPos] = GetInputToInt();
//（尝试步进分析，一旦遇到前者大于后者，马上重置prePos，剔除该两个，因为都不可能是主元了，
//1还保留一直遇到过的最小值curMinValue，和遇到过的最大值curMaxValue）
if(prePos<curPos)
{
//1.1若当前值大不过上一个值
if(nums[prePos]>nums[curPos])
{
//（作废情况）
//1.3看看是否遇上了比当前最小值还要小的当前值
if(curMinValue>nums[curPos])
{
//1.3.1 要是发现历史最小值都比不过当前值小，OK，前面全部作废
curMinValue = nums[curPos];
//更新MULength，这里分开写，让可读性好点
MULength = MULength - curPos;//前面作废，有多少个，curPos个(curPos是下标，curPos-1就是个数)
MULength--; //再减去当前第curPos那一个
prePos = curPos = 0;
}
else
{
MULength-=2;//当前这两个肯定不要了(pre与cur）
--prePos;
//1.3.2 要是发现前面最小值依然坚挺能接受考验。 需要把prePos退却到刚好nums[curPos]>nums[pre]的位置上
while(prePos>=0&&nums[curPos]<nums[prePos])
{
prePos--;
MULength--;
}
if(prePos<0)
//什么情况下会来到这里,应该没有，因为有1.3.1过滤了，最小值是来不了 例如，6(作废) 1(作废) 5(作废) 3 ，但pre=0.cur=0,明显，这个例子来不了 ，希望能找到例外
prePos = curPos = 0;
else
//来到这里，就是已经找到刚好 nums[curPos]>nums[pre]的位置上，重置curPos
curPos = prePos+1;
}
}
//1.2要是比得过，接下来看情况看下是否更新一下最大值
else
{
//（正常情况） 看看是否遇上了比历史最大值还要大的当前值
if(curMaxValue<nums[curPos])
{
curMaxValue = nums[curPos];//保留
prePos = curPos;
curPos++;
}
//若然当前值比不上历史最大值
else
{//（作废情况）
//这种情况就好像1，1000，2，3，4，此时cur=4,pre=3,虽然符合pre<pos,但是前面出现过巨无霸1000，在巨无霸后面到当前值都得作废，除非出现过比巨无霸还要猛的。
MULength = MULength -1;//减一就是当前cur的值不要了
curPos = prePos+1; //更新下一次应该要填的位置
//prePos = curPos = 0;
}
}
}
//2. 一般进入这里的情况都是，初始化，或者是前面都失效的情况下。
else if(prePos==curPos)//
{
//看情况更新最大值与最小值
//2.1
if(curMaxValue<nums[curPos])
curMaxValue = nums[curPos];
else
{//若是连历史最大值都大不上，也就是当前值作废 如 20(作废) 10(作废) 15 ，历史最小值是10
MULength--;
prePos = curPos = 0;
continue;
}
//2.2
if(curMinValue>nums[curPos])
//遇上了比历史最小值还小的值，更新 。如 2(作废) 3(作废) 1 ，历史最小值是2
curMinValue = nums[curPos];
else
{//若是连历史最小值都小不过. 如 20(作废) 10(作废) 21 ，历史最小值是10；如果是 20(作废) 10(作废) 15 ，这个有2.1过滤，不会来到这里
//不用操作 ，
}
prePos = curPos++;
}
}
//2. 输出
printf("%d\n",MULength);
for(i=0;i<MULength-1;i++)
printf("%d ",nums[i]);
if(i==MULength-1)
printf("%d",nums[i]);
putchar('\n');
return 0;
}
unsigned int GetInputToInt()
{
char c;
unsigned int sum =0;
while((c=getchar())!=EOF&&c!=' '&&c!='\n')
sum = sum*10+c-'0';
return sum;
}
