【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; }</code>