排序算法經過了很長時間的演變，產生了很多種不同的方法。對于初學者來說，對它們進行整理便于理解記憶顯得很重要。每種算法都有它特定的使用場合，很難通用。因此，我們很有必要對所有常見的排序算法進行歸納。
我不喜歡死記硬背，我更偏向于弄清來龍去脈，理解性地記憶。比如下面這張時間復雜度圖，我們將圍繞這張圖來分析。
上面的這張圖來自一個PPT。它概括了數據結構中的所有常見的排序算法，給大家總結如下。
區分穩定與不穩定：快速、希爾、堆、選擇不穩定，其他排序算法均穩定。
平均時間復雜度：冒泡，選擇，插入是O(n2)，其他均是O(n*log2n)
最壞時間復雜度：冒泡，選擇，插入，快排是O(n2)，其他是O(n*log2n)
平均和最壞時間復雜度：只有O(n2)和O(n*log2n)兩種，冒泡，選擇，插入是O(n2)，最壞情況下加一個快排，其他均是O(nlog2n)。
一、直接插入排序(插入排序)。
1、算法的偽代碼(這樣便于理解)：
|
1
2
3
4
5
6
7
8
|
INSERTION-SORT (A, n) A[1 . . n] for j ←2 to n do key ← A[ j] i ← j – 1 while i > 0 and A[i] > key do A[i+1] ← A[i] i ← i – 1 A[i+1] = key |
2、思想：如下圖所示，每次選擇一個元素K插入到之前已排好序的部分A[1…i]中，插入過程中K依次由后向前與A[1…i]中的元素進行比較。若發現發現A[x]>=K,則將K插入到A[x]的后面，插入前需要移動元素。
3、算法時間復雜度。
最好的情況下：正序有序(從小到大)，這樣只需要比較n次，不需要移動。因此時間復雜度為O(n)
最壞的情況下：逆序有序,這樣每一個元素就需要比較n次，共有n個元素，因此實際復雜度為O(n2)
平均情況下：O(n2)
4、穩定性。
理解性記憶比死記硬背要好。因此，我們來分析下。穩定性，就是有兩個相同的元素，排序先后的相對位置是否變化，主要用在排序時有多個排序規則的情況下。在插入排序中，K1是已排序部分中的元素，當K2和K1比較時，直接插到K1的后面(沒有必要插到K1的前面，這樣做還需要移動！！)，因此，插入排序是穩定的。
二、希爾排序(插入排序)
1、思想：希爾排序也是一種插入排序方法,實際上是一種分組插入方法。先取定一個小于n的整數d1作為第一個增量,把表的全部記錄分成d1個組,所有距離為d1的倍數的記錄放在同一個組中,在各組內進行直接插入排序；然后,取第二個增量d2(＜d1),重復上述的分組和排序,直至所取的增量dt=1
例如：將 n 個記錄分成 d 個子序列：
{ R[0]， R[d]， R[2d]，…， R[kd] }
{ R[1]， R[1+d]， R[1+2d]，…，R[1+kd] }
…
{ R[d-1]，R[2d-1]，R[3d-1]，…，R[(k+1)d-1] }
說明：d=5 時，先從A[d]開始向前插入，判斷A[d-d]，然后A[d+1]與A[(d+1)-d]比較，如此類推，這一回合后將原序列分為d個組。<由后向前>
2、時間復雜度。
最好情況：由于希爾排序的好壞和步長d的選擇有很多關系，因此，目前還沒有得出最好的步長如何選擇(現在有些比較好的選擇了，但不確定是否是最好的)。所以，不知道最好的情況下的算法時間復雜度。
最壞情況下：O(N*logN)，最壞的情況下和平均情況下差不多。
平均情況下：O(N*logN)
3、穩定性。
由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以shell排序是不穩定的。(有個猜測，方便記憶：一般來說，若存在不相鄰元素間交換，則很可能是不穩定的排序。)
三、冒泡排序(交換排序)
1、基本思想：通過無序區中相鄰記錄關鍵字間的比較和位置的交換,使關鍵字最小的記錄如氣泡一般逐漸往上“漂浮”直至“水面”。
2、時間復雜度
最好情況下：正序有序，則只需要比較n次。故，為O(n)
最壞情況下: 逆序有序，則需要比較(n-1)+(n-2)+……+1，故，為O(N*N)
3、穩定性
排序過程中只交換相鄰兩個元素的位置。因此，當兩個數相等時，是沒必要交換兩個數的位置的。所以，它們的相對位置并沒有改變，冒泡排序算法是穩定的！
四、快速排序(交換排序)
1、思想：它是由冒泡排序改進而來的。在待排序的n個記錄中任取一個記錄(通常取第一個記錄),把該記錄放入適當位置后,數據序列被此記錄劃分成兩部分。所有關鍵字比該記錄關鍵字小的記錄放置在前一部分,所有比它大的記錄放置在后一部分,并把該記錄排在這兩部分的中間(稱為該記錄歸位),這個過程稱作一趟快速排序。
2、算法復雜度
最好的情況下：因為每次都將序列分為兩個部分(一般二分都復雜度都和logN相關)，故為 O(N*logN)
最壞的情況下：基本有序時，退化為冒泡排序，幾乎要比較N*N次，故為O(N*N)
3、穩定性
由于每次都需要和中軸元素交換，因此原來的順序就可能被打亂。如序列為 5 3 3 4 3 8 9 10 11會將3的順序打亂。所以說，快速排序是不穩定的！
五、直接選擇排序(選擇排序)
1、思想：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小元素，然后放到排序序列末尾。以此類推，直到所有元素均排序完畢。具體做法是：選擇最小的元素與未排序部分的首部交換，使得序列的前面為有序。
2、時間復雜度。
最好情況下：交換0次，但是每次都要找到最小的元素，因此大約必須遍歷N*N次，因此為O(N*N)。減少了交換次數！
最壞情況下，平均情況下：O(N*N)
3、穩定性
由于每次都是選取未排序序列A中的最小元素x與A中的第一個元素交換，因此跨距離了，很可能破壞了元素間的相對位置，因此選擇排序是不穩定的！
六、堆排序
1、思想：利用完全二叉樹中雙親節點和孩子節點之間的內在關系，在當前無序區中選擇關鍵字最大(或者最小)的記錄。也就是說，以最小堆為例，根節點為最小元素，較大的節點偏向于分布在堆底附近。
2、算法復雜度
最壞情況下，接近于最差情況下：O(N*logN)，因此它是一種效果不錯的排序算法。
3、穩定性
堆排序需要不斷地調整堆，因此它是一種不穩定的排序！
七、歸并排序
1、思想：多次將兩個或兩個以上的有序表合并成一個新的有序表。
2、算法時間復雜度
最好的情況下：一趟歸并需要n次，總共需要logN次，因此為O(N*logN)
最壞的情況下，接近于平均情況下，為O(N*logN)
說明：對長度為n的文件，需進行logN 趟二路歸并，每趟歸并的時間為O(n)，故其時間復雜度無論是在最好情況下還是在最壞情況下均是O(nlgn)。
3、穩定性
歸并排序最大的特色就是它是一種穩定的排序算法。歸并過程中是不會改變元素的相對位置的。
4、缺點是，它需要O(n)的額外空間。但是很適合于多鏈表排序。
5、C++實現排序算法代碼總結如下：
#include<iostream>
#include<vector>
#include<limits>
using namespace std;
//插入排序，相當于打牌,相當于把一個值插入到已經排序好的一個數組中，
//先把待排序的值放到一個臨時變量里面，讓排好序的數字從大到小去與這個值做比較，若大于就把位置往后挪一個，
//騰出一個空位置出來，找到第一個小于他的位置就在該位置后面插入此值，因為是原地排序，所以待排序的值也在數組中，
//默認數組中第一個值是已經排好序的
void InsertSort(vector<int> &data)
{
if(!data.empty())
return;
int size = data.size();
for(int j = 1;j < size; ++j)//默認data[0]是排好序的
{
int temp = data[j];
int index = j-1;
while(index >= 0 && data[index] > temp)
{
data[index+1] = data[index];
index--;
}
data[index+1] = temp;
}
}
//歸并排序，先分治，在歸并
//假定sub1和sub2都是排好序的，result里面包含sub1和sub2中的所有元素
void Merge(vector<int> &result,vector<int> &sub1,vector<int> &sub2)
{
sub1.push_back(INT_MAX);
sub2.push_back(INT_MAX);
int number1 = sub1.size();
int number2 = sub2.size();
int sub1_i = 0,sub2_i = 0;
for(auto it = result.begin();it != result.end();++it)
{
if(sub1[sub1_i] <= sub2[sub2_i])
{
*it = sub1[sub1_i];
++sub1_i;
}
else
{
*it = sub2[sub2_i];
++sub2_i;
}
}
}
void MergeSort(vector<int>& coll)//合并排序，先分治法，再合并
{
unsigned int number=coll.size();
if(number<=1)
return;
unsigned int mid=number/2;
vector<int> sub1;
vector<int> sub2;
for(unsigned int i=0;i<mid;++i)
{
sub1.push_back(coll[i]);
}
for(unsigned int j=0;j<number-mid;++j)
{
sub2.push_back(coll[mid+j]);
}
MergeSort(sub1);
MergeSort(sub2);
Merge(coll,sub1,sub2);
}
//冒泡排序法,每次總是拿當前循環的值與還沒排好序的值進行比較交換，把這一輪
//中最小的值放在當前循環的下標數組中，每循環一次，就排好一個較小的值，這樣循環n次，就排好序了
void BubleSort(vector<int> &data)
{
int size = data.size();
bool sort_flag = false;
for(int i = 0;i < size;++i)
{
if(sort_flag == true) //冒泡改進版，當sort_flag = false;在某次循環中沒有執行時，說明剩下的元素都排好序了
return;
sort_flag = true;
for(int j = i;j < size;++j)//經過一次循環，將最小的值放在i處
{
if(data[i] > data[j])
{
swap(data[i],data[j]);
sort_flag = false;
}
}
}
}
//----------------------------------以下是不穩定排序算法-------------------------
//快速排序
int Partition(int data[],int length,int start,int end)
{
if(data == NULL || length <= 0 || start < 0 || end >= length)
throw new exception(" Invalid Parameters");
int index = rand()%(start-end+1)+start;
swap(data[index],data[end]);
int left = start-1;//小值放在左邊，大值放在右邊，循環時，if條件不成立時說明發現小值，否則一直值大值
for(index = start;index < end;++index)
{
if(data[index] < data[end])
{
++left;
if(left != index)
swap(data[left],data[index]);
}
}
++left;
swap(data[left],data[end]);
return left;
}
void QuickSort(int data[],int length,int start,int end)
{
if(start == end)
return;
int index = Partition(data,length,start,end);
if(index > start)
QuickSort(data,length,start,index-1);
if(index < end)
QuickSort(data,length,index+1,end);
}
//堆排序 1.堆維護 2、建堆 3、堆排序
void MaxHeapIFY(vector<int> &data,int local,int length)//堆維護,local為要維護的元素的下標,length為數組的長度
{
if(!data.empty())
return;
int left = local*2+1;//因為是從0開始計數，所以計算公式有2i變為此公式
int right = local*2;
int largest = local;
if(left < length && data[left] > data[local])
{
largest = left;
}
if(right < length && data[right] > data[local])
{
largest = right;
}
if(largest != local)
{
swap(data[largest],data[local]);
MaxHeapIFY(data,largest,length);//largest為退出遞歸的條件，當他大于length時，即終止遞歸
}
}
//建堆,是從第一個非葉子節點(length/2-1)進行堆維護
void BuileMaxHeap(vector<int> &data ,int length)
{
int root = length/2-1;
for(int i = root;i >= 0;--i)
{
MaxHeapIFY(data,i,length);
}
}
//將第一個元素的值和最后一個元素相互交換，然后舍去最后一個元素，用剩下的n-1個元素進行堆維護，逐個遞減到最后一個元素
void HeapSort(vector<int> &data)
{
if(!data.empty())
return;
BuileMaxHeap(data,data.size());
int length = data.size();
for(int i = length-1;i >= 0;--i)
{
swap(data[0],data[i]);
--length;
MaxHeapIFY(data,0,length);
}
}
//選擇排序,每次選擇一個本循環中最小的值,與冒泡排序差不多，只不過少了交換的次數，是直接進行排序的
void SelectionSort(vector<int> &data)
{
int size = data.size();
--size;
for(int i = 0;i < size-1;++i)
{
int min = i;
for(int j = i+1;j < size;++j)
{
if(data[min] > data[j])
min = j;
}
swap(data[min],data[i]);
}
}
//希爾排序，思想就是插入排序，把待排序的數組分成d組(下標每間隔為d的進行元素為一組)，然后每組進行插入排序，
//接著遞減d的值，然后插入排序，直到d=1最后的排序，這樣比插入排序來說，減少了排序次數，相當于跳著進行插入排序，最后跳度為1
void ShellSort(vector<int> &data)
{
int size = data.size();
size;
int separate = size / 2;
while(separate > 0)
{
for(int i = separate;i < size;++i)
{
int temp = data[i];
int j = i - separate;
while(j >=0 && data[j] > temp)
{
data[j+separate] = data[j];
j = j-separate;
}
data[j+separate] = temp;
}
separate /= 2;//遞減增量
}
}
總結： 每種算法都要它適用的條件，本文也僅僅是回顧了下基礎。有需要的可以參考。
