
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 运行结果