排序算法可以分為内部排序和外部排序，内部排序是資料記錄在記憶體中進行排序，而外部排序是因排序的資料很大，一次不能容納全部的排序記錄，在排序過程中需要通路外存。
常見的内部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。
一、插入排序
插入排序是一種最簡單直覺的排序算法，它的工作原理是通過建構有序序列，對于未排序資料，在已排序序列中從後向前掃描，找到相應位置并插入。
算法步驟：
1）将待排序序列第一個元素看做一個有序序列，把第二個元素到最後一個元素當成是未排序序列。
2）從頭到尾依次掃描未排序序列，将掃描到的每個元素插入有序序列的适當位置。（如果待插入的元素與有序序列中的某個元素相等，則将待插入元素插入到相等元素的後面。）
舉個栗子，對5,3,8,6,4這個無序序列進行簡單插入排序，首先假設第一個數的位置時正确的，想一下在拿到第一張牌的時候，沒必要整理。然後3要插到5前面，把5後移一位，變成3,5,8,6,4.想一下整理牌的時候應該也是這樣吧。然後8不用動，6插在8前面，8後移一位，4插在5前面，從5開始都向後移一位。注意在插入一個數的時候要保證這個數前面的數已經有序。簡單插入排序的時間複雜度也是O(n^2)。
實作代碼：
/**
* @Description:插入排序算法實作
* @author MPK
* @time 2017-7-30
*/
public class insertion_sort {
public static void insertion(int[] list) {
if (list == null || list.length == 0) return ;
for (int i = 1; i < list.length; i++) {
int j = i;
int target = list[i];
while (j > 0 && target < list[j-1]) {
list[j] = list[j-1];
j--;
}
list[j] = target;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] list = {5,3,8,6,4};
insertion(list);
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
}
}
二、希爾排序
希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。
希爾排序是基于插入排序的以下兩點性質而提出改進方法的：
* 插入排序在對幾乎已經排好序的資料操作時， 效率高， 即可以達到線性排序的效率
* 但插入排序一般來說是低效的， 因為插入排序每次隻能将資料移動一位
希爾排序的基本思想是：先将整個待排序的記錄序列分割成為若幹子序列分别進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。
算法步驟：
1）選擇一個增量序列t1，t2，…ti，...，tj ，...，tk，其中ti>tj，tk=1；
2）按增量序列個數k，對序列進行k 趟排序；
3）每趟排序，根據對應的增量ti，将待排序列分割成若幹長度為m 的子序列，分别對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。
舉個例子：
實作代碼：
/**
* @Description:希爾排序算法實作
* @author MPK
* @time 2017-7-30
*/
public class shell_sort {
public static void shellsort(int[] list) {
if (list == null || list.length == 0) return ;
int d = list.length / 2;//初始增量的選擇
while (d >= 1) {
shellinsert(list, d);
d /= 2;
}
}
public static void shellinsert(int[] list, int d) {
for (int i = d; i < list.length; i++) {
int j = i - d;
int temp = list[i];
while (j >= 0 && temp < list[j]) {
list[j+d] = list[j];
j -= d;
}
if (j != i - d) list[j+d] = temp;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] list = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
shellsort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
三、選擇排序
選擇排序(Selection sort)也是一種簡單直覺的排序算法。
算法步驟：
1）首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
2）再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。 3）重複第二步，直到所有元素均排序完畢。 舉個栗子，對5,3,8,6,4這個無序序列進行簡單選擇排序，首先要選擇5以外的最小數來和5交換，也就是選擇3和5交換，一次排序後就變成了3,5,8,6,4.對剩下的序列一次進行選擇和交換，最終就會得到一個有序序列。
實作代碼：
/**
* @Description:選擇排序算法實作
* @author MPK
* @time 2017-7-30
*/
public class select_sort {
public static void selectsort(int[] list) {
if (list == null || list.length == 0) return ;
for (int i = 0; i < list.length - 1; i++) {
//尋找剩餘子序列中最小值
int minindex = i;
for (int j = i+1; j < list.length; j++) {
if (list[j] < list[minindex]) {
minindex = j;
}
}
if (minindex != i) {
int temp = list[i];
list[i] = list[minindex];
list[minindex] = temp;
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] list = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
selectsort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
四、冒泡排序
冒泡排序（Bubble Sort）也是一種簡單直覺的排序算法。它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
算法步驟：
1）比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2）對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。（每次确定一個倒數第幾大的數）
3）針對所有的元素重複以上的步驟，除了最後一個。
4）持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
實作代碼：
/**
* @Description:冒泡排序算法實作
* @author MPK
* @time 2017-7-30
*/
public class bubble_sort {
public static void bubblesort(int[] list) {
if (list == null || list.length == 0) return ;
for (int i = list.length; i > 1; i--) {
for (int j = 0; j < i-1; j++) {
if (list[j] > list[j+1]) {
int temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] list = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
bubblesort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
五、歸并排序
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
算法步驟：
1. 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并後的序列
2. 設定兩個指針，最初位置分别為兩個已經排序序列的起始位置
3. 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
4. 重複步驟3直到某一指針達到序列尾
5. 将另一序列剩下的所有元素直接複制到合并序列尾
如 設有數列{6，202，100，301，38，8，1}
初始狀态：6,202,100,301,38,8，1
第一次歸并後：{6,202},{100,301},{8,38},{1}，比較次數：3；
第二次歸并後：{6,100,202,301}，{1,8,38}，比較次數：4；
第三次歸并後：{1,6,8,38,100,202,301},比較次數：4；
總的比較次數為：3+4+4=11,；
逆序數為14；
代碼實作：
/**
* @Description:歸并排序算法實作
* @author MPK
* @time 2017-7-30
*/
public class merge_sort {
public static void mergesort(int[] list) {
msort(list, 0, list.length-1);
}
public static void msort(int[] list, int left, int right) {
if (left >= right) return ;
int mid = (left + right) /2;
msort(list, left, mid);//遞歸排序左部分
msort(list, mid+1, right);//遞歸排序右部分
merge(list, left, mid, right);//合并
}
public static void merge(int[] list, int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = 0;
int[] temp = new int[right - left + 1];
while (i <= mid && j <= right) {
if (list[i] <= list[j]) {
temp[k++] = list[i++];
}
else {
temp[k++] = list[j++];
}
}
while (i <= mid) {
temp[k++] = list[i++];
}
while (j <= right) {
temp[k++] = list[j++];
}
for (int p = 0; p < temp.length; p++) {
list[left+p] = temp[p];
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] list = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
mergesort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
六、快速排序
快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的内部循環（inner loop）可以在大部分的架構上很有效率地被實作出來。
快速排序使用分治法（Divide and conquer）政策來把一個串行（list）分為兩個子串行（sub-lists）。
算法步驟：
1 從數列中挑出一個元素，稱為 “基準”（pivot），
2 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
3 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的疊代（iteration）中，它至少會把一個元素擺到它最後的位置去。
一趟快速排序的算法是：
1）設定兩個變量i、j，排序開始的時候：i=0，j=N-1；
2）以第一個數組元素作為關鍵資料，指派給key，即key=A[0]；
3）從j開始向前搜尋，即由後開始向前搜尋(j--)，找到第一個小于key的值A[j]，将A[j]和A[i]互換；
4）從i開始向後搜尋，即由前開始向後搜尋(i++)，找到第一個大于key的A[i]，将A[i]和A[j]互換；
5）重複第3、4步，直到i=j； (3,4步中，沒找到符合條件的值，即3中A[j]不小于key,4中A[i]不大于key的時候改變j、i的值，使得j=j-1，i=i+1，直至找到為止。找到符合條件的值，進行交換的時候i， j指針位置不變。另外，i==j這一過程一定正好是i+或j-完成的時候，此時令循環結束）。
示例
假設使用者輸入了如下數組：
建立變量i=0（指向第一個資料）, j=5(指向最後一個資料), k=6(指派為第一個資料的值)。
我們要把所有比k小的數移動到k的左面，是以我們可以開始尋找比6小的數，從j開始，從右往左找，不斷遞減變量j的值，我們找到第一個下标3的資料比6小，于是把資料3移到下标0的位置，把下标0的資料6移到下标3，完成第一次比較：
i=0 j=3 k=6
接着，開始第二次比較，這次要變成找比k大的了，而且要從前往後找了。遞加變量i，發現下标2的資料是第一個比k大的，于是用下标2的資料7和j指向的下标3的資料的6做交換，資料狀态變成下表：
i=2 j=3 k=6
稱上面兩次比較為一個循環。
接着，再遞減變量j，不斷重複進行上面的循環比較。
在本例中，我們進行一次循環，就發現i和j“碰頭”了：他們都指向了下标2。于是，第一遍比較結束。得到結果如下，凡是k(=6)左邊的數都比它小，凡是k右邊的數都比它大：
如果i和j沒有碰頭的話，就遞加i找大的，還沒有，就再遞減j找小的，如此反複，不斷循環。注意判斷和尋找是同時進行的。
然後，對k兩邊的資料，再分組分别進行上述的過程，直到不能再分組為止。
注意：第一遍快速排序不會直接得到最終結果，隻會把比k大和比k小的數分到k的兩邊。為了得到最後結果，需要再次對下标2兩邊的數組分别執行此步驟，然後再分解數組，直到數組不能再分解為止（隻有一個資料），才能得到正确結果。
實作代碼：
/**
* @Description:快速排序算法實作
* @author MPK
* @time 2017-7-30
*/
public class quick_sort {
public static void quicksort(int[] list, int left, int right) {
if (left >= right) return ;
int privotpos = partition(list, left, right);
quicksort(list, left, privotpos-1);
quicksort(list, privotpos+1, right);
}
public static int partition(int[] list, int left, int right) {
int privotkey = list[left];
int privotPointer = left;
while (left < right) {
while (right > left && list[right] >= privotkey) {
right--;
}
while (left < right && list[left] <= privotkey) {
left++;
}
int temp = list[right];
list[right] = list[left];
list[left] = temp;
}
list[privotPointer] = list[left];
list[left] = privotkey;
return left;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] list = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
quicksort(list, 0, list.length-1);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
七、堆排序
堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。
堆排序的平均時間複雜度為Ο(nlogn) 。
算法步驟：
1）建立一個堆H[0..n-1]
2）把堆首（最大值）和堆尾互換
3）把堆的尺寸縮小1，并調用shift_down(0)，目的是把新的數組頂端資料調整到相應位置
4） 重複步驟2，直到堆的尺寸為1
堆排序 堆排序是利用堆的性質進行的一種選擇排序。下面先讨論一下堆。
1.堆
堆實際上是一棵完全二叉樹，其任何一非葉節點滿足性質：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
即任何一非葉節點的關鍵字不大于或者不小于其左右孩子節點的關鍵字。
堆分為大頂堆和小頂堆，滿足Key[i]>=Key[2i+1]&&key>=key[2i+2]稱為大頂堆，滿足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]稱為小頂堆。由上述性質可知大頂堆的堆頂的關鍵字肯定是所有關鍵字中最大的，小頂堆的堆頂的關鍵字是所有關鍵字中最小的。
2.堆排序的思想
利用大頂堆(小頂堆)堆頂記錄的是最大關鍵字(最小關鍵字)這一特性，使得每次從無序中選擇最大記錄(最小記錄)變得簡單。
其基本思想為(大頂堆)：
1)将初始待排序關鍵字序列(R1,R2....Rn)建構成大頂堆，此堆為初始的無須區；
2)将堆頂元素R[1]與最後一個元素R[n]交換，此時得到新的無序區(R1,R2,......Rn-1)和新的有序區(Rn),且滿足R[1,2...n-1]<=R[n];
3)由于交換後新的堆頂R[1]可能違反堆的性質，是以需要對目前無序區(R1,R2,......Rn-1)調整為新堆，然後再次将R[1]與無序區最後一個元素交換，得到新的無序區(R1,R2....Rn-2)和新的有序區(Rn-1,Rn)。不斷重複此過程直到有序區的元素個數為n-1，則整個排序過程完成。
操作過程如下：
1)初始化堆：将R[1..n]構造為堆；
2)将目前無序區的堆頂元素R[1]同該區間的最後一個記錄交換，然後将新的無序區調整為新的堆。
是以對于堆排序，最重要的兩個操作就是構造初始堆和調整堆，其實構造初始堆事實上也是調整堆的過程，隻不過構造初始堆是對所有的非葉節點都進行調整。
下面舉例說明：
給定一個整形數組a[]={16,7,3,20,17,8}，對其進行堆排序。
這樣整個區間便已經有序了。
從上述過程可知，堆排序其實也是一種選擇排序，是一種樹形選擇排序。隻不過直接選擇排序中，為了從R[1...n]中選擇最大記錄，需比較n-1次，然後從R[1...n-2]中選擇最大記錄需比較n-2次。事實上這n-2次比較中有很多已經在前面的n-1次比較中已經做過，而樹形選擇排序恰好利用樹形的特點儲存了部分前面的比較結果，是以可以減少比較次數。對于n個關鍵字序列，最壞情況下每個節點需比較log2(n)次，是以其最壞情況下時間複雜度為nlogn。堆排序為不穩定排序，不适合記錄較少的排序。
實作代碼：
/**
* @Description:堆排序算法實作
* @author MPK
* @time 2017-7-30
*/
public class heap_sort {
public static void heapsort(int[] list) {
if (list == null || list.length == 0) return ;
//建立大頂堆
for (int i = list.length/2-1; i >= 0; i--) {
heapAdjust(list, i, list.length-1);
}
//堆排序
for (int i = list.length - 1; i >= 0; i--) {
int temp = list[0];
list[0] = list[i];
list[i] = temp;
heapAdjust(list, 0, i-1);
}
}
public static void heapAdjust(int[] list, int start, int end) {
int temp = list[start];
//從start結點開始往下進行修正
for (int i = 2*start+1; i <= end; i = 2*i+1) {
//選出左右孩子較大的下标
if (i < end && list[i] < list[i+1]) {
i++;
}
if (temp >= list[i]) {
break;
}
list[start] = list[i];//将子節點上移
start = i;
}
list[start] = temp;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] list = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
heapsort(list);
for (int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}
}
八、基數排序
基數排序是一種非比較型整數排序算法，其原理是将整數按位數切割成不同的數字，然後按每個位數分别比較。由于整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，是以基數排序也不是隻能使用于整數。
說基數排序之前，我們簡單介紹桶排序：
算法思想：是将陣列分到有限數量的桶子裡。每個桶子再個别排序（有可能再使用别的排序算法或是以遞回方式繼續使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列内的數值是均勻配置設定的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
簡單來說，就是把資料分組，放在一個個的桶中，然後對每個桶裡面的在進行排序。
例如要對大小為[1..1000]範圍内的n個整數A[1..n]排序
首先，可以把桶設為大小為10的範圍，具體而言，設集合B[1]存儲[1..10]的整數，集合B[2]存儲 (10..20]的整數，……集合B[i]存儲( (i-1)*10， i*10]的整數，i = 1，2，..100。總共有 100個桶。
然後，對A[1..n]從頭到尾掃描一遍，把每個A[i]放入對應的桶B[j]中。 再對這100個桶中每個桶裡的數字排序，這時可用冒泡，選擇，乃至快排，一般來說任何排序法都可以。
最後，依次輸出每個桶裡面的數字，且每個桶中的數字從小到大輸出，這 樣就得到所有數字排好序的一個序列了。
假設有n個數字，有m個桶，如果數字是平均分布的，則每個桶裡面平均有n/m個數字。如果
對每個桶中的數字采用快速排序，那麼整個算法的複雜度是
O(n + m * n/m*log(n/m)) = O(n + nlogn – nlogm)
從上式看出，當m接近n的時候，桶排序複雜度接近O(n)
當然，以上複雜度的計算是基于輸入的n個數字是平均分布這個假設的。這個假設是很強的 ，實際應用中效果并沒有這麼好。如果所有的數字都落在同一個桶中，那就退化成一般的排序了。
基本解法
第一步
以LSD為例，假設原來有一串數值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根據個位數的數值，在走訪數值時将它們配置設定至編号0到9的桶子中：
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
第二步
接下來将這些桶子中的數值重新串接起來，成為以下的數列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再進行一次配置設定，這次是根據十位數來配置設定：
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
第三步
接下來将這些桶子中的數值重新串接起來，成為以下的數列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。
LSD的基數排序适用于位數小的數列，如果位數多的話，使用MSD的效率會比較好。MSD的方式與LSD相反，是由高位數為基底開始進行配置設定，但在配置設定之後并不馬上合并回一個數組中，而是在每個“桶子”中建立“子桶”，将每個桶子中的數值按照下一數位的值配置設定到“子桶”中。在進行完最低位數的配置設定後再合并回單一的數組中。
最後，加一張8大排序算法的穩定性、時間複雜度、空間複雜度總結表格：