经典排序之 快速排序
经典排序之 快速排序
Author: bakari Date: 2012.7.21
排序算法有很多种，每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为快排。
快排是一个非常重要的算法，在各个领域几乎都有它的身影，尤其是文件检索这一块。运用一个好的排序算法是衡量一个软件优劣的关键因素，下面我就此总结一下快排的几种经典的情况：
我是用C++的类写的，存储结构为vector（这个无所谓），本来一个通用的快排函数应该是QuickSort(str, left ,right);
有了类之后我改写成了QuickSort(left, right);不过没关系，代码，函数都不重要，重要的是懂得算法的本质。
快排关键之处在于选取基准元素，根据基准元素所在的位置可以分为三种情况，下面分别述之。文中实例程序皆已测试通过。
关于快排的理解我不想多讲，简单地说就是给一个数据序列划分界限，小的放前面，大的放后面，然后在前域和后域分别递归进行。
如果想知道VC库中的快排函数的原理：请参考我的另一篇文章：
VC库中的快排函数详解：https://cloud.tencent.com/developer/article/1017829
如果不懂的童鞋可以参考下面这个视频，这是我在网上找的一个超级形象的视频，懂的童鞋可以直接跳过，本文重点在于总结算法。
http://v.youku.com/v_show/id_XMzMyODk4NTQ4.html
1、基准元素选择第一个元素：
1 /******************************************************************
2 * Author: bakari Date :2012.7.21
3 * 快速排序
4 * 算法重点：选基准元素：比基准元素小的放前面，比基准元素大的放后面
5 * 第一种：基准元素选第一个元素
6 * 第二种：基准元素选中间元素
7 * 第三种：基准元素选序列最后一个元素
8 * 第三种算法关键在于找合适的位置将最后一个元素插入，然后在其两边在运用快排。
9 ******************************************************************/
10
11 /* 基准元素是第一个 */
12 void QuickSort::Quick_Sort1(int left,int right)
13 {
14 int iLeft = left;
15 int iRight = right;
16 int temp = QuickList[left]; //取第一个元素作为基准元素
17 while(iLeft < iRight)
18 {
19 while (iLeft < iRight && QuickList[iRight] >= temp) iRight --;
20 if (iLeft < iRight){
21 Swap(iLeft,iRight);
22
23 /* 这里有两种途径：交换和替换都可以，改动相应地方就可以了 */
24 /* 第二种方法 如文中注释的地方 */
25 //QuickList[iLeft] = QuickList[iRight];
26 //iLeft++;
27
28 }
29 while (iLeft < iRight && QuickList[iLeft] <= temp) iLeft ++;
30 if (iLeft < iRight){
31 Swap(iLeft,iRight);
32 //QuickList[iRight] = QuickList[iLeft];
33 //iRight--;
34 }
35 }
36 //QuickList[iLeft] = temp;
37 if (iLeft != left) Quick_Sort1(left,iLeft - 1);
38 if (iRight != right) Quick_Sort1(iRight + 1,right);
39 }2、基准元素选中间（最好的）
1 /* 基准元素是中间个 */
2 void QuickSort::Quick_Sort2(int left,int right)
3 {
4 int iLeft = left;
5 int iRight = right;
6 int iMiddle = (iLeft + iRight) / 2; //选中间元素
7 int temp = QuickList[iMiddle];
8
9 while (1)
10 {
11 while (QuickList[iRight] > temp) iRight--;
12 while (QuickList[iLeft] < temp) iLeft++;
13 if(iLeft >= iRight) break;
14 Swap(iLeft,iRight); //交换
15 }
16
17 if(iLeft != left) Quick_Sort2(left,iLeft - 1); //递归调用
18 if(iRight != right) Quick_Sort2(iRight + 1,right);
19 }3、基准元素选最后一个
这个是我之前没遇到过的，上课的教材也没有，老师也没讲，我也自己写过，可见，自己有多被动。这儿是我前两天看左飞的书时不小心看到的，个人觉得还蛮经典的。让我思维一下子开阔起来。
先说明这个快排的概念，先以最右边的s为标准，分为三部分，小于s的部分，大于s 的部分和未处理的。如下图：
在排序过程中 i 和 j 会不断地往右进行比较和交换，最后变成：
然后s值置于中间，按相同的方法再在左右区域进行相同的动作。如：
一个实际例子的演算如下：
代码展示：
1 void QuickSort::Quick_Sort3(int left,int right)
2 {
3
4 if (left < right)
5 {
6 int p = FindPosition(left,right);
7 Quick_Sort3(left,p - 1);
8 Quick_Sort3(p + 1,right);
9 }
10 }
11
12 /* 找最后一个元素的合适位置 */
13 int QuickSort::FindPosition(int left,int right)
14 {
15 int i = left - 1;
16 int iFind = QuickList[right];
17 for (int j = left;j != right;++j)
18 {
19 if (QuickList[j] <= iFind)
20 {
21 i++;
22 Swap(i,j);
23 }
24 }
25 Swap(i + 1,right);
26 return (i + 1);
27
28 }OK，目前我知道的快排就有这三种，熟练掌握着三种排序就OK了。
腾讯云开发者
