QuickSort，快速排序。数据结构必然遇上之，原理都知道是分治法，但不实现一次总有些心慌。而一步一步实现算法的时候，往往会遇到新问题，新困难，新考验。本篇从QuickSort算法的理解说起，希望我不会又忘记了吧~——ZwqXin.com
本文来源于 ZwqXin (http://www.zwqxin.cn/), 转载请注明
原文地址：http://www.zwqxin.cn/archives/arithmetic/quick-sort-implement.html
1.二分治十分喜欢logN
我不太清楚这鼓仰慕之情是从哪里来的，是偶然的吗？不，大妈都说，只有必然。因此，请相信严谨的数学大师给予我们的教诲：二分治就是就是喜欢logN。而QuickSort是二分治，所以说起QuickSort，我们就联想起logN......注意底数是二哦。
把一个问题分解为两个，把两个问题分解为四个......分解直到能轻易解决当前问题的地步，再如同聚焦一样反噬回来——把原问题解决。假设底线是分解为N个，那么共经过logN次分解行为。当然这每次分解行为都包含了多个分解动作，但只要它们是同时发生的，就不必区分它们——这是什么道理？
2.QuickSort的道理
QuickSort处理N个数的时候，就是按上思路，先选取一个“主元”，再把整个数列分割成两部分，前部分的值小于“主元”，后部分的值大于“主元”——主元位于这两部分之间。然后分别对这两部分再做此处理（递归），最后就成了一组从小到大排列的数表了。主元的选取本来应该很考究，但为了效率应该随便选一个。理想情况是主元位是当前排序表中间大的元素，这样分出来的两子列将基本等大；如果不好采每次选的主元都是最小的那个，那就等着N^2的复杂度来收尾吧。但若非精心安排，是难以出现这个局面的，这里有篇文章[算法与数据结构——快速排序]用一堆数学证明了平均情况跟最好情况一样是N*logN（最好情况：二分，分解logN次，每次里都蕴涵N次比较换位）。
3.大于.小于
比较动作涉及比较换位，若是数值类型还好办，其他类型的怎么办呢？很明显需要自定义我们的“大于.小于”。由于相反性，就考虑小于就可以了（元素相等也得处理啊，归于“大于”那里吧）。抽象出这个“小于”函数，设为QSCompareL(A，B)，则整个QS算法弄成以下模样：
- template<typename ObjectQS>
- int QSort<ObjectQS>::Partition(ObjectQS *buffer, int low, int high, bool (*QSCompareL)( ObjectQS A, ObjectQS B))
- {
- ObjectQS pivotkey = buffer[low];
- while(low<high)
- {
- //while(low<high && buffer[high].ID >= pivotkey)
- //while(low<high && QsortCompareGE(buffer[high], pivotkey) )
- while(low<high && !(*QSCompareL)(buffer[high], pivotkey) )
- high--;
- if(low < high)
- buffer[low++] = buffer[high];
- //while(low<high && buffer[low].ID <= pivotkey)
- //while(low<high && QsortCompareLE(buffer[low], pivotkey) )
- while(low<high && (*QSCompareL)(buffer[low], pivotkey) )
- low++;
- if(low < high)
- buffer[high--] = buffer[low];
- }
- buffer[low] = pivotkey;
- SORTtimes++;
- return low;
- }
- template<typename ObjectQS>
- void QSort<ObjectQS>::SetQSortObject(ObjectQS *buffer, int low, int high, bool (*QSCompareL)( ObjectQS A, ObjectQS B))
- {
- QSortObject = buffer;
- mLow = low;
- mHigh = high;
- QSCompareL_Func = QSCompareL;
- }
- template<typename ObjectQS>
- void QSort<ObjectQS>::CalQSortProcess(int low, int high)
- {
- if(low<high)
- {
- int pivotloc = Partition(QSortObject, low, high, QSCompareL_Func);
- CalQSortProcess(low, pivotloc-1);
- CalQSortProcess(pivotloc+1, high);
- }
- }
- template<typename ObjectQS>
- void QSort<ObjectQS>::QSortProcess()
- {
- CalQSortProcess(mLow, mHigh);
- }
上面的注释行表明了一路下来代码的进化。递归的思路就不多说了，QSORT的核心是Partition函数和CalQSortProcess。基本上外调用之QSortProcess函数要知道的是待比较表和表的起始和结束位置，还有比较函数。这由SetQSortObject设置。函数编写运用了类模板，ObjectQS是随意的类型，因此使用者要自定义比较函数——当然对单纯的数值类型也可以不用，因为我给了个默认形参QsortCompareL专门比较数值类型的。
4.在游戏中的运用
排序是到处都需要用的东西。比起冒泡，Qsort具有明显的优势，事实上VC函数库也给出了简单数值的QSORT的API调用，STL里面的通用函数SORT很明显跟QSORT有关，我也很明显是看着STL之SORT来作为程序完备性的衡量.....
在游戏中，有时候需要给眼前怪物的ID排序，有时候需要知道怪物位置前后信息……实在太多应用了，只有你想不到的。
- typedef struct tagObjectX{
- unsigned int ID;
- CVector3 Position;
- CVector3 Rotation;
- } ObjectX;
- bool CompareObjectX_ID(ObjectX A, ObjectX B){ return A.ID < B.ID; }
- bool CompareObjectX_PosZ(ObjectX A, ObjectX B){ return A.Position.z < B.Position.z; }
- int main(int argc, char* argv[])
- {
- ObjectX ObjectArray[10] = {.....};
- //qsortX.SetQSortObject(ObjectArray, 0, 9, CompareObjectX_PosZ);
- qsortX.SetQSortObject(ObjectArray, 0, 9, CompareObjectX_ID);
- qsortX.QSortProcess();
- int buffer[40] = {23,56,23,....,50,100,98};
- qsortX2.SetQSortObject(buffer, 0, 39);
- qsortX2.QSortProcess();
- printf("SORTtimes:%d\n",qsortX2.GetSortTimes());
- printf("index:%d\n", qsortX2.GetElementIndex(88) );
- return 0;
- }
最后一行是返回查找元素的索引，既然都排好序了，何不用折半查找？于是就实现了一下折半查找，恩，又是递归，又是二分治，又是logN。
放出DEMO：QuickSort-searchByZwqXin.rar
本文来源于 ZwqXin (http://www.zwqxin.cn/), 转载请注明
原文地址：http://www.zwqxin.cn/archives/arithmetic/quick-sort-implement.html