已知序列{503,87,512,61,908,170,897,275,653,462}，请给出采用快速排序法对该序列作升序排序的每一趟。

Question

请高手详细写明每一趟的排列结果。并将每一趟怎么排的解释一下。如何进行快速排序我一点也不明白，没有思路。马上考试了，希望高手详细解答一下。十分感谢。

Answer 1

快速排序过程即为如下三个步骤：
1. 选定序列中的一个元素，作为枢轴
2. 用该枢纽划分序列，依据指定的偏序规则使得位于枢轴左侧的序列都比枢纽小，位于枢轴右侧的数都比枢纽大
3. 对划分所得的序列重复1,2步，直到序列不可再分。
所以由上面的三个步骤可知：
1.快速排序每次都会将序列一分为二
2.划分完序列之后即确定了枢轴在最终有序序列所处的位置
快速排序划分的结果，受到枢轴选择的影响，假设算法选择序列的第一个元素作为枢轴。
则枢轴为数字503，小于503的数将位于其左边，大于503的数将位于其右边，所以序列为：
{462,87,275,61,170} , 503 , {897,908,653,512}
这个序列的由来按照严版数据结构中使用的移动元素算法，其经历了如下几个步骤：
1. 从右找到一个比枢轴小的数与其进行交换
2. 从左找到一个比枢轴大的数与其进行交换
3. 直到左右两个移动的查找指针已经相遇
1. 从右找到比503小的数462与503交换位置
{462,87,512,61,908,170,897,275,653,503}
2. 从左找到比503大的数512与503交换位置
{462,87,503,61,908,170,897,275,653,512}
3. 从右找到比503小的数275与503交换位置
{462,87,275,61,908,170,897,503,653,512}
4. 从左找到比503大的数908与503交换位置
{462,87,275,61,503,170,897,908,653,512}
5. 从右找到比503小的数170与503交换位置得到最终序列,此时503已经位于最终位置
{462,87,275,61,170, 503 ,897,908,653,512}
接下来重复的对划分后的序列{462,87,275,61,170}和 {897,908,653,512}重复上面的过
程则可以完成整个快速排序。追问

1. 从右找到比503小的数462与503交换位置
{462,87,512,61,908,170,897,275,653,503}
一直到最后这一部分还是没有理解。

这部分没明白。还有503 , {897,908,653,512}就是503右侧这些数据怎么排列。

追答

1. 起始序列为：{503,87,512,61,908,170,897,275,653,462}
从右找到的第一个比503小的数是462，所以用462与503进行交换得到
序列{462,87,512,61,908,170,897,275,653,503}，这个过程应该很好理解吧。
2. 我猜想你是不理解为什么采用如此左右轮流查找小和大数并进行交换的方式最终
可以达到划分序列的效果对吧
1. 起始503位于最左端，因为此时其为第一个元素
2. 从右开始查找比其小的数进行交换，使得每次其交换到右侧位置时，其右侧再没有比其小的数
3. 从左侧开始查找比其大的数进行交换，可以使得其左侧位置再没有比其大的数
4. 由于左右侧的查找是不断向中间汇聚的，所以最终两个指针会在中间汇聚在一起，从而无论
枢轴交换到了哪个位置，由于这种汇聚，会使得其左侧再没有比起大的数，其右侧再没有比起
小的数，达到划分序列的目的。
{897,908,653,512}右侧序列的排列与从左至右查找到的比503大的数据顺序有关，实际上等于将左侧较大的数交换到右侧较小的数的位置上，而右侧较小的数交换到左侧较大的数的位置上（位置包含503自身）因此右侧起始四个数{897,275,653,462}（为什么只取四个，因为整个序列比503大的数只有四个）中只有275与462比503小，将左侧依顺序比503大的数交换过来，512与462换，908与275换。右侧较小的数换到左侧需要包含503自身的位置，因此462放置在原来503的位置，275放置在原来512的位置，而170放置在908的位置上。从而得到序列：
{462,87,275,61,170, 503 ,897,908,653,512}