快速排序的原理和实现（纯白话文口述）
快速排序的形象例子：
一队人组成两排拍集体照，拍摄者发现有些前排队员身高太高挡住了后排队员，于是想弄一个法子来确保后排所站队员的身高不低于前排队员。第一次想到的是先将所有队员从低到高进行排序，然后将排好的序列从某个地方折断成两个部分，前一部分的作为前排，后一部分的作为后排。但这种方式效率太低了太耗时了，因为它不但确定了某个队员是属于前排还是后排，而且还确定了该队员在该所属排中的具体位置，即做了许多无用的操作，所以太慢了。接着想到的是将所有队员以其中某个队员的身高为参考基准，身高高于他的队员站后排，身高低于他的队员站前排。对身高等于他的队员不做要求，即原来属于前排就仍然在前排，原来属于后排就仍然在后排（为什么身高等于的不做要求，因为这样有个好处，如果所有队员身高都等于该队员，那么就不需要做任何调整了）。由于没有进一步要求每排队员相互之间的身高顺序（譬如左边的队员身高不能比右边的队员低），所以从整体上来看，这可以看作是一次为了操作方便（即节省时间、速度快）而进行的粗略排序，这个粗略排序只有一个简单的规则，即后排身高不能低于前排（如果进一步要求同排左方队员不能低于右方队员，显然这就会增加操作的复杂度，导致所需时间增加，即速度变慢）。这种粗略的排序因为操作方便，实施起来速度快，所以又叫快速排序。
快速排序的两种基本思想：
思想一：通过一趟排序将数组分割成两部分，其中一部分的任意一数据都大于或等于另一部分的任意一数据，这样的一次排序称作为一次快速排序。然后再用同样的方法分别对被分割而成的两部分数组进行快速排序，一直递归下去，直到分割所得到的部分包含的数据个数不大于一为止。
这种思想的内在原理是，当把一个数组分成两个部分时，虽然各部分中的元素仍然是处于无序状态，但是此时元素所在位置与最终数组完全排好序后该元素所处的位置的相离的更近一些了。随着快速排序的一次次递归下去，元素所处的位置与最终排好序所处的位置离的越来越近，直至元素位置最终等于数组完全排好序时该元素所处的位置，整个数组排序完成。
也就是说，一开始数组元素位置的可变动范围很大，随着快速排序的递归执行，元素的可变动范围越来越小，直至元素的位置最终被完全确定，排序结束。
思想二：通过一趟排序将数组分割成两部分另加一个基准元素，其中一部分的任意一数据都大于或等于基准元素值，另一部分的任意一数据都小于或等于基准元素值，将这样的一次排序也称作为一次快速排序。然后再用同样的方法分别对被分割而成的两部分数组进行快速排序，一直递归下去，直到分割所得到的部分包含的数据个数不大于一为止。
这种思想的内在原理是，每一次快速排序，都会使得选出来的基准元素被放在一个正确的位置，这个位置与整个数组完全排好序后的位置是一致的（都是左边的元素小于或等于它，右边的元素大于或等于它）。随着快速排序的递归进行，越来越多的基准元素被放在了正确的位置，知道所有的元素都被用作基准元素放在了正确位置，排序结束。
快速排序实现的要点：
要点在于如何将一个数组拆分成两个满足快速排序规则的子数组，即一个子数组中的所有元素都大于或等于另一个子数组中的元素，这其中容易存在两种错误的直觉，或者说是两种错误的潜意识。下面分别介绍下这两种错觉以及应该形成一个怎样的正确的直觉：
1. 错误直觉之俩子数组长度相等：很容易产生一种错觉，认为对数组进行一趟快速排序后，将会产生两个长度相等（或长度大小相差不超过一）的子数组。而因为有这种错觉，甚至使人在实现快速排序算法的时候，直接先把数组分为两个部分，然后将数值大于某参考元素值的元素放于其中一个部分，其它的元素放入另一个部分（这是错误的，因为实际一趟快速排序很可能会将数组分割成两个不同长度的数组，所分出来的俩数组长度决定于快速排序时所选择的参考元素的值的大小）。
2. 错误直觉之参考元素位置决定俩子数组分界线：另一个容易产生的错觉是，既然我们选择了一个参考元素，那么将各元素与参考元素相比较，较小的元素放参考元素左边，较大的元素放参考元素右边，结束后将数组分为以参考元素位置为分界线的两个数组（这也是错误的，原因同上，也就是有可能参考元素的左边没有多余的位置盛放需要挪到左边的元素，而挪到右边的元素太少，根本没有占满右边数组的空位）。
正确直觉的建立：那么怎么来确定两个子数组的分界点呢？可以假想从数组的两端各有一个盛放小于等于和大于等于参考值元素的子数组（将一次快排所操作的数组视为母数组，若参考元素为母数组的第一个元素，则左子数组的始地址为母数组左端的第二个元素的地址），并且两子数组以逐渐向对方增长的方式来最终得到一个分割点。即可以在母数组的左端遍历，将符合“小于等于参考值”规则的元素统计为左子数组的一部分，直到找到第一个大于参考值的元素，然后在母数组的右端反向遍历，将符合“大于等于参考值”规则的元素统计为右子数组的一部分，直到找到第一个小于参考值的元素，此时两个子数组因为遇到了违反规则的元素，所以两个数组停止增长。这时如果俩数组还没有相遇或相交，则将两个元素彼此交换，交换后两个子数组又可以继续进行相向增长，直到两子数组停止增长时（遇到不符合与参考元素大小关系的元素或遇到了母数组的边界）发现两个子数组已经相接或重叠时为止（重叠是因为含有等于参考元素值的元素，这些元素可以属于两个子数组中的任何一个数组），此时再将参考元素与右子子数组起始地址的前一个元素进行交换（该元素可能是左子数组中最后一个不属于右子树的元素，也可能是参考元素自身。也就是说，参考元素不能与右子数组中的下标最小的元素进行交换，因为这个元素可能大于参考元素。由于最初参考元素选择的是母数组的第一个元素，元素位置应处于左子数组，所以参考元素不能与右子数组的元素交换，否则交换后，左子数组中的元素可能会违反与参考元素的大小规则。交换后，左子数组从母数组第一个元素开始，到交换后的参考元素的前一元素为止），交换后，参考元素的位置就是俩数组的分割点，并且也是整个母数组有序化后参考元素应该在的位置。由于参考元素已经放在了应该放的位置，所以参考元素不必参与后续的左右子数组快排过程。
不存在的零长子数组问题：
利用快速排序思想进行排序时，思考的深一些的时候还会有另一种错觉，其实它是不存在的，下面来介绍一下：
错误直觉之零长子数组导致无穷递归：有时候会忽然想到“将母数组分为俩子数组时，会不会出现其中一子数组的长度为零，另一子数组的长度为整个母数组的长度”，即导致实际一趟快排并没有将一个数组分为两个数组的效果，从而出现无穷次数的递归调用快速排序呢。
解答：会出现分成的两个数组一个长度为零，另一个为母数组长度减一的情况。但这并不会出问题，因为参考元素是不参与下一次快速排序的。一次快速排序完毕后，参考元素总能放到它应该在的位置，并且不再参与下一次俩子数组的快速排序。所以俩子数组即使有一个长度为零，但另一个子数组的长度还是要比原母数组长度小（少一个元素即参考元素）。所以快速排序的递归调用不会无穷次数的进行下去。
快速排序代码（C++版）（使用思想二实现）：
#include <iostream>
using namespace std;
void Qsort(int arr[], int low, int high){
if (high <= low) return;
int i = low;
int j = high + 1;
/* 参考值取参与快速排序的第一个元素 */
int key = arr[low];
while (true)
{
/*从左向右找比key大的值, 实际是找左子数组向右生长的停止元素*/
while (arr[++i] <= key) //++i：即快速排序从参考元素的下一位置元素开始
{
if (i == high){
break;
}
}
/*从右向左找比key小的值，实际上是找右子数组向左生长的停止元素*/
while (arr[--j] >= key)
{
if (j == low){
break;
}
}
/* 俩子数组相接或交叉，则一段快速排序完成 */
if (i >= j) break;
/*交换i,j对应的值，实际是交换左右俩子数组的停止元素，使得俩数组可以继续生长*/
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/*参考值与j对应值交换*/
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
/* 参考元素（元素下标为j）不再参与下一次快排 */
Qsort(arr, low, j - 1);
Qsort(arr, j + 1, high);
}
int main()
{
int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24};
Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1);/*这里原文第三个参数要减1否则内存越界*/
for(int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
{
cout << a[i] << "";
}
return 0;
}/*参考数据结构p274(清华大学出版社，严蔚敏)*/