快速排序

快速排序的基本思想是：通过一趟排序将待排序的记录划分为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后再分别对这两部分记录继续进行快速排序，以达到整个序列有序。

一趟快速排序的具体做法是：附设两个位置指示变量i和j，它们的处置分别指向文件的第一个记录和最后一个记录。设枢轴记录（通常是第一个记录）的关键字为pivotkey，则首先从j所指位置起向前搜索，找到第一个关键字小于pivotkey记录，将其向前移，然后从i所指位置起向后搜索，找到第一个关键字大于pivotkey的记录，将其向后移，重复这两步，直至i与j相等为止。快速排序是不稳定的排序方法。时间复杂度为O(nlog2n), 被认为是平均性能最好的一种排序方式。 

举例如图：

  49   38   65  97  76  13  27  49            // i=0 , j =7 , pivot = 49

第一遍：因为已经抽出了pivot，所以腾出一个位置，将右侧小于pivot值的27，挪到了左侧。然后，将左侧大于pivot的65移动到了右侧腾出了27后的空位。

27   38   65  97  76   13  27   49

27   38   65  97  76   13   65   49

第二遍：i++，j-- 继续重复着上面第一遍的动作循环。

27   38    13   97  76  13  65   49

27   38    13    97  76  97  65  49

第三遍： 这时候，i = j，将pivot写回来到i所指的位置。

27   38   13   49   76   97  65   49      

这时候pivot已经在序列中拍好了，最后继续以pivot为界分成前后两个序列，继续递归。