1.2.1 快速排序的原理
快速排序又称为分区交换排序，简称快排。快排是排序中的一种算法，最早由托尼·霍尔提出。以从小到大快排为例，其主要思想是：
（1）在一个待排序的序列中取出一个元素作为中心元素（可以用第一个、最后一个，也可以是中间任意一个），习惯上将其称为基准；
（2）将所有比基准小的放在其左边，将所有比基准大的放在其右边，形成左右两个子表；
（3）对左右两个子表按照前面的算法进行排序，直到每个子表的元素只剩下一个。
显然，快排用到了分而治之的思想。将一个数组分成两个数组的方法为：
（1）从数组的右边找到一个比基准元素小的元素，将数组的第一个位置赋值给该元素；
（2）从数组的左边找到一个比基准元素大的元素，将从上面取元素的位置赋值为该值；
（3）依次进行，直到左右相遇，将基准元素赋值到相遇位置。
1.原始数组的第一次快速排序
为了更清楚地说明快排算法，下面举一个例子。假设一个数组：
x={39,28,55,87,66,3,17,40}
（1）定义基准，将其初始化为第一个元素的值，即39。其中，查询左边元素的指针为left，查询右边元素的指针为right，如图1.8所示。
图1.8 初始指针left和right的位置
（2）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，遇到17时，因为17<基准，因此将x［right］填入到x［left］，即此时变量left指向的数为17，如图1.9所示。
图1.9 原始数组right从右向左遍历第一次的结果
（3）left从左边开始遍历，找到第一个比基准大的元素，如果没找到，left一直递增1，遇到55时，因为55>基准，因此将x［left］填入到x［right］，即此时指针right指向的数为55，如图1.10所示。
图1.10 left从左向右遍历第一次的结果
（4）right继续从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，遇到3时，因为3<基准，因此将x［right］填入到x［left］，即此时指针left指向的数为3，如图1.11所示。
图1.11 right从右向左遍历第二次的结果
（5）left从左边开始遍历，找到第一个比基准大的元素，如果没找到，left一直递增1，遇到87时，因为87>基准，因此将x［left］填入到x［right］，即此时指针right指向的数为87，如图1.12所示。
图1.12 left从左向右遍历第二次的结果
（6）right继续从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，此时出现left和right重合，因此在left和right重合的位置，填入基准值，如图1.13所示。
图1.13 left和right重合
这样，就将数组分成了两个子数组，即{17，28，3}和{66,87,55,40}。
2.第一个子数组的快速排序
本部分将介绍如何对子数组{17，28，3}进行快速排序。
（1）定义基准，将其初始化为第一个元素的值，即17。查询左边元素的指针为left，查询右边元素的指针为right，如图1.14所示。
（2）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，遇到3时，因为3<基准，因此将x［right］填入x［left］，即此时指针left指向的数为3，如图1.15所示。
图1.14 初始指针left和right的位置
图1.15 right从右向左遍历第一次的结果
（3）left从左边开始遍历，找到第一个比基准大的元素，如果没找到，left一直递增1，遇到28时，因为28>基准，因此将x［left］填入到x［right］，即此时指针right指向的数为28，如图1.16所示。
（4）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，结果left和right重合，因此在left和right重合的位置，填入基准值，如图1.17所示。
图1.16 left从左向右遍历第一次的结果
图1.17 right从右向左遍历第二次的结果
由于左侧和右侧都只有一个元素，因此排序结束。
3.第二个子数组的快速排序
本部分将介绍如何对子数组{66,87,55,40}进行快速排序。
（1）定义基准，将其初始化为第一个元素的值，即66。查询左边元素的指针为left，查询右边元素的指针为right，如图1.18所示。
（2）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，遇到40时，因为40<基准，因此将x［right］填入到x［left］，即此时指针left指向的数为40，如图1.19所示。
图1.18 初始指针left和right的位置
图1.19 right从右向左遍历第一次的结果
（3）left从左边开始遍历，找到第一个比基准大的元素，如果没找到，left一直递增1，遇到87时，因为87>基准，因此将x［left］填入到x［right］，即此时指针right指向的数为87，如图1.20所示。
（4）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，因为55<基准，因此将x［right］填入到x［left］，即此时指针left指向的数为55，如图1.21所示。
图1.20 left从左向右遍历第一次的结果
图1.21 right从右向左遍历第二次的结果
（5）left从左边开始遍历，找到第一个比基准大的元素，如果没找到，left一直递增1，结果left和right重合，因此在left和right重合的位置，填入基准值，如图1.22所示。
由于左侧有两个元素{40,55}，因此需要再一次快排；而右侧只有一个元素，因此无须进行排序。
4.第三个子数组的快速排序
本部分将介绍如何对子数组{40,55}进行快速排序。
（1）定义基准，将其初始化为第一个元素的值，即40。查询左边元素的指针为left，查询右边元素的指针为right，如图1.23所示。
图1.22 left从左向右遍历第二次的结果
图1.23 初始指针left和right的位置
（2）right从右边开始遍历，找到第一个比基准小的元素，如果没找到，right一直递减1，结果left和right重合，因此在left和right重合的位置，填入基准值，如图1.24所示。
图1.24 right从右向左遍历第一次的结果
因此，快速排序的过程如图1.25所示。
图1.25 快速排序的过程