『壹』 基於比較的排序演算法
基於比較的排序演算法，應該是最符合人們直覺的方法。在各種演算法的技術書上，已經證明了基於比較的排序演算法的時間最優復雜度為O(nlogn)。
下面是幾種常見的基於比較的排序演算法：
1. 選擇排序：這應該是最直觀的排序方法。在排序n個元素時，第一次遍歷，找到最小的元素，將其與第一個元素互換；第二次遍歷，找到次小的元素，將其與第二個元素交換；直至剩下最後一個元素。
2. 冒泡排序：這應該是我們學到的第一種排序演算法。基本思想就是，通過依次比較相鄰的兩個元素，如後值比前值小，則交換這兩個值，小值被交換到前面，大值被交換到後面。這樣一次遍歷後，最大值被放到最後。而小值被交換到n-1前。然後再次遍歷前n-1，n-2，直至最後2個元素。整個兒過程，小值隨著不斷的遍歷過程，逐漸被交換到前面，很像氣泡逐漸從水底逐漸冒出。所以被稱為冒泡演算法。
3. 插入排序：這個演算法的思想很直觀。按照《演算法導論》中的解釋，這個演算法可以參照我們平時打撲克的情形。當抓取一張牌的時候，按順序比較手牌，將其插入到恰當的位置。這樣保證了手中所有的牌依然有序。當已排序的值數量較多時，由於已經保證了有序，那麼在確定新值插入位置的時候，可以通過二分查找的方法來去確定插入位置。
4. 希爾排序：在冒泡演算法中，所以小值只能以步長為1的速度向前面移動。希爾排序在步長上作了優化，開始以一個較大的m步長進行分組，每組進行插入排序，這樣就實現了步長為m的移動。然後逐漸縮小步長m直至1。所以根本思想是盡可能的將元素移動較遠的位置代替移動一位。
5.歸並排序：該思想利用的是解決問題的一個常用思想，divide-and-conquer，即分而治之的思想。將n個元素每次2分，變為兩個n/2個元素組，直至1個元素——1個元素，自然是排好序了。然後，再兩兩合並元素組，最終合並為一個元素組。歸並演算法，因為需要歸並，所以必然需要一個額外的n空間來實現歸並。
6.快速排序：同樣是分而治之的思想，將原始數據分為2組。但是與歸並演算法直接將原始數據分為兩部分不同的是，快排選擇一個中值，新的兩個子組，一個子組所有的元素都小於中值，另外一個子組所有的元素都大於等於中值，直至元素個數為1。當元素個數為1時，實際上快排已經完成了排序。這點與歸並排序也不同，快排在子組完成以後，無需額外的操作。很明顯，快排的效率依賴於中值的選擇。如果中值可以將數據分為兩個數量相等的子組，那麼效率則為最高的。快排無需額外的存儲空間，可以in-place進行排序。
7.堆排序：該思想是將原始元素視為一個平衡二叉樹。然後要求父節點必須大於子節點的規則，調整該平衡二叉樹。由於是平衡二叉樹，所以數據被完美的等分。這樣根節點即為最大值。這時，堆排序完成了最大值的選擇。為排序，則將根節點與最後一個子節點交換。此時，樹的規則被破壞，需要從根節點逐級verify規則。
『貳』 幾種經典排序演算法優劣比較的C++程序實現
一、低級排序演算法
1.選擇排序
（1）排序過程
給定一個數值集合，循環遍歷集合，每次遍歷從集合中選擇出最小或最大的放入集合的開頭或結尾的位置，下次循環從剩餘的元素集合中遍歷找出最小的並如上操作，最後直至所有原集合元素都遍歷完畢，排序結束。
（2）實現代碼
//選擇排序法
template
void Sort：：SelectSort（T* array， int size）
{
int minIndex；
for（int i = 0； i < size； i++）
{
minIndex = i；
for（int j = i + 1； j < size； j++）
{
if（array[minIndex] > array[j]）
{
minIndex = j；
}
}
if（minIndex ！= i）
{
Swap（array， i， minIndex）；
}
}
}
（3）分析總結
選擇排序時間復雜度比較高，達到了O（n^2），每次選擇都要遍歷一遍無序區間。選擇排序對一類重要的元素序列具有較好的效率，就是元素規模很大，而排序碼卻比較小的序列。另外要說明的是選擇排序是一種不穩定的排序方法。
2.冒泡排序
（1）排序過程
冒泡排序的過程形如其名，就是依次比較相鄰兩個元素，優先順序高（或大或小）的元素向後移動，直至到達序列末尾，無序區間就會相應地縮小。下一次再從無序區間進行冒泡操作，依此循環直至無序區間為1，排序結束。
（2）實現代碼
//冒泡排序法
template
void Sort：：BubbleSort（T* array， int size）
{
for（int i = 0； i < size； i++）
{
for（int j = 1； j < size - i； j++）
{
if（array[j] < array[j - 1]）
{
Swap（array， j， j - 1）；
}
}
}
}
（3）分析總結
冒泡排序的時間復雜度也比較高，達到O（n^2），每次遍歷無序區間都將優先順序高的元素移動到無序區間的末尾。冒泡排序是一種穩定的排序方式。
二、高級排序演算法
（1）排序過程
歸並排序的原理比較簡單，也是基於分治思想的。它將待排序的元素序列分成兩個長度相等的子序列，然後為每一個子序列排序，然後再將它們合並成一個序列。
（2）實現代碼
//歸並排序
template
void Sort：：MergeSort（T* array， int left， int right）
{
if（left < right）
{
int mid = （left + right） / 2；
MergeSort（array， left， mid）；
MergeSort（array， mid + 1， right）；
Merge（array， left， mid， right）；
}
}
//合並兩個已排好序的子鏈
template
void Sort：：Merge（T* array， int left， int mid， int right）
{
T* temp = new T[right - left + 1]；
int i = left， j = mid + 1， m = 0；
while（i <= mid && j <= right）
{
if（array[i] < array[j]）
{
temp[m++] = array[i++]；
}
else
{
temp[m++] = array[j++]；
}
}
while（i <= mid）
{
temp[m++] = array[i++]；
}
while（j <= right）
{
temp[m++] = array[j++]；
}
for（int n = left， m = 0； n <= right； n++， m++）
{
array[n] = temp[m]；
}
delete temp；
}
（3）分析總結
歸並排序最好、最差和平均時間復雜度都是O（nlogn），是一種穩定的排序演算法。