4.6 快速排序算法
快速排序法又称为分割交换法，是对冒泡排序法的一种改进。其基本思想是：先在数据中找一个虚拟的中间值，并按此中间值将打算排序的数据分为两部分。其中，小于中间值的数据放在左边，大于中间值的数据放在右边；再用同样的方式处理左右两边的数据，直到排序完成为止。
例如，有n项数据，数据值用K1, K2, …, Kn来表示。其快速排序法操作步骤如下：
（1）先在数据中假设一个虚拟中间值K（为了方便，一般取第一个位置上的数）。
（2）从左向右查找数据Ki，使得Ki>K，Ki的位置数记为i。
（3）从右向左查找数据Kj，使得Kj<K，Kj的位置数记为j。
（4）若i<j，数据Ki与Kj交换，并回到步骤（2）。
（5）若i≥j，数据K与Kj交换，并以j为基准点分割成左右两部分，然后针对左右两部分再进行步骤（1）～步骤（5），直到左半边数据等于右半边数据为止。
例如，有这样一组数据：6, 1, 2, 7, 9, 3, 4, 5, 10, 8，如图4.41所示。采用快速排序法递增排序，步骤如下。
图4.41 原始数列
（1）取原始数列的第一个数6为虚拟中间值，即K=6；然后从左向右查找大于6的数，得到数字7，位置i=4；再从右向左查找小于6的数，得到数字5，位置j=8，如图4.42所示。
图4.42 步骤（1）排序过程
（2）i<j，因此交换Ki（数字7）和Kj（数字5）的位置，完成第一次排序。继续从左向右查找值大于6的数，即数字9，位置i=5；再从右向左查找值小于6的数，即数字4，位置j=7，如图4.43所示。
图4.43 步骤（2）排序过程
（3）i<j，因此交换Ki（数字9）和Kj（数字4）的位置，完成第二次排序。继续从左向右查找值大于6的数，即数字9，位置i=7；再从右向左查找值小于6的数，即数字3，位置j=6，如图4.44所示。
图4.44 步骤（3）排序过程
（4）i>j，因此交换虚拟中间值K（数字6）和Kj（数字3）的位置，完成第三次排序。此时，发现6的左半边都是小于6的数，右半边都是大于6的数，虚拟中间值6变成了真正的中间值，如图4.45所示。
图4.45 步骤（4）排序过程
（5）对中间值6左半边的数据排序，中间值和右半边数据暂时可以忽略。在左半边取第一个位置的数为虚拟中间值，即K=3，从左向右查找大于3的值，即数字5，位置i=4；再从右向左查找小于3的值，即数字2，位置j=3，如图4.46所示。
图4.46 步骤（5）排序过程
（6）i >j，因此需要交换虚拟中间值K（数字3）和Kj（数字2）的值，如图4.47所示。此时虚拟中间值变成了真正的中间值。小于3的都在中间值3的左半边，大于3的都在中间值3的右半边。
图4.47 步骤（6）排序过程
（7）接下来对中间值3的左、右两侧排序，排序后的结果如图4.48所示。
图4.48 步骤（7）排序过程
（8）此时，整组数据的左半边已经完成排序，接下来需要忽略已排序好的左半边和中间值6，对右半边进行排序。取右半边第一个位置的数为虚拟中间值，即K=9，然后从左向右找大于9的值，即数字10，位置i=9；再从右向左找小于9的值，即数字8，位置j=10，如图4.49所示。
图4.49 步骤（8）排序过程
（9）i<j，因此交换Ki（数字10）和Kj（数字8）。然后再从左向右查找大于9的值，即为数字10，位置i=10；再从右向左找小于9的值，即为数字8，位置j=9，如图4.50所示。
图4.50 步骤（9）排序过程
（10）i>j，因此交换虚拟中间值K（数字9）和Kj（数字8）的值，此时，虚拟中间值变成为真正的中间值，如图4.51所示。
图4.51 步骤（10）排序过程
（11）以中间值9为界，分为左右两侧，再进行排序，最后完成右半边排序，如图4.52所示。
图4.52 步骤（11）排序过程
（12）结合左半边排序和右半边排序，最终的排序结果如图4.53所示。
图4.53 最终排序结果
【实例4.11】 使用快速排序法将列表中的数字递增排序。（实例位置：资源包\Code\04\11）
用Python代码实现上方示例中的快速排序算法，具体代码如下：
运行结果如图4.54所示。
【实例4.12】 入职年限排名。（实例位置：资源包\Code\04\12）
例如，某公司的6名职员入职年限分别是1、3、15、20、5、4。利用快速排序法给这些职员入职年限从高到低顺序排序，用Python实现具体代码如下：
运行结果如图4.55所示。
图4.54 快速排序法
图4.55 运行结果