45,80,55,40,42,85快速排序第一次划分的结果

Question

45,80,55,40,42,85快速排序第一次划分的结果

Answer 1

快速排序过程即为如下三个步骤：
1. 选定序列中的一个元素,作为枢轴
2. 用该枢纽划分序列,使得位于枢轴左侧的序列都比枢纽小,位于枢轴右侧的数都比枢纽大
3. 对划分所得的序列重复1,2步,直到序列不可再分.
所以由上面的三个步骤可知：
1.快速排序每次都会将序列一分为二
2.划分完序列之后即确定了枢轴在最终有序序列所处的位置
快速排序第一次划分的结果,受到枢轴选择的影响,假设选择序列的第一个元素作为枢轴.
则枢轴为数字45,小于45的数将位于其左边,大于45的数将位于其右边,所以序列为：
（42,40）45（55,80,85）
1. 左右集合的内容在枢轴选定是即被确定
2. 左右集合中元素的次序收到具体的元素移动算法的影响,按照严版数据结构书中的移动方式其序列如上面所示.其步骤如下：
首先从右找到第一个比45小的元素42与45交换得到序列(42,80,55,40,45,85)
接着从左往右找到第一个比45大的元素80与45交换得到序列(42,45,55,40,80,85)
重复这个过程依次得到序列(42,40,55,45,80,85)、(42,40,45,55,80,85)即最终序列

注：这个过程移动过程并非是一定的,采用不同的元素移动算法可以得到不同的左右顺序序列.