1069: 顺序表的划分

将顺序表（a1，a2，…，an）重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值均比a1大（假设数据元素的类型具有可比性，不失一般性，设为整型）。

解题思路分析：重新排列的方法很多，在尽可能少的占用辅助空间的情况，有一种称为划分的算法，它的思路是：

（1）先从最后一个元素开始，从后向前扫描，让a1与之比较，如果当前元素比a1大，表明他在a1后面；如果当前元素比a1小，表明它应在前面，则相互交换位置。

（2）从第二元素开始，从前向后扫描，让当前元素与a1比较，如果当前元素比a1小，则表明他在a1的前面，不必改变元素的位置，继续向后比较，直到当前元素比a1大为止；如果当前元素比a1大，表明它应在a1后面，则相互交换位置。

记录下两端每次交换的位置，重复（1）（2）,从表两端继续交替比较，交换，直到所有元素比较结束。

初始的线性表如 15,20,5,9,30,17,11,18

划分之后的线性表如 11,9,5,15,30,17,20,18

15 20 5 9 30 17 11 18

11 9 5 15 20 30 17 18