[PAT练级笔记] 45 Basic Level 1045 快速排序

乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

PAT乙级BasicLevelPractice 1045

问题分析

题设要求所有给定数列中的满足主元条件的元素。
主元条件: 这个元素大于等于其左边所有元素 且 小于等于其右边所有元素;
所以题目可以描述为:
找出所有「大于等于其左边所有元素且小于等于其右边所有元素」的元素。

如何找?

最符合直觉的方法就是:
既然确定一个元素是不是主元, 只需要遍历其左边元素检查是否小于这个元素，
同时遍历其右边元素检查是否大于这个元素，那么对所有元素做这个操作就可以找出所有主元。
于是会写成两重循环的结构:

for 元素 in 所有元素:
    for 元素 in 左边元素:
        比较大小
    for 元素 in 右边元素:
        比较大小

先不考虑是否会被OJ系统判为超时的问题(事实确实会被判为超时), 我们考虑优化性能上的优化, 看看是不是存在不必要的操作
首先我们遍历左边是为了