Author: bakari Date: 2012.7.21
排序算法有很多种，每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为快排。
快排是一个非常重要的算法，在各个领域几乎都有它的身影，尤其是文件检索这一块。运用一个好的排序算法是衡量一个软件优劣的关键因素，下面我就此总结一下快排的几种经典的情况：
转载引用请注明出处：http://www.cnblogs.com/bakari/archive/2012/08/11/2633545.html 谢谢！
我是用C++的类写的，存储结构为vector（这个无所谓），本来一个通用的快排函数应该是QuickSort(str, left ,right);
有了类之后我改写成了QuickSort(left, right);不过没关系，代码，函数都不重要，重要的是懂得算法的本质。
快排关键之处在于选取基准元素，根据基准元素所在的位置可以分为三种情况，下面分别述之。文中实例程序皆已测试通过。
关于快排的理解我不想多讲，简单地说就是给一个数据序列划分界限，小的放前面，大的放后面，然后在前域和后域分别递归进行。
如果想知道VC库中的快排函数的原理：请参考我的另一篇文章：
VC库中的快排函数详解：http://www.cnblogs.com/bakari/archive/2012/08/11/2633453.html
如果不懂的童鞋可以参考下面这个视频，这是我在网上找的一个超级形象的视频，懂的童鞋可以直接跳过，本文重点在于总结算法。
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了。
转载引用请注明出处：http://www.cnblogs.com/bakari/archive/2012/08/11/2633545.html 谢谢！
