Source
#ifndef kimi_quicksort
#define kimi_quicksort
#include <functional>
#include <iterator>
#include <algorithm>
namespace kimi_boost
{
using namespace std;
template<class RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last)
{
//>= and <= operator
typedef greater_equal<
typename iterator_traits<RandomAccessIterator>::value_type >
Compare1;
typedef less_equal<
typename iterator_traits<RandomAccessIterator>::value_type >
Compare2;
if (distance(first,last) <= 1) return;
RandomAccessIterator i = first, j = last-1, n = first;
//partition
while (i < j)
{
while (i < j && Compare1()(*j,*n) ) --j;
iter_swap(n, j);
n = j;
while (i < j && Compare2()(*i,*n) ) ++i;
iter_swap(n, i);
n = i;
}
//递归
if(first != n)
quicksort(first, n - 1);
if(n != last)
quicksort(n + 1, last);
}
}
#endif//kimi_quicksort
Test code
void loki_pool_test2()
{
std::vector<unsigned> vi;
std::deque<unsigned> di;
vi.push_back(rand());
vi.push_back(rand());
vi.push_back(rand());
vi.push_back(rand());
vi.push_back(rand());
vi.push_back(rand());
vi.push_back(rand());
vi.push_back(rand());
vi.push_back(rand());
vi.push_back(rand());
vi.push_back(rand());
vi.push_back(rand());
di.assign(vi.begin(), vi.end());
kimi_boost::quicksort(vi.begin(), vi.end());
copy(vi.begin(), vi.end(), ostream_iterator<unsigned>(cout," "));
cout<<endl;
kimi_boost::quicksort(di.begin(), di.end());
copy(di.begin(), di.end(), ostream_iterator<unsigned>(cout," "));
}
Output
41 5705 6334 11478 15724 18467 19169 24464 26962 28145 26500 29358
41 5705 6334 11478 15724 18467 19169 24464 26962 28145 26500 29358
分享到:
相关推荐
C语言编写的泛型快速排序算法,快速排序使用的是泛型编写,通过自己编写比较回调函数来进行调用,模仿一个API底层函数的写法。
主要介绍了Java中使用泛型实现快速排序算法的方法,快速排序的平均时间复杂度为(nlog n),文中的方法立足于基础而并没有考虑优化处理,需要的朋友可以参考下
C#语言使用泛型进行快速排序算法,本程序采用泛型类的排序方法,
使用泛型的对象排序工具类(使用算法:快速排序),适合初学者学习快速排序的基本原理和实现。
各种常用的排序算法,c++泛型实现,对于学习排序算法以及c++泛型编程都是很好的材料
快速排序 随机化快速排序 双路快速排序 三路快速排序 堆和堆排序 堆的基本存储 ShiftUp ShiftDown 基础堆排序和Heapify 优化的堆排序 索引堆(IndexHeap) 索引堆的优化 二分搜索树 二分查找法(Binary Search) 二分...
采用四种排序算法——直接插入排序、直接选择排序、冒泡排序和快速排序,四种排序并发运行,因而在排序数据量较大的情况下可以直观体现四种排序算法之间的性能差异; 3. 排序元素输入有三种方式:1)手动输入;2)...
支持任意类型数据的排序,采用5中排序算法冒泡排序,选择,插入,快速,堆排序。
1、插入排序(InsertSort) 2、冒泡排序(BubbleSort) ...4、快速排序(QuickSort) 5、希尔排序(ShellSort) 6、计数排序(CountSort) 7、堆排序(HeapSort) 8、归并排序(MergeSort) 9、基数排序(RadixSort)
Java常用排序算法源码 稳定:冒泡排序、插入排序、归并排序和基数排序;不稳定:选择排序、快速排序、希尔排序、堆排序
java排序算法包 易于扩展排序要求,泛型实现,可以对任意对象排序,前提是定义了自己的比较器
仿制药Go泛型的快速实验algebra ,浮点型,复数型和有理数的通用平方根函数。 concur ,各种并发实用程序。 future ,并发缓存(“未来缓存”)。 mapreduce ,并行Map,Reduce和ForEach实用程序maps ,具有基于...
Ada 2012泛型套件可简化多核系统的迭代和递归并行性,并为单核和多核系统提供更安全的递归。... 还包括石蜡,石蜡是一组有用的泛型,用于并行快速排序,快速傅立叶变换,函数集成,前缀和和Red-Black树
同样对string等简单类型List排序均如此,如果我们要排的对象复杂了怎么办,我们知道List<T> sort()最后是用快速排序实现,快速排序也好,什么排序都需要知道list中item之间的比较结果,如果是简单的int类型,直接...
排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单排序算法的下界7.4 希尔排序7.5 堆排序7.6 归并排序7.7 快速排序7.7.1 选取枢纽元7.7.2 分割策略7.7.3 小数组7.7.4 实际的快速排序例程...
经过优化的JSON for Go是一种高性能解析器,具有多种其他JSON工具。 OjG for Go的JSON优化是一种高性能的解析器...具有排序选项的快速JSON编写器(速度提高了1.6倍)。 使用推送和弹出方法的简单数据构建器。 对象编码
7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法 7.8 排序算法的一般下界 7.9 桶式排序 7.10 外部排序 7.10.1 为什么需要一些新的算法 7.10.2 外部...
7.7.3 小数组 7.7.4 实际的快速排序例程 7.7.5 快速排序的分析 7.7.6 选择问题的线性期望时间算法 7.8 排序算法的一般下界 7.9 桶式排序 7.10 外部排序 7.10.1 为什么需要一些新的算法 7.10.2 外部...
您可以选择许多排序例程,包括: Timsort(稳定) 快速排序合并排序(稳定) 就地归并排序(不稳定) Shellsort 二进制插入排序堆排序选择排序(实际上仅是为了进行比较) 圣杯排序(稳定) 基于 。 感谢Andrey ...