下载掌阅APP，畅读海量书库
立即打开
快速排序采用分治的策略。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列的目的。
如图3-7所示，假设最开始的基准数据为数组第一个元素23，则首先用一个临时变量去存储基准数据，即tmp=23。然后分别从数组的两端扫描数组，设两个指示标志：low指向起始位置，high指向末尾。
（1）先从后半部分开始，如果扫描到的值大于基准数据就让high减1，如果发现有元素比该基准数据的值小（如图3-7中的18≤tmp），就将high位置的值赋值给low位置，结果如图3-8所示。
（2）开始从前往后扫描，如果扫描到的值小于基准数据就让low加1，如果发现有元素大于基准数据的值（如图3-8中的46≥tmp），就再将low位置的值赋值给high位置的值，指针移动并且数据交换后的结果如图3-9所示。
图3-7 最开始的基准数据
图3-8 值大于基准数据high减1
（3）然后再开始从后向前扫描，原理同上，发现图3-9的11≤tmp，则将high位置的值赋值给low位置的值，结果如图3-10所示。
图3-9 值小于基准数据low加1
图3-10 high位置的赋值给low位置的值
图3-11 从前往后遍历
（4）然后再开始从前往后遍历，直到low=high结束循环，此时low或high的下标就是基准数据23在该数组中的正确索引位置，如图3-11所示。
快速排序的本质就是把比基准数大的都放在基准数的右边，把比基准数小的放在基准数的左边，这样就找到了该数据在数组中的正确位置。
【例3-10】 利用快速排序对序列[50，36，61，95，73，13，27，50]进行排序。
运行程序，输出如下：
快速排序：
[13,27,36,50,50,61,73,95]