高速经济的排序算法有没有一种既不浪费空间又可以更快的排序算法？那就是“快速排序”！是不是光听名字就觉得很高端？假设我们现在正在对10个数字“61279345108”进行排序。首先在这个数列中随机找一个数作为参考数（不要被这个词吓到，是一个参考数，以后就知道是干什么用的了）。为方便起见，让第一个数字6为基准数字。接下来，需要把这个数列中所有大于参考数的数放在6右边，小于参考数的数放在6左边，类似下面的排列：31254697108in在初始状态下，数字6是序列中的第一个。我们的目标是把6移动到序列中间的某个位置，假设这个位置是k。现在我们要求出这个k，并以第k位为分界点，左边的数都小于等于6，右边的数都大于等于6。想一想，有没有办法做到这一点？排序算法显示其强大的方法其实很简单：从初始序列“61279345108”的两端开始“检测”。先从右到左找一个小于6的数，再从左到右找一个大于6的数，然后交换。这里可以使用两个变量i和j，分别指向序列的最左边和最右边。我们给这两个变量起了好听的名字“sentineli”和“sentinelj”。一开始让sentineli指向序列最左边（即i=1），指向数字6。让sentinelj指向序列最右边（即=10），指向数字。第一个哨兵j开始派遣。因为这里设置的benchmark数是最左边的数，所以让sentinelj先dispatch很重要（请想想为什么）。Sentinelj一步步向左移动（即j--），直到找到一个小于6的数，停止。接下来，哨兵i一步步向右移动（即i++），直到找到大于6的数停止。***哨兵j停在数字5前面，哨兵i停在数字7前面。现在交换哨兵i和哨兵j指向的元素的值。交换后的顺序如下：61259347108至此，第一次交换结束。接下来哨兵j继续向左移动（友情提示，每次哨兵j必须先出发）。他找到了4个（比基准数6小，符合要求）就停了下来。Sentineli也继续向右移动，在找到9（大于基准数字6，符合要求）后停了下来。此时再次进行交换，交换后的顺序为：61254397108第二次交换结束，继续“试探”。Sentinelj继续向左移动。他找到了3个（比基准数6小，符合要求）然后停了下来。Sentineli继续向右移动，哎呀！这时候哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到了3。说明“检测”到此结束。我们交换基数6和3，交换后的序列如下：31254697108至此，第一轮“检测”才真正结束。此时以参考数字6为分界点，6左边的数字都小于等于6，6右边的数字都大于等于6。在刚才的过程中，其实sentinelj的任务是找到一个比参考数小的数，sentineli的任务是找到一个比参考数大的数，直到i和j相遇。OK，说明结束。基数6现在就位，它恰好是序列中的数字6。至此，我们已经将原始序列拆分为以6为分界点的两个序列。左边的序列是“31254”，右边的序列是“97108”。接下来，需要分别处理这两个序列。因为6左右的序列还是很混乱的。不过没关系，我们已经掌握了方法，接下来我们只需要模拟刚才的方法就可以分别处理6左右的序列了。现在让我们先处理6左边的数列。左边的序列是“31254”。请以3为基础调整这个数列，使3左边的数都小于等于3，3右边的数都大于等于3。好了，开始写吧。如果你的模拟是正确的，调整后的顺序应该是：21354OK，现在3已经回到原位了。接下来需要处理3左边的序列“21”和右边的序列“54”。序列“21”以2为基数进行调整，处理后的序列为“12”，2又回到了原位。序列“1”只有一个数，不需要任何处理。至此我们处理完了序列“21”，得到的序列为“12”。序列“54”的处理也是仿照这个方法，最终得到的序列如下：12345697108对于序列“97108”也是模拟刚才的过程,直到无法分离新的序列。的后续。最终会得到这样一个序列，如下：12345678910至此，排序就彻底结束了。细心的同学可能已经发现，每一轮快速排序其实都是在返回本轮的基准数字，直到所有数字都到位，排序结束。下面这张霸气的图描述了整个算法的处理过程。为什么是这样？快速排序更快，因为与冒泡排序相比，每次交换都是一次跳跃。每次排序时设置一个参考点，将所有小于或等于参考点的数放在参考点的左边，所有大于或等于参考点的数放在参考点的右边。这样，每次交换不仅会像冒泡排序那样每次只交换相邻的数，而且交换距离会大很多。所以总的比较和交流的次数少了，速度自然就提高了。当然，在最坏的情况下，还是有可能两个相邻的号码已经互换了。因此，快速排序和冒泡排序最差的时间复杂度为O(N2)，其平均时间复杂度为O(NlogN)。事实上，快速排序是基于一种叫做“两点”的思想。后面会遇到“二分法”思维，以后再说。先添加代码，如下#include
