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语言中,由于没有内置的泛型机制,实现泛型快速排序需要借助于指针和回调函数。回调函数的作用是在排序过程中提供元素间的比较规则,使得快速排序可以应用于不同类型的数据,如整数、浮点数、自定义结构体等。...
在Java中,我们可以利用泛型来实现快速排序,这样就可以让排序功能适用于多种数据类型。泛型是Java中的一项重要特性,它允许在编译时检查类型安全,并且可以与任何引用类型一起工作。在快速排序的泛型实现中,我们...
在编程领域,排序算法是数据处理中的基础,它在各种应用中都发挥着重要作用。...而选择排序虽然在效率上不如快速排序或归并排序,但其简单的实现和固定的比较次数在某些特定场景下仍然具有一定的价值。
快速排序是一种高效的排序算法,由英国...总的来说,C++的模板类提供了强大的泛型编程能力,使得我们可以编写出高效且通用的代码,如快速排序算法。这种实现方式降低了代码的重复性,提高了代码的可复用性和维护性。
在Java中,我们可以使用泛型和递归来实现快速排序。首先,定义一个`quickSort()`方法,接受一个可比较的数组和两个整数作为下标,表示待排序的子数组。然后,选择一个基准元素,使用`Arrays.sort()`方法的双指针...
- **快速排序(Quick Sort)**:快速排序是一种高效的排序算法,采用分治策略。它选取一个“基准”元素,将数组分为比基准小和大的两部分,然后对这两部分分别进行快速排序,直到整个数组有序。 - **归并排序...
在C#编程语言中,我们可以利用泛型来实现快速排序,使得该算法可以应用于各种数据类型的数组或集合。 泛型是.NET框架中的一个重要特性,它允许我们在不指定具体类型的情况下定义类、接口和方法,从而提高了代码的...
使用泛型的对象排序工具类(使用算法:快速排序),适合初学者学习快速排序的基本原理和实现。
选择排序、插入排序和快速排序都是经典的排序算法,各有其特点和适用场景。接下来,我们将详细探讨这三个排序算法。 1. **选择排序(Selection Sort)** 选择排序是一种简单直观的排序算法。它的基本思想是在未...
在主函数中,作者使用了 clock 函数来计算快速排序的时间复杂度,并将其与非递归快速排序的时间复杂度进行比较。结果表明,非递归快速排序的时间复杂度要比递归快速排序的时间复杂度低很多。 结论 排序算法是...
根据给定的信息,我们可以深入探讨基于模板的快速排序这一主题,并从中提炼出多个重要的知识点。 ### 1. 快速排序的基本概念 快速排序是一种高效的排序算法,采用分治法策略来把一个序列分为较小和较大的两个子...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的核心思想是分治策略,通过一趟排序(分区操作)将待排序的序列分成两个子序列,使得一个子序列的所有元素都小于另一个子序列的所有...
它提供了快速的索引访问,但插入和删除操作相对较慢,因为需要移动后续元素。 2. **LinkedList**: 它通过节点链接实现,插入和删除速度快,但是随机访问速度慢。LinkedList实现了List、Deque和Iterator接口,可以...
本篇文章将深入探讨TIA博途SCL语言中的快速排序算法,以及如何将其封装为一个全局功能块(FC)库文件,以便在项目中重复使用,并支持升序或降序排列。 快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. ...
字典集合提供键值对的存储,通过键快速访问对应的值。`Dictionary, TValue>`类实现了`IDictionary, TValue>`接口。使用`Add`方法添加键值对,`TryGetValue`方法尝试获取值,`Remove`方法移除键值对。 5. **泛型...
总结来说,这个项目重点在于理解和实现快速排序算法,通过操作符重载提供灵活的比较方式,利用模板实现泛型排序,确保代码能在不同的数据类型上工作,并且所有这些都在Visual Studio 2005环境下进行了测试和调试。...
比如,`std::sort`函数就是一个泛型算法,可以对任何可以比较的类型进行排序,无论是整数、浮点数还是自定义的类对象。 在实际开发中,掌握STL和泛型编程能够极大地提高代码质量和效率。通过利用STL提供的工具,...