« 全屏反锯齿 - 多重采样ⅡVFW视频捕获之尝试 »

QuickSort 快速排序的实现

QuickSort,快速排序。数据结构必然遇上之,原理都知道是分治法,但不实现一次总有些心慌。而一步一步实现算法的时候,往往会遇到新问题,新困难,新考验。本篇从QuickSort算法的理解说起,希望我不会又忘记了吧~——ZwqXin.com

本文来源于 ZwqXin (http://www.zwqxin.com/), 转载请注明
      原文地址:http://www.zwqxin.com/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算法弄成以下模样:

  1. template<typename ObjectQS>
  2. int QSort<ObjectQS>::Partition(ObjectQS *buffer, int low, int high, bool (*QSCompareL)( ObjectQS A,  ObjectQS B))
  3. {
  4.     ObjectQS pivotkey = buffer[low];
  5.  
  6.     while(low<high)
  7.     {
  8.         //while(low<high && buffer[high].ID >= pivotkey)
  9.         //while(low<high && QsortCompareGE(buffer[high], pivotkey) )
  10.           while(low<high && !(*QSCompareL)(buffer[high], pivotkey) )
  11.             high--;
  12.  
  13.         if(low < high)
  14.             buffer[low++] = buffer[high];
  15.  
  16.         //while(low<high && buffer[low].ID <= pivotkey)
  17.         //while(low<high && QsortCompareLE(buffer[low], pivotkey) )  
  18.           while(low<high && (*QSCompareL)(buffer[low], pivotkey) )           
  19.             low++;
  20.  
  21.         if(low < high)
  22.             buffer[high--] = buffer[low];
  23.  
  24.     }
  25.  
  26.  
  27.     buffer[low] = pivotkey;
  28.  
  29.     SORTtimes++;
  30.     return low;
  31. }
  32.  
  33. template<typename ObjectQS>
  34. void QSort<ObjectQS>::SetQSortObject(ObjectQS *buffer, int low, int high, bool (*QSCompareL)( ObjectQS A,  ObjectQS B))
  35. {
  36.     QSortObject = buffer;
  37.     mLow = low;
  38.     mHigh = high;
  39.     
  40.     QSCompareL_Func = QSCompareL;
  41.  
  42. }
  43.  
  44. template<typename ObjectQS>
  45. void QSort<ObjectQS>::CalQSortProcess(int low, int high)
  46. {
  47.     if(low<high)
  48.     {
  49.         int pivotloc = Partition(QSortObject, low, high, QSCompareL_Func);
  50.         CalQSortProcess(low, pivotloc-1);
  51.         CalQSortProcess(pivotloc+1, high);
  52.     }
  53. }
  54.  
  55. template<typename ObjectQS>
  56. void QSort<ObjectQS>::QSortProcess()
  57.     CalQSortProcess(mLow, mHigh);
  58. }

上面的注释行表明了一路下来代码的进化。递归的思路就不多说了,QSORT的核心是Partition函数和CalQSortProcess。基本上外调用之QSortProcess函数要知道的是待比较表和表的起始和结束位置,还有比较函数。这由SetQSortObject设置。函数编写运用了类模板,ObjectQS是随意的类型,因此使用者要自定义比较函数——当然对单纯的数值类型也可以不用,因为我给了个默认形参QsortCompareL专门比较数值类型的。

4.在游戏中的运用

排序是到处都需要用的东西。比起冒泡,Qsort具有明显的优势,事实上VC函数库也给出了简单数值的QSORT的API调用,STL里面的通用函数SORT很明显跟QSORT有关,我也很明显是看着STL之SORT来作为程序完备性的衡量.....

在游戏中,有时候需要给眼前怪物的ID排序,有时候需要知道怪物位置前后信息……实在太多应用了,只有你想不到的。

  1. typedef struct tagObjectX{
  2.     unsigned int ID;
  3.     CVector3  Position;
  4.     CVector3  Rotation;
  5.  
  6. } ObjectX;
  7.  
  8. bool CompareObjectX_ID(ObjectX A, ObjectX B){   return A.ID < B.ID; }
  9. bool CompareObjectX_PosZ(ObjectX A, ObjectX B){ return A.Position.z < B.Position.z; }
  10.  
  11. int main(int argc, char* argv[])
  12. {
  13.    ObjectX ObjectArray[10] = {.....};
  14.  
  15.  
  16.     //qsortX.SetQSortObject(ObjectArray, 0, 9, CompareObjectX_PosZ);
  17.     qsortX.SetQSortObject(ObjectArray, 0, 9, CompareObjectX_ID);
  18.     qsortX.QSortProcess();
  19.  
  20.  
  21.         int buffer[40] = {23,56,23,....,50,100,98};
  22.  
  23.       qsortX2.SetQSortObject(buffer, 0, 39);
  24.       qsortX2.QSortProcess();
  25.     
  26.       printf("SORTtimes:%d\n",qsortX2.GetSortTimes());
  27.       printf("index:%d\n", qsortX2.GetElementIndex(88) );
  28.  
  29.     return 0;
  30. }
  31.  

最后一行是返回查找元素的索引,既然都排好序了,何不用折半查找?于是就实现了一下折半查找,恩,又是递归,又是二分治,又是logN。

放出DEMO:QuickSort-searchByZwqXin.rar

本文来源于 ZwqXin (http://www.zwqxin.com/), 转载请注明
      原文地址:http://www.zwqxin.com/archives/arithmetic/quick-sort-implement.html

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

IE下本页面显示有问题?

→点击地址栏右侧【兼容视图】←

日历

Search

网站分类

最新评论及回复

最近发表

Powered By Z-Blog 1.8 Walle Build 100427

Copyright 2008-2013 ZwqXin. All Rights Reserved. Theme edited from ipati.