一般講排序算法的文章，為了方便說明算法本身，待排序元素的類型一般使用整型。還有些文章講泛型排序，待排序元素可以是任意類型，但對於待排序序列，卻一般只支持某一種存儲形式，比如定長數組，比如std::vector，但不能同時支持它們。那麼我們有沒有辦法使用泛型技術即支持任意元素類型又支持大多數常用的序列類型進行排序呢？
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所能訪問的序列。
int a[100];
MyClass * p = new MyClass[100];
網上也有一些文章，寫如何支持泛型排序，如這篇，但裡面所指的泛型是指待排序序列中元素類型的泛型，而不是指待排序序列的泛型。對於待排序序列，它只支持數組存儲形式（T a[]），不支持vector和list等存儲形式（如：std::vector<T>& a）。
2. 我們的目標
我們希望C++排序算法能支持多種序列類型（當然，序列中的元素類型是任意的），排序函數的原型最好能像下面的聲明一樣，其中arr為任意類型的序列，size為序列的長度，ascending為升序的標志，降序時設為false。
void Sort(A arr, int size, bool ascending = true);
3. 實現
A arr的聲明有點像動態類型語言？是。不過C++不能支持運行時的動態類型推導。我們還是得使用編譯期類型推導的template（什麼？C++11標准裡有自動類型推導？那也許將來我們就不需要這篇文章了）。
我們聲明一個排序器的模板基類，如下：
template <typename A>
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 <typename T, typename A>
class InsertionSorter : public Sorter<A>
{
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<MyClass *> * pMyClassSorterPointer = new InsertionSorter<MyClass, MyClass *>;
pMyClassSorterPointer->Sort(pMyClass, size);
delete pMyClassSorterPointer;
為std::vector序列排序（std::vector<MyClass>&實際上就是A的編譯期類型）：
std::vector<MyClass> vecMyClass;
// 為vecMyClass賦值代碼省略
// ...
Sorter<std::vector<MyClass>&> * pMyClassSorterVector = new InsertionSorter<MyClass, std::vector<MyClass>&>;
pMyClassSorterPointer->Sort(vecMyClass, vecMyClass.size());
delete pMyClassSorterVector;
大家可能會說：std::list沒有重載操作符[]，無法使用這個泛型排序。是的，要想用這個泛型排序，序列類型必須支持[]。解決辦法是，我們繼承list類，並讓其重載操作符[]，代碼如下：
template <typename T>
class MyList : public std::list<T>
{
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++;
}
&
