PAT 1045 快速排序

PAT1045
本题采用递推方式，使用 over 数组记录位置 i 与前面所有数据最大值的差值(本题中所有的差值均指当前元素减去其他值)；记录后，从后向前遍历，找出当前数据与后面最小值的差值；若当前数与最前面最大元素的差值为正表示当前元素的前面所有元素都小于当前元素，若当前元素与后面最小元素的差值为负，表示当前元素大于后面的所有元素；当两者同时满足时，该元素可以作为主元，记录当前元素位置； 本题的关键在于找到递推关系，可以通过分析得到当前元素与前面最大元素的差值为
当前元素 - 前一个元素 + 前一个元素与前面最大元素的差值 或 当前元素 - 前一个元素

第二种可能是当前一个元素为最大时(即 over[i - 1] > 0)
与后面最小元素的差值类似；
#include
const int maxn = 100010;
int over[maxn] = {0}; //当前位置与最大元素

PAT 1045 快速排序最先出现在Python成神之路。