排序(Sorting)是計算機程式設計中的一種重要操作，其功能是對一個資料元素集合或序列重新排列成一個按資料元素某個項值有序的序列。
有 n 個記錄的序列{R1，R2，…，Rn}，其相應關鍵字的序列是{K1，K2，…，Kn}，相應的下标序列為1，2，…，n。通過排序，要求找出目前下标序列1，2，…， n 的一種排列p1，p2， …，pn，使得相應關鍵字滿足如下的非遞減（或非遞增）關系，即：Kp1≤Kp2≤…≤Kpn，這樣就得到一個按關鍵字有序的記錄序列{Rp1，Rp2，…，Rpn}。
作為排序依據的資料項稱為“排序碼”，也即資料元素的關鍵碼。若關鍵碼是主關鍵碼，則對于任意待排序序列，經排序後得到的結果是唯一的；若關鍵碼是次關鍵碼，排序結果可能不唯一。
實作排序的基本操作有兩個：
（1）“比較”序列中兩個關鍵字的大小；
（2）“移動”記錄。
若對任意的資料元素序列，使用某個排序方法，對它按關鍵碼進行排序：若相同關鍵碼元素間的位置關系，排序前與排序後保持一緻，稱此排序方法是穩定的；而不能保持一緻的排序方法則稱為不穩定的。
1.直接插入排序
直接插入排序是最簡單的插入類排序。僅有一個記錄的表總是有序的，是以，對 n 個記錄的表，可從第二個記錄開始直到第 n 個記錄，逐個向有序表中進行插入操作，進而得到n個記錄按關鍵碼有序的表。
它是利用順序查找實作“在R[1..i-1]中查找R[i]的插入位置”的插入排序。
注意直接插入排序算法的三個要點：
（1）從R[i-1]起向前進行順序查找，監視哨設定在R[0];
R[0] = R[i]; // 設定“哨兵”
for (j=i-1; R[0].key<R[j].key; --j) // 從後往前找
return j+1; // 傳回R[i]的插入位置為j+1
（2）對于在查找過程中找到的那些關鍵字不小于R[i].key 的記錄，可以在查找的同時實作向後移動,即:查找與移動同時進行.
for (j=i-1; R[0].key<R[j].key; --j)
{
R[j+1] = R[j];
}
（3）i = 2，3，…, n, 實作整個序列的排序(從i = 2開始).
【算法如下】
//C++代碼,確定能夠運作
void insertionSort(int *R,int length)
for (int i = 2; i <= length; ++i)
{
R[0] = R[i]; //設為監視哨
int j;
for (j = i-1; R[0] < R[j]; --j)
{
R[j+1] = R[j]; //邊查找邊後移
}
R[j+1] = R[0]; // 插入到正确位置
}
【性能分析】
（1）空間效率：僅用了一個輔助單元，空間複雜度為O(1)。隻需R[0]做輔助.
（2）時間效率：向有序表中逐個插入記錄的操作，進行了n-1 趟，每趟操作分為比較關鍵碼和移動記錄，而比較的次數和移動記錄的次數取決于待排序列按關鍵碼的初始排列。
直接插入排序的最好情況的時間複雜度為O(n)，平均時間複雜度為O(n^2)。
（3）穩定性：直接插入排序是一個穩定的排序方法。
總體來說:直接插入排序比較适用于帶排序數目少,且基本有序的情況下.
2.折半插入排序
直接插入排序的基本操作是向有序表中插入一個記錄，插入位置的确定通過對有序表中記錄按關鍵碼逐個比較得到的。平均情況下總比較次數約為(n^2)/4。既然是在有序表中确定插入位置，可以不斷二分有序表來确定插入位置，即一次比較，通過待插入記錄與有序表居中的記錄按關鍵碼比較，将有序表一分為二，下次比較在其中一個有序子表中進行，将子表又一分為二。這樣繼續下去，直到要比較的子表中隻有一個記錄時，比較一次便确定了插入位置。
折半插入排序是利用折半查找實作“在R[1..i-1]中查找R[i]的插入位置”。
綜上:折半插入排序隻是減少了比較的次數,是以折半插入排序總的時間複雜度仍是O(n^2).
3.希爾排序
希爾排序又稱縮小增量排序，較直接插入排序和折半插入排序方法有較大的改進。直接插入排序算法簡單，在 n 值較小時，效率比較高，在 n 值很大時，若序列按關鍵碼基本有序,效率依然較高，其時間效率可提高到O(n)。希爾排序即是從這兩點出發，給出插入排序的改進方法。
希爾排序的基本思想是：先将待排序記錄序列分割成若幹個“較稀疏的”子序列，分别進行直接插入排序。經過上述粗略調整， 整個序列中的記錄已經基本有序，最後再對全部記錄進行一次直接插入排序。具體實作時，首先標明兩個記錄間的距離d1，在整個待排序記錄序列中将所有間隔為d1 的記錄分成一組，進行組内直接插入排序，然後再取兩個記錄間的距離d2<d1，在整個待排序記錄序列中，将所有間隔為d2 的記錄分成一組，進行組内直接插入排序，直至標明兩個記錄間的距離dt=1 為止，此時隻有一個子序列，即整個待排序記錄序列。
（1）空間效率：僅用了一個輔助單元，空間複雜度為O(1)。
（2）時間效率：希爾排序時效分析很難，關鍵碼的比較次數與記錄移動次數依賴于步長因子序列的選取，特定情況下可以準确估算出關鍵碼的比較次數和記錄的移動次數。目前還沒有人給出選取最好的步長因子序列的方法。步長因子序列可以有各種取法，有取奇數的，也有取質數的，但需要注意：步長因子中除 1 外沒有公因子，且最後一個步長因子必須為1。
O(log2n)~O(n^2)之間的一個值.
(3)穩定性：希爾排序方法是一個不穩定的排序方法。
交換排序主要是通過兩兩比較待排記錄的關鍵碼，若發生與排序要求相逆，則交換之。
1.冒泡排序(相鄰比較法)
冒泡排序是最簡單的一種交換排序。
假設在排序過程中，記錄序列R[1..n]的狀态為:
則第 i 趟起泡插入排序的基本思想為：借助對無序序列中的記錄進行“交換”的操作，将無序序列中關鍵字最大的記錄“交換”到R[n-i+1]的位置上。
//C++代碼
void bubbleSort(int *R,int length)
bool change = true;
for (int i = 0; i != length-1 && change; ++i)
change = false;
for (int j = 0; j != length-i-1; ++j)
if (R[j] > R[j+1]) //如果相鄰元素中大者在前,交換之
{
int temp = R[j];
R[j] = R[j+1];
R[j+1] = temp;
change = true;
}
(1)空間效率：僅用了一個輔助單元，空間複雜度為O(1)。
(2)時間效率：最好情況的時間複雜度為O(n)，平均時間複雜度為O(n^2)。
(3)穩定性：冒泡排序法是一種穩定的排序方法
總比較次數
2.快速排序
快速排序是通過比較關鍵碼、交換記錄，以某個記錄為界(該記錄稱為支點)，将待排序列分成兩部分。其中，一部分所有記錄的關鍵碼大于等于支點記錄的關鍵碼，另一部分所有記錄的關鍵碼小于支點記錄的關鍵碼。我們将待排序列按關鍵碼以支點記錄分成兩部分的過程，稱為一次劃分。對各部分不斷劃分，直到整個序列按關鍵碼有序.
如果每次劃分對一個元素定位後,該元素的左側子序列與右側子序列的長度相同,則下一步将是對兩個長度減半的子序列進行排序,這是最理想的情況!
//僞碼表示
//一趟快速排序算法：
int Partition1 (Elem R[], int low, int high)
pivotkey = R[low].key; // 用子表的第一個記錄作樞軸記錄
while (low<high) // 從表的兩端交替地向中間掃描
while (low<high && R[high].key>=pivotkey)
--high;
R[low]←→R[high]; // 将比樞軸記錄小的記錄交換到低端
while (low<high && R[low].key<=pivotkey)
++low;
R[low]←→R[high]; // 将比樞軸記錄大的記錄交換到高端
return low; // 傳回樞軸所在位置
容易看出，調整過程中的樞軸位置并不重要，是以，為了減少記錄的移動次數，應先将樞軸記錄“移出”，待求得樞軸記錄應在的位置之後(此時low=high),再将樞軸記錄到位。
将上述“一次劃分”的算法改寫如下：
int Partition2 (Elem R[], int low, int high)
R[0] = R[low]; // 用子表的第一個記錄作樞軸記錄
pivotkey = R[low].key; // 樞軸記錄關鍵字
while (low < high) // 從表的兩端交替地向中間掃描
R[low] = R[high]; // 将比樞軸記錄小的記錄移到低端
R[high] = R[low]; // 将比樞軸記錄大的記錄移到高端
R[low] = R[0]; // 樞軸記錄到位
return low; // 傳回樞軸位置
//遞歸形式的快速排序算法：
void QSort (Elem R[], int low, int high)
// 對記錄序列R[low..high]進行快速排序
if (low < high-1) // 長度大于1
pivotloc = Partition(L, low, high); // 将L.r[low..high]一分為二
QSort(L, low, pivotloc-1); // 對低子表遞歸排序，pivotloc 是樞軸位置
QSort(L, pivotloc+1, high); // 對高子表遞歸排序
void QuickSort(Elem R[], int n) // 對記錄序列進行快速排序
QSort(R, 1, n);
(1)空間效率：快速排序是遞歸的，每層遞歸調用時的指針和參數均要用棧來存放，遞歸調用層次數與上述二叉樹的深度一緻。因而，存儲開銷在理想情況下為O(log2n)，即樹的高度；在最壞情況下，即二叉樹是一個單鍊，為O(n)。
(2)時間效率：在n 個記錄的待排序列中，一次劃分需要約 n 次關鍵碼比較，時效為O(n)，若設T(n)為對 n 個記錄的待排序列進行快速排序所需時間。理想情況下：每次劃分，正好将分成兩個等長的子序列，則
T(n)≤cn+2T(n/2) c 是一個常數
≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)
≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)
······
≤cnlog2n+nT(1)=O(nlog2n)
可以證明,QuickSort的平均計算也是O(nlog2n).
最壞情況下：即每次劃分，隻得到一個子序列，時效為O(n^2)。
快速排序是通常被認為在同數量級O(nlog2n)的排序方法中平均性能最好的。但若初始序列按關鍵碼有序或基本有序時，快排序反而蛻化為冒泡排序。為改進之，通常以“三者取中法”來選取支點記錄，即将排序區間的兩個端點與中點三個記錄關鍵碼居中的調整為支點記錄。
(3)快速排序是一個不穩定的排序方法.
(4) 最慘情況:空間複雜度->O(n),時間複雜度->O(n^2)
平均情況:空間複雜度->O(log2n),時間複雜度->O(nlog2n)
(5)快速排序比較适用于輸入規模n較大的情況.
1.選擇排序
簡單選擇排序是最簡單的一種選擇類的排序方法。假設排序過程中，待排記錄序列的狀态為：
并且有序序列中所有記錄的關鍵字均小于無序序列中記錄的關鍵字，則第i 趟簡單選擇排序是，從無序序列R[i..n]的n-i+1 記錄中選出關鍵字最小的記錄加入有序序列。
操作方法：第一趟，從n 個記錄中找出關鍵碼最小的記錄與第1 個記錄交換；第二趟，從第二個記錄開始的n-1 個記錄中再選出關鍵碼最小的記錄與第2 個記錄交換；如此，第i趟，則從第i 個記錄開始的n-i+1 個記錄中選出關鍵碼最小的記錄與第 i 個記錄交換，直到整個序列按關鍵碼有序。
int selectMinIndex(int *A,int index,int length)
int min = index;
for (int i = index+1; i != length; ++i)
if (A[i] < A[min])
min = i;
return min;
void selectSort(int *A,int length)
for (int i = 0; i != length; ++i)
int k = selectMinIndex(A,i,length);
if (k != i)
int temp = A[i];
A[i] = A[k];
A[k] = temp;
(2)時間效率：簡單選擇排序的最好和平均時間複雜度均為O(n^2)。
(3)穩定性：不同教材對簡單選擇排序的穩定性有争議，一般認為，若是從前往後比較來選擇第i 小的記錄則該算法是穩定的，若是從後往前比較來選擇第i 小的記錄則該算法是不穩定的。
2.堆排序
堆排序的特點是，在以後各趟的“選擇”中利用在第一趟選擇中已經得到的關鍵字比較的結果.
堆的定義: 堆是滿足下列性質的數列{r1, r2, …，rn}：
若将此數列看成是一棵完全二叉樹，則堆或是空樹或是滿足下列特性的完全二叉樹：其左、右子樹分别是堆，并且當左/右子樹不空時，根結點的值小于(或大于)左/右子樹根結點的值。
由此，若上述數列是堆，則r1 必是數列中的最小值或最大值，分别稱作小頂堆或大頂堆。
堆排序即是利用堆的特性對記錄序列進行排序的一種排序方法。具體作法是：設有 n 個元素，将其按關鍵碼排序。首先将這 n 個元素按關鍵碼建成堆，将堆頂元素輸出，得到n 個元素中關鍵碼最小(或最大)的元素。然後，再對剩下的n-1 個元素建成堆，輸出堆頂元素，得到n 個元素中關鍵碼次小(或次大)的元素。如此反複，便得到一個按關鍵碼有序的序列。稱這個過程為堆排序。
是以，實作堆排序需解決兩個問題：
（1）如何将n 個元素的序列按關鍵碼建成堆。
建堆方法：對初始序列建堆的過程，就是一個反複進行篩選的過程。n 個結點的完全二叉樹，則最後一個結點是第 n/2 個結點的孩子。對第 n/2 個結點為根的子樹篩選，使該子樹成為堆，之後向前依次對各結點為根的子樹進行篩選，使之成為堆，直到根結點。
（2）輸出堆頂元素後，怎樣調整剩餘n-1 個元素，使其按關鍵碼成為一個新堆。
調整方法：設有m 個元素的堆，輸出堆頂元素後，剩下m-1 個元素。将堆底元素送入堆頂，堆被破壞，其原因僅是根結點不滿足堆的性質。将根結點與左、右孩子中較小(或小大)的進行交換。若與左子女交換，則左子樹堆被破壞，且僅左子樹的根結點不滿足堆的性質；若與右子女交換，則右子樹堆被破壞，且僅右子樹的根結點不滿足堆的性質。繼續對不滿足堆性質的子樹進行上述交換操作，直到葉子結點，堆被建成。稱這個自根結點到葉子結點的調整過程為篩選。
堆排序的算法如下所示：
void heapSort ( Elem R[], int n ) // 對記錄序列R[1..n]進行堆排序。
for ( i=n/2; i>0; --i ) // 把R[1..n]建成大頂堆
HeapAdjust ( R, i, n );
for ( i=n; i>1; --i )
R[1]←→R[i];
//将堆頂記錄和目前未經排序子序列,R[1..i]中最後一個記錄互相交換
HeapAdjust(R, 1, i-1); // 将R[1..i-1] 重新調整為大頂堆
}
其中篩選的算法如下所示。為将R[s..m]調整為“大頂堆”，算法中“篩選”應沿關鍵字較大的孩子結點向下進行。
void HeapAdjust (Elem R[], int s, int m)
/* 已知R[s..m]中記錄的關鍵字除R[s].key 之外均滿足堆的定義，本函數調整R[s] 的關
鍵字，使R[s..m]成為一個大頂堆（對其中記錄的關鍵字而言）*/
rc = R[s];
for ( j=2*s; j<=m; j*=2 ) // 沿key 較大的孩子結點向下篩選
if ( j<m && R[j].key<R[j+1].key )
++j; // j 為key 較大的記錄的下标
if ( rc.key >= R[j].key )
break; // rc 應插入在位置s 上
R[s] = R[j];
s = j;
R[s] = rc; // 插入
（2）時間效率：
①對深度為k 的堆，“篩選”所需進行的關鍵字比較的次數至多為2(k-1);
②對n 個關鍵字，建成深度為h(=ëlog2nû+1)的堆，所需進行的關鍵字比較的次數至多為4n;
③調整“堆頂”n-1 次，總共進行的關鍵字比較的次數不超過
2(log2(n-1)+ log2(n-2)+ …+log22)<2n(log2n)
是以，堆排序的平均和最壞時間複雜度均為O(nlogn)。
(3)堆排序是一個不穩定的排序方法。
2.二路歸并排序:
【算法思想】
歸并排序的基本思想是：将兩個或兩個以上的有序子序列“歸并”為一個有序序列。
在内部排序中，通常采用的是2-路歸并排序。即：将兩個位置相鄰的有序子序列，
空間複雜度為O(n),穩定,時間複雜度O(nlog2n)
//僞代碼,不一定能夠運作
void Merge(Elem SR[], Elem TR[], int i, int m, int n)
// 将有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n]
for (j=m+1, k=i; i<=m && j<=n; ++k) // 将SR 中記錄由小到大地并入TR
if (SR[i].key<=SR[j].key)
TR[k] = SR[i++];
else
TR[k] = SR[j++];
if (i<=m)
TR[k..n] = SR[i..m]; // 将剩餘的SR[i..m]複制到TR
if (j<=n)
TR[k..n] = SR[j..n]; // 将剩餘的SR[j..n]複制到TR
歸并排序的算法可以有兩種形式：遞歸的和遞推的，它是由兩種不同的程式設計思想得出的。
在此，隻讨論遞歸形式的算法，這是一種自頂向下的分析方法：如果記錄無序序列R[s..t]的兩部分R[s..ë(s+t)/2û]和R[ë(s+t)/2+1..tû]分别按關鍵字有序，則利用上述歸并算法很容易将它們歸并成整個記錄序列是一個有序序列，由此，應該先分别對這兩部分進行2-路歸并排序。
void Msort ( Elem SR[], Elem TR1[], int s, int t )
if (s==t)
TR1[s] = SR[s];
else
m = (s+t)/2; // 将SR[s..t]平分為SR[s..m]和SR[m+1..t]
Msort (SR, TR2, s, m);
// 遞歸地将SR[s..m]歸并為有序的TR2[s..m]
Msort (SR, TR2, m+1, t);
//遞歸地SR[m+1..t]歸并為有序的TR2[m+1..t]
Merge (TR2, TR1, s, m, t);
// 将TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]
void MergeSort (Elem R[]) // 對記錄序列R[1..n]作2-路歸并排序。
MSort(R, R, 1, n);
(1)空間效率：需要一個與表等長的輔助元素數組空間，是以空間複雜度為O(n)。
(2)時間效率：對n 個元素的表，将這n 個元素看作葉結點，若将兩兩歸并生成的子表看作它們的父結點，則歸并過程對應由葉向根生成一棵二叉樹的過程。是以歸并趟數約等于二叉樹的高度-1，即log2n，每趟歸并需移動記錄n 次，故時間複雜度為O(nlog2n)。
(3)穩定性：歸并排序是一個穩定的排序方法。