C++实现类型不限的序列的划分算法
代码:
/**
* project: partition template
* author:billhoo
* date: 2012年3月10日
*/
#pragma once
#ifndef _PARTITION_H
#define _PARTITION_H
template<class Iterator, class Comp>
Iterator partition(Iterator beg, Iterator end){
//为避免部分编译器对迭代器的限制，本算法从后往前遍历
//以首元素作为分界值，当然，我们还可以取随机下标作为
//分界值以获得平均算法时间
using std::swap;
typedef typename std::iterator_traits<Iterator>::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
复制内容到剪贴板
代码:
/**
* author:billhoo
* date: 2012年3月10日
*/
#include<iostream>
#include<list>
#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<int> intList(intArr, intArrEnd);
displayArr<int*>(intArr, intArrEnd);
partition<int*, std::greater<int>>(intArr, intArrEnd);
displayArr<int*>(intArr, intArrEnd);
displayArr(intList.begin(), intList.end());
partition<list<int>::iterator, std::greater<int>>(intList.begin(), intList.end());
displayArr(intList.begin(), intList.end());
return EXIT_SUCCESS;
} 本文转自Bill_Hoo 51CTO博客，原文链接：http://blog.51cto.com/billhoo/802141，如需转载请自行联系原作者
