排序可以说是百花齐放，据算法宗师高德纳爷爷的《TAOCP》第三卷所记载的至少就有20多种。从大的方面来说，排序可以分成内排序和外排序——内排序是外排序的基础。我们常用的内排序又可以粗略分成下面的类型：
插入排序
交换排序
堆排序
归并排序
别看排序有那么多种类型，但它们都离不开这样的核心思想：
|有序序列区|无序序列区|
一个待排序列总是被不断从无序序列转变为有序序列。
从效率来说，目前已知最快的排序方法是“快速排序（QuickSort）”。牛B吧？呵呵，连名字都起得那么牛。（别的排序方法的名称要么是表示出它的本质（例如“插入排序”），要么是以其发明者命名的（例如“ShellSort”），只有QuickSort是直言不讳地用“Quick”来命名，这或许就是在排序上的最高荣誉吧！）
但要注意的是，没有一种排序方法的效率是在任何情况下都能独占鳌头的，具体采取哪种方法要根据实际情况而定（有的人喜欢用快速排序通吃各种情况，这有点像是赌博了，呵呵）。我举个例子，假设要在10000个随机的数据中找出最大的10个数，那么采用堆排序应该是最合适的，因为：第一，经验指出堆排序是一个非常稳定的算法，在各种环境中其效率变化不会太大；第二，堆排序的特性决定了只要构建一棵根节点为最大数的优先队列树，然后取其前10个根节点就行了。
该说的基本上就说完了，我不想重复敲入书上的话，各种排序算法的具体解释请参阅教科书，下面给出代码。
各种排序的代码实现如下：
/////////////////////////////////////////////////////////////////////////////// // // FileName : sort.h // Version : 0.10 // Author : Luo Cong // Date : 2005-1-23 16:49:42 // Comment : // /////////////////////////////////////////////////////////////////////////////// #ifndef __SORT_H__ #define __SORT_H__ template<typename T> class CSort { private: // the following three functions are for HeapSort(): int LeftChild(const int i); void PercDown(T x[], int i, const int n); void Swap(T *l, T *r); // the following two functions are for MergeSort(): void MSort(T x[], T tmp[], int left, int right); void Merge(T x[], T tmp[], int lpos, int rpos, int rightend); // for QuickSort(): T Median3(T x[], const int left, const int right); public: void InsertSort(T x[], const int n); void ShellSort(T x[], const int n); void HeapSort(T x[], const int n); void MergeSort(T x[], int n); void QuickSort(T x[], int left, int right); }; template<typename T> inline void CSort<T>::InsertSort(T x[], const int n) { int i; int j; T tmp; for (i = 0; i < n; ++i) { tmp = x[i]; // copy it first for (j = i; j > 0; --j) // unsorted region; (0 ~ (i - 1)) is sorted if (x[j - 1] > tmp) x[j] = x[j - 1];// move back elements to empty a right position else break; // we got it! x[j] is the right position x[j] = tmp; // place it to the right position } } template<typename T> inline void CSort<T>::ShellSort(T x[], const int n) { int i; int j; int nIncrement; T tmp; for (nIncrement = n / 2; nIncrement > 0; nIncrement /= 2) { for (i = nIncrement; i < n; ++i) { tmp = x[i]; for (j = i; j >= nIncrement; j -= nIncrement) { if (tmp < x[j - nIncrement]) x[j] = x[j - nIncrement]; else break; } x[j] = tmp; } } } template<typename T> inline int CSort<T>::LeftChild(const int i) { return (2 * i + 1); } template<typename T> inline void CSort<T>::PercDown(T x[], int i, const int n) { int nChild; T tmp; for (tmp = x[i]; LeftChild(i) < n; i = nChild) { nChild = LeftChild(i); if ((nChild != n - 1) && (x[nChild + 1] > x[nChild])) ++nChild; if (tmp < x[nChild]) x[i] = x[nChild]; else break; } x[i] = tmp; } template<typename T> inline void CSort<T>::Swap(T *l, T *r) { T tmp = *l; *l = *r; *r = tmp; } template<typename T> inline void CSort<T>::HeapSort(T x[], const int n) { int i; for (i = n / 2; i >= 0; --i) // build heap PercDown(x, i, n); for (i = n - 1; i > 0; --i) { Swap(&x[0], &x[i]); // delete max PercDown(x, 0, i); } } template<typename T> inline void CSort<T>::Merge(T x[], T tmp[], int lpos, int rpos, int rightend) { int i; int leftend; int numelements; int tmppos; leftend = rpos - 1; tmppos = lpos; numelements = rightend - lpos + 1; // main loop while ((lpos <= leftend) && (rpos <= rightend)) { if (x[lpos] <= x[rpos]) tmp[tmppos++] = x[lpos++]; else tmp[tmppos++] = x[rpos++]; } while (lpos <= leftend) // copy rest of first half tmp[tmppos++] = x[lpos++]; while (rpos <= rightend) // copy rest of second half tmp[tmppos++] = x[rpos++]; // copy tmp back for (i = 0; i < numelements; ++i, --rightend) x[rightend] = tmp[rightend]; } template<typename T> inline void CSort<T>::MSort(T x[], T tmp[], int left, int right) { int center; if (left < right) { center = (left + right) / 2; MSort(x, tmp, left, center); MSort(x, tmp, center + 1, right); Merge(x, tmp, left, center + 1, right); } } template<typename T> inline void CSort<T>::MergeSort(T x[], int n) { T *tmp; tmp = new (T[n * sizeof(T)]); if (NULL != tmp) { MSort(x, tmp, 0, n - 1); delete tmp; } } template<typename T> inline T CSort<T>::Median3(T x[], const int left, const int right) { int center = (left + right) / 2; if (x[left] > x[center]) Swap(&x[left], &x[center]); if (x[left] > x[right]) Swap(&x[left], &x[right]); if (x[center] > x[right]) Swap(&x[center], &x[right]); // invariant: x[left] <= x[center] <= x[right] Swap(&x[center], &x[right - 1]); // hide pivot return x[right - 1]; // return pivot } template<typename T> inline void CSort<T>::QuickSort(T x[], int left, int right) { int i; int j; int cutoff = 3; T pivot; if (left + cutoff <= right) { pivot = Median3(x, left, right); i = left; j = right - 1; for (;;) { while (x[++i] < pivot) {} while (x[--j] > pivot) {} if (i < j) Swap(&x[i], &x[j]); else break; } Swap(&x[i], &x[right - 1]); // restore pivot QuickSort(x, left, i - 1); QuickSort(x, i + 1, right); } else // do an insertion sort on the subarray InsertSort(x + left, right - left + 1); } #endif // __SORT_H__
测试代码：
/////////////////////////////////////////////////////////////////////////////// // // FileName : sort.cpp // Version : 0.10 // Author : Luo Cong // Date : 2005-1-23 16:49:39 // Comment : // /////////////////////////////////////////////////////////////////////////////// #include "sort.h" int main() { int x[] = {2, 9, 1, 6, 4, 8, 10, 7, 3, 5}; CSort<int> sort; sort.QuickSort(x, 0, 9); // sort.ShellSort(x, 10); }