【C++實作序列的劃分】

C++實作類型不限的序列的劃分算法

<code>/** * project: partition template * author:billhoo * date: 2012年3月10日 */ #pragma once #ifndef _PARTITION_H #define _PARTITION_H template&lt;class Iterator, class Comp&gt; Iterator partition(Iterator beg, Iterator end){   //為避免部分編譯器對疊代器的限制，本算法從後往前周遊   //以首元素作為分界值，當然，我們還可以取随機下标作為   //分界值以獲得平均算法時間   using std::swap;   typedef typename std::iterator_traits&lt;Iterator&gt;::value_type val_t;   Iterator left = end;   Iterator right = end;   val_t key = *beg;   for(--left; left != beg; --left)     if(Comp()(*left, key))       swap(*left, *--right);   swap(*beg, *--right);   return right; }// end of partition #endif</code>

複制内容到剪貼闆

<code>/** * author:billhoo * date: 2012年3月10日 */ #include&lt;iostream&gt; #include&lt;list&gt; #include"partition.h"  //partition #include"display_array.h"  //displayArr using std::cout; using std::endl; using std::list; int main(int argc, char **argv){   int intArr[ ] = {0,2,-48,3,4,-78,5,6,7,8,-5};   int *intArrEnd = intArr + sizeof(intArr) / sizeof(*intArr);      list&lt;int&gt; intList(intArr, intArrEnd);   displayArr&lt;int*&gt;(intArr, intArrEnd);   partition&lt;int*, std::greater&lt;int&gt;&gt;(intArr, intArrEnd);   displayArr&lt;int*&gt;(intArr, intArrEnd);   displayArr(intList.begin(), intList.end());   partition&lt;list&lt;int&gt;::iterator, std::greater&lt;int&gt;&gt;(intList.begin(), intList.end());   displayArr(intList.begin(), intList.end());   return EXIT_SUCCESS; }                          本文轉自Bill_Hoo 51CTO部落格，原文連結：http://blog.51cto.com/billhoo/802141，如需轉載請自行聯系原作者</code>