举例说明什么是快速排序算法（分割交换排序法）？

排序（Sorting）算法是经常使用的一种算法，就是将一组数据按照某一个特定规则重新排列，使数据具有递增或递减的次序关系。按照特定规则用以排序的依据称为键（Key），它所含的值称为“键值（Key Value）”。排序的各种算法称得上是数据结构这门学科的精髓所在。每一种排序方法都有其适用的情况与数据类型。

快速排序（Quick Sort）是由C.A.R.Hoare提出来的。快速排序法又称分割交换排序法，是目前公认最佳的排序法，也是使用“分而治之”的方式。这种算法会先在数据中找到一个虚拟的中间值，并按此中间值将所有打算排序的数据分为两部分，其中小于中间值的数据放在左边，而大于中间值的数据放在右边，再以同样的方式分别处理左右两边的数据，直到排序完为止。操作与分割步骤如下：

假设有n项记录R ₁ 、R ₂ 、R ₃ 、…、Rn，其键值为K ₁ 、K ₂ 、K ₃ 、…、K _n 。

步骤01 先假设K的值为第一个键值。

步骤02 从左向右找出键值K _i ，使得K _i >K。

步骤03 从右向左找出键值K _j ，使得K _j <K。

步骤04 如果i<j，那么K _i 与K _j 互换，并回到 步骤02 。

步骤05 若i≥j，则将K与K _j 交换，并以j为基准点分割成左右部分。

步骤06 针对左右两边进行 步骤01 至 步骤05 的操作，直到左半边键值等于右半边键值为止。

下面示范用快速排序法对数据进行排序的过程，原始数据如图3-18所示。

步骤01 因为i<j，故交换K _i 与K _j ，如图3-19所示，然后继续比较。

步骤02 因为i<j，故交换K _i 与K _j ，如图3-20所示，然后继续比较。

步骤03 因为i≥j，故交换K与K _j ，并以j为基准点分割成左右两半，如图3-21所示。

经过上述这几个步骤，大家可以将小于键值K的数据放在左半边；大于键值K的数据放在右半边，按照上述排序过程对左右两边再分别排序，过程如图3-22所示。