最近在忙著准備找工作，對於碼農來說，找工作之前必備的就是各種的排序算法，其中包括算法實現、復雜度分析。於是我也開始研究各種排序算法，但是看完幾遍之後發現，其原理並不復雜，於是就在思考，這些算法這麼重要，那麼它們在實際解決問題時如何來使用呢？這篇文章我就個人的理解，盡量形象、簡單的描述各種基本排序算法的原理，並對其復雜度進行了相應的分析，最後說明其在實際使用中的應用。我希望我的這篇文章盡量的通俗形象，讓我們展開想象的空間吧！
一、算法原理分析：
1、冒泡排序：
首先從它的名字上來理解它的原理，假設一個湖底從左到右並排了10(n)個泡泡，我們在湖底從左向右游動，每次只比較相鄰的兩個泡泡，如果左邊的比右邊的小則交換其位置，這樣游玩了一趟之後，即比較了9（n-1）次，最大的那個就得到了，這時我們將這個泡泡冒出水面，以此類推，我們需要這樣重復9（n-1）次即可（考慮最後只剩下兩個），每一次需要比較（n-i）次,j為跑了的次數。
偽代碼如下：
for i = 1:n-1 (n-1趟)
for j = 1:n-i（比較n-i次）
if a[j] > a[j + 1]
swap(a[j],a[j+1])
endif
endfor
endfor
當然由於數組元素從0開始，則編程時只需要將循環的首尾均減一即可。
復雜度分析：本算法共有兩個循環，外循環共(n-1)個，內循環共（n-i）個，則總數為（n-1）+(n-2)+...+1 = [n*（n-1)]/2=O(n^2).
2、插入排序：
本算法也從其名字來理解，這次我們想象一下學生們排隊好了，每個學生的身高都不同，現在希望他們能夠快速的按照從矮到高的順序排好隊。我們的策略是插入的人都和隊伍中的人挨個比，如果比隊伍中的人矮，那就將隊伍中的人向後移動一個位置，一直到合適的位置將其插入進去。這時候我們假設第一個元素已經在數組中了（因為沒人和他比），這時我們只需要將剩下的n-1個人插入到隊伍中就好了。假設隊伍中已經插入了i個人，則第i+1個人需要和隊伍中的i個人比才可以。
for i = 2:n //插入第i個人
key = a[i]; //設其為關鍵字用來跟每一個位置進行比較
j = i-1;
for j = i-1:1 //關鍵字和前面i-1個人比較
if a[j] > key //大於關鍵字則將其向後移動一個，空一個空出來
a[j+1] = a[j];
else //如果key大於隊伍中的值時就退出
break;
endif
endfor
a[j+1] = key;//將其插入到該值的後面
endfor
復雜度分析：該算法也包含兩層循環，外層有n-1個元素，內層有i-1個元素，則共有1+2+...+n-1 = [n*(n-1)]/2 = O(n^2)
稍微休息一下，縱觀以上兩個算法，雖然算法不同，但是都得需要循環比較，在相對有序時，快速排序的內層循環可以快速退出，因此其效果相對好一點，而冒泡排序還是從頭比較。
3、歸並排序：
看了兩個循環嵌套的算法，下面看看遞歸的算法吧。歸並排序是典型的具有歸並性質的算法。先來說說它的思想，歸並，換言之就是合並，既然要合並那就得先把原來的數組分開吧。咱們還是接著上面的例子，我們先將隊伍分成兩組，然後對兩組排序，排序後進行合並。分成的兩組其實又可以繼續分為兩組並合並，因此此處就可以使用遞歸的方法。
Merge://合並的代碼
input:a[]
n1 = med；
n2 = n-med;
L[] = a[1:n1];
R[] = a[med+1:n];
L[n1+1] = 65535;//哨兵牌，每次到這之後只將剩下的那一摞放到數組中即可
R[n2+1] = 65535；
i = 1:n1;
j = 1:n2;
for k = 1:n
if(L[i] < R[j])
a[k] = L[i]
i++;
else
a[k] = R[j]
j++;
endif
endfor
MergeSort:
q = n/2;
MergeSort(a,1,q);
MergeSort(a,q+1,n);
Merge(a,1,q,n);
復雜度分析：對於遞歸調用的復雜度分析，要明白主方法：T（n）=aT(n/b)+f(n) 要掌握三種情況：1）如果f(n)比n^(log(b)a)小，則T（n） = Ot(n^(log(b)a));2）如果f(n)比n^(log(b)a)大，則T（n）= ot(f(n));3）如果f(n)和n^(log(b)a)差不多大，則T（n）= ot(n^(log(b)a) * lgn)。
在此算法中，a = 2,b = 2;故 n^(log(b)a) = n = f(n),所以滿足3），故T（n）= O(nlgn)。雖然該算法時間很快，但是需要使用兩個數組來存儲L和R，典型的空間換取時間的手法。
4、快速排序：
聽到這個名字，相必大家很快就覺得這個算法肯定很快，事實上也確實如此。該算法也采用了分而治之以及遞歸的思想。其主要的思想是：先隨機選擇一個關鍵人物作為標准，將比他矮的放到左邊，比他高的放到右邊。然後再在剩下的兩組中按照此種方法進行遞歸。
Partition://分開確定pivot的位置，方便將其分開遞歸排序
pivote = a[1];//將第一個人作為標准
p_low = 1;
for i = 2:n
if a[i]<pivote
swap(a[i],a[p_low]);
p_low++;
endif
endfor
return p_low;
QuickSort:
p = Partition(a,1,n);
QuickSort(a,1,p-1);
QuickSort(a,p+1,n);
復雜度分析：類似於歸並排序，該算法也將原問題分成兩部分，T（n）= T(n/p)+T(n/(1-p))+n,其最好情況T（n）=2T(n/2)+n=O(nlgn),最壞的情況是T（n）= T(n-1)+O(n),T(n) = O(n^2);而對於不均分的情況，分析得出T（n）=O(nlgn)。
該算法雖然和快速排序算法的復雜度一樣，但是該算法在基本排好序的情況下屬於最壞的情況，因此使用時需謹慎。
5、堆排序：
下面就來說一說堆排序，堆排序相對於上面幾種排序稍微麻煩一點，但是只要掌握其精髓，也是很容易理解的。這個舉實際的例子確實不太好舉，但是大家可以想象出一棵二叉樹。
堆排序，主要利用了最大堆和最小堆，其本質就是棵二叉樹。
該排序過程大概可以分成如下三步：1）建立一個二叉樹 2）將堆變為最大堆（即將最大值轉移到堆頂），從最後一個非葉子節點開始 3）將堆頂元素和最後一個元素互換，然後調整堆，使其滿足最大堆（堆長度在變）
1）此處不需要什麼操作，只是提醒大家數組中的元素在樹中的位置為前序遍歷存儲（根左右）
2）
BuildMaxHeap(a,n)：
第一個非葉子節點為：n/2
for i = n/2:1
HeapAjust(a,i,n);
end
HeapAjust(a,i):調整為最大堆
l=LEFT(i);//左子樹
r = RIGHT(i);//右子樹
if l<n && a[l] > a[i]
largest = l;
endif
if r<n && a[r] >a[largest]
largest = r;
endif
if largest != i
swap(a[i],a[largest]);
HeapAjust(a,largest);
endif
HeapSort(a,n)
BuildMaxHeap(a,n);
for i = n:2
swap(a[1],a[i];
HeapAjust(a,1,i-1);
endfor
復雜度分析：該算法主要包括兩部分，第一部分是堆調整O（lgn）,建最大堆時，共調用（n/2）次，故其為O（nlgn）.堆排序時主要包括O（nlgn）+ O(nlgn) = O(nlgn)
堆排序不需要大量的遞歸或者多維的暫存數組。這對於數據量非常巨大的序列是合適的。比如超過數百萬條記錄，因為快速排序，歸並排序都使用遞歸來設計算法，在數據量非常大的時候，可能會發生堆棧溢出錯誤。但是快速的時間一般線性增長，但是堆排序為nlgn的速度。
