算法的穩定性：如果待排序的兩個元素Ri,Rj,其對應的關鍵字keyi=keyj,且在排序前Ri在Rj的前面，如果排序後Ri還在Rj的前面，則稱這種排序算法是穩定的，否則稱排序算法是不穩定的。
内部排序和外部排序：内部排序是指在排序期間，元素全部存放在記憶體中的排序。外部排序是指排序期間元素無法全部同時存放在記憶體中，必須在排序過程中根據要求不斷地在内外存之間移動的排序。
1.插入排序
1）插入排序：每次将一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子序列中，直到全部記錄插入完成。
時間複雜度：O（n2）,空間複雜度：O(1).穩定性：穩定的排序方法。
2）希爾排序：将待排序表分割成若個形如L[i，i+d，i+2d,i+3d,.....i+kd]的特殊子表，分别進行直接插入排序。當整個表呈基本有序時，在對全體記錄進行一次直接插入排序。
過程：先去一個小于n的步長d1,把表中全部記錄分成d1個組，所有距離為d1的倍數的記錄放在同一組中，在各組中進行直接插入排序。然後取第二個步長d2<d1.重複上述過程，直到di=1,即所有記錄在同一組中，再進行直接插入排序。
增量求法：目前不統一，一般采用d1=n/2,，
最後一個增量為1.
時間複雜度：當n在某個特定範圍時為
，最壞情況下為：
，空間複雜度O(1)
不穩定排序
2.交換排序
冒泡排序：将設待排序表長為n,從後往前兩兩比較相鄰元素的值，若為逆序，則交換他們，直到序列比較完。此為一趟冒泡。結果為将最小的元素交換到待排序的第一個位置。下一趟冒泡時，前一趟确定的最小元素不再參與比較，待排序列減少一個元素，每趟排序吧最小元素放到最終位置，這樣最多做n-1趟冒泡就把所有元素排好。
快速排序：快速排序是對冒泡排序的一種改進。其基本思想是基于分治法的：在待排序L[1....n]中任意取一個元素pivot作為基準，通過一趟排序将待排序表劃分為獨立的兩部分L[1...k-1],L[k+1....n]使得L[1....k-1]中所有元素小于等于pivot,L[k+1...n]中所有元素大于pivot,則pivot則放置在最終位置上L(k),這個過程稱為一趟快速排序。而後分别遞歸的對兩個子表重複上述過程，直到每一部分内隻有一個元素或空為止（所有元素放置在最終位置上）
過程：首先假定劃分算法已知，記為partition（），傳回上述中的k,L(k)已經在最終位置上，是以可以先對表進行劃分，而後對表調用同樣的排序操作。遞歸的調用快速排序算法進行排序。程式結構如下：
1)兩個下标分别從首，尾向中間掃描的方法
假設每次都是以目前表中第一個元素作為樞紐值對表進行劃分，則必須将表中比樞紐值大的元素向右移動，比樞紐值小的元素向左移動，使得一趟partition()操作後，表的元素被樞紐值一分為二。
若初始序列3，8，7，1，2，5，6，4排序過程如下：
2 8 7 1 2 5 6 4
2 8 7 1 8 5 6 4
2 1 7 1 8 5 6 4
2 1 7 7 8 5 6 4
2 1 3 7 8 5 6 4 //A[high]A[low]
2）兩個指針索引一前一後逐漸向後掃描
快速排序是所有内部排序算法中平均性能最優的排序算法。在快速排序算法中，并不産生有序子序列，但每一趟排序後将一個元素（基準元素）放在其最終位置上。當初始排序表基本有序或基本逆序是，就得到最壞情況下的時間複雜度O（n2）.
A快排一次排序的應用
A)區分數組中大小寫字母（編寫函數，讓小寫字母在所有大寫字母之前）
b)給定含n個元素的整型數組a,包含0和非0,對數組進行排序，使排序後滿足1.排序後的所有0元素在前，非零元素在後，且非零元素排序前後相對位置不變，不能使用額外的存儲空間。
c)荷蘭國旗問題
D)輸入n個整數，輸出其中最小的k個。
思路1：将輸入的n個數排序，這樣排在最前面的k個數就是最小的k個數。
思路2：假設最小的k個數中最大的為A。在快排中，先在數組中随機選擇一個數字，然後調整數組中數字的順序，使得比選中數字小的數字排在他的左邊，比選中數字大的排在他的右邊（快排一次）
若選中的數字下表剛好是k-1(從0開始)，那麼這個數字（A）加上左側的k-1個數就是最小的k個數。如果他的小标大于k-1,則A位于他的左側，我們可以在他的左邊部分的數組中查找。若小标小于k-1，那麼A應該位于他的右邊，我們可以接着在他的右邊部分中尋找。（發現這是一個遞歸問題，但是我們找到的k個數不一定是有序的）
3.選擇排序
思想：每一趟在後面n-i+1(i=1,2..n-1)個待排序元素中選取關鍵字最小的元素，作為有序子序列的第i個元素，直到n-1趟做完，待排序元素隻剩下1就不用再選了。
1)簡單選擇排序
空間複雜度：O(1)。時間複雜度：元素移動較少不超過3（n-1）(一次swap三次元素移動)。最好移動0次（此時表已經有序）。但是元素間比較的次數與序列的初始狀态無關，始終為n(n-1)/2次。時間複雜度為O（n2）.
2）堆排序
堆排序是一種樹形選擇排序方法，在排序過程中将L[1..n]視為一棵完全二叉樹的順序村粗結構。利用完全二叉樹中雙親結點和孩子結點之間的内在關系，在目前無序區中選擇關鍵字最大（或最小）的元素。
堆排序的實質是建構初始堆，對初始序列建堆，就是一個反複篩選的過程。
A)根據初始關鍵字序列（20，18，22，16，30，19）建構初始大根堆。
在元素個數為n的序列上建堆,其時間複雜度為O(n),這說明可以線上性時間内，将一個無序數組建成一個大頂堆。
B)堆排序的思想
由于堆本身的特點（以大頂堆為例），堆頂元素就是最大值。輸出堆頂元素後，通常将堆底元素放入堆頂，此時根節點已不滿足堆的性質，将堆頂元素向下調整繼續保持大頂堆性質，輸出堆頂元素，重複，直到僅剩一個元素為止。
C)堆的插入和删除
删除堆頂元素時，先将堆的最後一個元素與堆頂元素交換，有序性質破壞，需要堆根結點進行向下調整。
對堆進行插入操作時，先将新結點放在堆的末端，再對這個新結點執行向上調整操作，大頂堆插入操作如下圖所示：
向上調整算法如下所示：
D)堆排序的應用（最小k個數）
輸入n個整數，輸出其中最小的k個.（用堆排序來解決，适合處理海量資料）
思路：首先讀入k個數建立一個大小為k的大頂堆，然後依此讀入剩餘資料，如果目前資料比大頂堆的堆頂小，則用這個數代替目前堆頂元素，并調整時期保持大頂堆性質，如果目前資料比堆頂大，則此數不可能為最小的k個整數之一，故抛棄此數。（時間複雜度:O(nlogk)）
4.歸并排序
二路歸并排序（内部排序，基于分治算法的，使用輔助空間）
含義：将兩個或兩個以上的有序表組合成一個新的有序表。假定待排序表含有n個記錄，則可視為n個有序子表，每個子表長度為1，兩兩歸并，得到
長度為2的有序表，再兩兩歸并...如此重複，直到合成一個長度為n的有序表為止。
過程：分解：将n個元素的待排序表分成各含n/2個元素的子表，采用二路歸并算法對兩個子表遞歸的進行排序。
合并：合并兩個已排序的子表得到排序結果。
Merge()的功能時将前後相鄰的兩個有序表歸并為一個有序表的算法。設兩段有序表A【low...mid】A[mid+1...high]存放在同一順序表中相鄰的位置上，先将他們複制到輔助數組B中，每次從對應B中的兩個段取出一個記錄進行關鍵字比較，将較小者放入A中，當輸入B中有一段超出其表長，則将另一段剩餘部分直接複制到A中。
A)合并兩個排好序的連結清單（連個遞增排序連結清單，合并他們使新連結清單結點仍然是按照遞增排序的）
b)給定有序數組a,b.已知數組a末尾有足夠空間容納b,請實作将b合并到a中。函數頭如下：
Void merge（int a[],int b[],int n,int m）//n為數組a的元素個數，m為數組b的元素個數
思路：先計算總元素個數，從數組末尾（最大元素）開始歸并。
C)原地歸并排序（二叉歸并排序 内部排序，不适用輔助空間）
原地歸并排序不需要輔助數組即可歸并。關鍵在merge這個函數。假設有兩段遞增的子數組arr[begin....mid-1]和arr[mid...end],但整個數組不是遞增的。其中i=begin,j=mid,k=end.
然後把i到mid-1的部分和mid到j-1的部分對調（可通過三次逆序實作）較小部分就調到前面去了，此時數組變為0 1 2 3 4 5 6 9 7 8（前面有序了，後面又是兩個遞增子數組，繼續疊代即可）
D)多路歸并排序（外部排序）
外部排序是指大檔案的排序，即待排序的記錄存儲在外部存儲器上，待排序的檔案無法一次裝入記憶體，需要在記憶體和外部存儲器之間進行多次資料交換，以達到排序整個檔案的目的。
思路：外部排序最常用的算法是多路歸并排序，即将源檔案分解成多個能夠一次性裝入記憶體的部分，分别把每一部分調入記憶體完成排序，然後對已排序的子檔案進行歸并排序。
從二路到多路，增大k可以減少外存資訊讀寫時間，但k個歸并段中選擇最小的記錄需要比較k-1次，為了降低選出每個記錄需要的比較次數k,引入敗者數。
敗者樹可視為一棵完全二叉樹，每個葉結點存放各歸并段在歸并過程中目前參加比較的記錄，内部結點用來記憶左右子樹中的失敗者，讓勝者網上繼續進行比較，一直到根節點。如果比較兩個數，大的為失敗者，小的為勝利者，則根節點指向的數為最小數。
圖中第一個葉子結點為b0.k路歸并的敗者樹深度為
，是以k個記錄中選擇最小關鍵字，最多需要
次比較，比依此比較的k-1次小得多。
案例：有20個有序數組，每個數組有500個unsigned int元素，降序排序。要求從這10000個元素中選出最大的500ge.
思路：依此從20個有序數組中選擇一個目前元素，兩兩比較，然後找出最大的數，循環500次，即可選擇出500個最大的數。但是這裡每選擇一個最大元素，需要比較19次，效率低。
改進方法1：利用堆，從20個數組中各取一個數，并記錄每個數的來源數組，建立一個含有20個元素的大頂堆。此時堆頂就是最大元素，去除堆頂元素，并從堆頂元素的來源數組中取下一個元素加入堆，調整堆後再取最大值，一直這樣進行500次即可。時間複雜度
，其中n為要選出的元素個數，k為有序數組個數。
改進方法2：利用敗者樹。從20個數組中各取一個數，并記錄每個數的來源數組，建立一個20路歸并的敗者樹。此時敗者樹輸出的就是最大的數，然後從最大數的來源數組繼續取下一個數加入敗者樹，繼續比較，直到輸出500個數為止。時間複雜度為
其中n為要選出的元素個數，k為有序數組個數。
不同排序算法的比較