4.6　快速排序算法

快速排序法又称为分割交换法，是对冒泡排序法的一种改进。其基本思想是：先在数据中找一个虚拟的中间值，并按此中间值将打算排序的数据分为两部分。其中，小于中间值的数据放在左边，大于中间值的数据放在右边；再用同样的方式处理左右两边的数据，直到排序完成为止。

例如，有n项数据，数据值用K₁, K₂, …, K_n来表示。其快速排序法操作步骤如下：

（1）先在数据中假设一个虚拟中间值K（为了方便，一般取第一个位置上的数）。

（2）从左向右查找数据K_i，使得K_i>K，K_i的位置数记为i。

（3）从右向左查找数据K_j，使得K_j<K，K_j的位置数记为j。

（4）若i<j，数据K_i与K_j交换，并回到步骤（2）。

（5）若i≥j，数据K与K_j交换，并以j为基准点分割成左右两部分，然后针对左右两部分再进行步骤（1）～步骤（5），直到左半边数据等于右半边数据为止。

例如，有这样一组数据：6, 1, 2, 7, 9, 3, 4, 5, 10, 8，如图4.41所示。采用快速排序法递增排序，步骤如下。

（1）取原始数列的第一个数6为虚拟中间值，即K=6；然后从左向右查找大于6的数，得到数字7，位置i=4；再从右向左查找小于6的数，得到数字5，位置j=8，如图4.42所示。

（2）i<j，因此交换K_i（数字7）和K_j（数字5）的位置，完成第一次排序。继续从左向右查找值大于6的数，即数字9，位置i=5；再从右向左查找值小于6的数，即数字4，位置j=7，如图4.43所示。

（3）i<j，因此交换K_i（数字9）和K_j（数字4）的位置，完成第二次排序。继续从左向右查找值大于6的数，即数字9，位置i=7；再从右向左查找值小于6的数，即数字3，位置j=6，如图4.44所示。

（4）i>j，因此交换虚拟中间值K（数字6）和K_j（数字3）的位置，完成第三次排序。此时，发现6的左半边都是小于6的数，右半边都是大于6的数，虚拟中间值6变成了真正的中间值，如图4.45所示。

（5）对中间值6左半边的数据排序，中间值和右半边数据暂时可以忽略。在左半边取第一个位置的数为虚拟中间值，即K=3，从左向右查找大于3的值，即数字5，位置i=4；再从右向左查找小于3的值，即数字2，位置j=3，如图4.46所示。

（6）i >j，因此需要交换虚拟中间值K（数字3）和K_j（数字2）的值，如图4.47所示。此时虚拟中间值变成了真正的中间值。小于3的都在中间值3的左半边，大于3的都在中间值3的右半边。

（7）接下来对中间值3的左、右两侧排序，排序后的结果如图4.48所示。

（8）此时，整组数据的左半边已经完成排序，接下来需要忽略已排序好的左半边和中间值6，对右半边进行排序。取右半边第一个位置的数为虚拟中间值，即K=9，然后从左向右找大于9的值，即数字10，位置i=9；再从右向左找小于9的值，即数字8，位置j=10，如图4.49所示。

（9）i<j，因此交换K_i（数字10）和K_j（数字8）。然后再从左向右查找大于9的值，即为数字10，位置i=10；再从右向左找小于9的值，即为数字8，位置j=9，如图4.50所示。

（10）i>j，因此交换虚拟中间值K（数字9）和K_j（数字8）的值，此时，虚拟中间值变成为真正的中间值，如图4.51所示。

（11）以中间值9为界，分为左右两侧，再进行排序，最后完成右半边排序，如图4.52所示。

（12）结合左半边排序和右半边排序，最终的排序结果如图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所示。