一道快速排序题的解析
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/article/details/53710179
关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照关键码值递增的次序进行排序，若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是 （）。
分析：
快速排序的分割策略之一就是，首先用一个临时变量对首元素（轴元素）进行备份，取两个指针left和right。他们的初始值分别是待排序列两端的下标，其中left指向序列最左边的下标，right指向序列最右边的下标。在整个排序过程中保证left不大于right，用下面的方法不断移动指针：
1、首先从right所指的位置向左搜索，找到第一个小于或者等于轴的元素，把这个元素移动到left的位置；
2、再从left所指的位置向右搜索，找到第一个大于轴的元素，把这个元素移动到right的位置；
3、重复上述过程，直到left=right；
4、最后把轴元素放在left所指的位置。
按照上面的方法，对应本题，解题过程如下： 1、初始时，left、right指针指向如下图所示：
2、right指针向左搜索，当遇到F时，由于F小于轴值Q，所以把F移动到left指针所指位置：
3、left指针向右搜索，当遇到Y时，由于Y大于轴值Q，所以把Y移动到right指针所指位置：
4、right指针向左搜索，当遇到D时，由于D小于轴值Q，所以把D移动到left指针所指位置：
5、left指针向右搜索，当遇到S时，由于S大于轴值Q，所以把S移动到right指针所指位置：
6、此时，left=right，于是把轴元素Q放到left指针此时所指位置上：
整个过程如下图所示：
