1. 现有的泛型排序
我们知道STL支持几种泛型排序，像sort，stable_sort，partial_sort，list::sort，但是它们都有一些限制。
- sort和partial_sort只支持支持随机访问迭代器RandomAccessIterator的序列，像vector，但不支持list。
- list::sort只支持list排序。
- stable_sort支持支持双向迭代器BidirectionalIterator的序列，如vector和list等，但不能支持数组（包括指针寻址的）序列，比如下面的数组a和指针p所能访问的序列。
MyClass * p = new MyClass[100];
网上也有一些文章，写如何支持泛型排序，如这篇，但里面所指的泛型是指待排序序列中元素类型的泛型，而不是指待排序序列的泛型。对于待排序序列，它只支持数组存储形式（T a[]），不支持vector和list等存储形式（如：std::vector
2. 我们的目标
我们希望C++排序算法能支持多种序列类型（当然，序列中的元素类型是任意的），排序函数的原型最好能像下面的声明一样，其中arr为任意类型的序列，size为序列的长度，ascending为升序的标志，降序时设为false。
void Sort(A arr, int size, bool ascending = true);
3. 实现
A arr的声明有点像动态类型语言？是。不过C++不能支持运行时的动态类型推导。我们还是得使用编译期类型推导的template（什么？C++11标准里有自动类型推导？那也许将来我们就不需要这篇文章了）。
我们声明一个排序器的模板基类，如下：
template
class Sorter
{
public:
Sorter(void) {}
virtual ~Sorter(void) {}
virtual void Sort(A arr, int size, bool ascending = true) = 0;
private:
Sorter(Sorter& sorter);
Sorter& operator=(const Sorter& sorter);
};
简单说说此类。Sorter的模板参数A就是序列类型，后面我们将看到它是如何被应用的。之所以声明一个基类，是为了实现策略模式。之所以Sort函数被声明为纯虚函数，目的是为了让各种派生的排序算法类重载它。声明Sorter类的复制构造和赋值操作符而不定义它们，是为了避免Sorter子类对象间无意的复制和赋值（参见《Effective C++》条款06）。在实践中，有时我们会根据不同时间和空间的要求，使用不同排序算法，所以，以上代码是为了支持策略模式而存在的，不需要策略模式，不用声明这个基类。这部分不是本文主要要讨论的内容，我们来看看本文的重点。
下面我们以插入排序为例，说明如何实现泛型的排序器。
template
class InsertionSorter : public Sorter
{
public:
InsertionSorter(void) {}
virtual ~InsertionSorter(void) {}
virtual void Sort(A arr, int size, bool ascending = true)
{
for (int j = 1;j < (int)size;j++)
{
T key = arr[j];
int i = j-1;
while (i >= 0 && (ascending?(arr[i] > key):(key > arr[i])))
{
arr[i+1] = arr[i];
i--;
}
arr[i+1] = key;
}
}
}
这个类又增加了一个模板参数T，这个就是序列中元素的类型，有了T，我们的排序就可以支持任意元素类型（只要T支持“大于”操作“>”和“赋值”操作符“=”）。另一方面，从上面的代码可以看到，序列arr用[]寻址，这样所有支持[]操作符的序列类型，比如：数组、指针数组、std::vector、std::deque，MFC的CArray，它们都已重载了操作符[]，就都能使用这个排序函数来排序。
举几个例子，来展现不同序列类型如何使用这个进行排序（以下MyClass为自定义的一个类，即编译期替换T的类型，读者可以换成任何其它类型，但无论用什么类型，必须支持操作符“>”和“=”）。
为指针数组排序（MyClass *实际上就是A的编译期类型）：
MyClass * pMyClass = new MyClass[100];
// 为pMyClass赋值代码省略
// ...
Sorter
pMyClassSorterPointer->Sort(pMyClass, size);
delete pMyClassSorterPointer;
为std::vector序列排序（std::vector
std::vector
// 为vecMyClass赋值代码省略
// ...
Sorter
pMyClassSorterPointer->Sort(vecMyClass, vecMyClass.size());
delete pMyClassSorterVector;
大家可能会说：std::list没有重载操作符[]，无法使用这个泛型排序。是的，要想用这个泛型排序，序列类型必须支持[]。解决办法是，我们继承list类，并让其重载操作符[]，代码如下：
template
class MyList : public std::list
{
public:
T& operator[](size_type _Pos)
{
int i = 0;
iterator iter = begin();
while (iter != end())
{
if (_Pos == i) break;
iter++;
i++;
}
return *iter;
}
const T& operator[](size_type _Pos) const
{
int i = 0;
const_iterator iter = begin();
while (iter != end())
{
if (_Pos == i) break;
iter++;
i++;
}
return *iter;
}
};
可能又有人会说：你这里用循环遍历，时间复杂度又会增加一级。确实如此，效率上会下降，也许我们需要一些办法来提高效率，比如：对于在list后半段的元素，我们可以逆向遍历（用reverse_iterator和const_reverse_iterator遍历）。毕竟，完成功能是第一步，提高效率是第二步。
这样，MyList的排序代码如下（MyList
MyList
// 为listMyClass赋值代码省略
// ...
Sorter
pMyClassSorterList->Sort(listMyClass, listMyClass.size());
delete pMyClassSorterList;
4. 局限性
到这里，已经确定能支持的序列类型包括：数组、指针数组、std::vector、std::deque、std::list。我没有试MFC的CArray，理论上应该也可以支持。std::set、std::map、std::priority_queue和类似的类型不需要支持，因为它们在插入元素时已自动排序。std::queue、std::stack或类似的类型没有支持，虽然理论上也可以遍历它们，也可以重载[]以实现随机访问，但是这些结构，如果排序了，也就失去了它们原有存在的意义。
5. 其它排序算法的泛型实现
除了插入排序，这里再提供3个其它排序算法的泛型实现。
冒泡排序：
冒泡排序template 合并排序：
堆排序：
以上部分排序算法参考《算法导论（原书第二版）》。
最新评论