快速排序(QUICK SORT)

冒泡排序是通过遍历整个链表，进行两两比较、交换操作的排序方法。然而，该方法在每一趟遍历过程中，只是简单的在两个相邻的元素中操作，如果能对每一次的比较结果进行利用，有可能提高排序效率。

快速排序就是这样的一种排序方法。同样是利用比较交换的思想，只是每次比较的元素选取不同：冒泡排序是通过比较相邻的两个元素，而快速排序是列表中元素与枢轴(Pivot)进行比较，大的元素交换到枢轴后面，小的元素交换到枢轴前面。这样就利用到了每一次的比较结果。

如果一个队列中只有三个元素，分别是2、3、1，如果以2为枢轴，3比2大，1比2小，那么只需要将最小的1放在枢轴2的位置上，最大的3放到最小的1的位置上，2放在最大的3的位置上。

快速排序一般步骤：

• 选取枢轴，一般选取队列的第一个元素作为枢轴pivotkey；
• 分别从队列的首和尾进行遍历。从首部找到第一个大于枢轴的元素为止，位置记为i，从尾部找到第一个小于枢轴的元素为止，位置记为j；
• 交换操作是这三个元素进行交换。和前面提到的三个元素交换方法相类似，最小的元素j放在枢轴pivotkey上，最大的元素i放在最小的元素j的位置上，枢轴pivotkey放在最大的位置i上；
• 从两端想中间遍历，一趟遍历直到交汇为止，即i==j；
• 每一趟结束后，都会将当前队列分割成两个子队列，对两个子队列分别进行1～4步操作。直到子队列大小为1时，排序结束。

快速排序特性：

• 快速排序每一趟排序结束，都会有一个元素(即枢轴Pivot)在最终位置上，其前面的元素都比它小，后面的元素都比它大；
• 一趟排序结束，会产生两个子队列，分别对这两个子队列进行排序。这是分治的思想，分而治之；
• 如果待排序队列基本有序，例如正序或者逆序，此时枢轴为队列中最大(小)的值，所以从两个开始遍历的操作只能找到一个队列中最小(大)的值来进行交换，此时快速排序变退化成了冒泡排序。例如队列1、2、3和2、3、1，前者虽然不需要交换操作，但是需要两趟遍历，第一趟确定1的位置，第二趟确实2和3的位置，后者只需要一次交换操作就可以完成排序；
• 排序的效率和初始化队列排序情况与枢轴的选取有关。枢轴越接近队列的中间值越好，队列越混乱越好；
• 快速排序通过使用分治的思想，减少了排序趟数，冒泡排序数量级是O(n)，而快速排序数量级是O(log_{2} n)，所以时间复杂度是O(nlog_{} n)；
• 排序的过程中只是交换的时候需要申请临时空间，空间复杂度是O(1)；
• 快速排序不稳定。

快速排序实例：

• {49, 38, 65, 97, 76, 13, 27, 49} 初始序列；
• {27, 38, , 97, 76, 13, 65, 49} 将49作为枢轴，并将其保存在临时空间内，从38开始遍历，找到第一个大于49的元素65，然后从49开始遍历，找到第一个小于49的元素27。将这3个元素进行交换，枢轴的位置存放最小的元素27，最小元素13的位置存放最大元素65，最大元素位置存放枢轴49。继续遍历，找到最小元素13，最大元素97。一趟排序结束；
• {27, 38, 13}, 49, {76, 97, 65, 49} 一趟排序结果；
• {13}, 27, {38}, 49, {49, 65}, 76, {97} 对两个子序列分别进行快速排序；
• 13, 27, 38, 49, 49, 65, 76, 97 最终结果。

原文链接：快速排序(QUICK SORT)，转载请注明来源！