這個問題糾纏了我好久，總想怎樣才能把各種算法可視化，更容易理解和記憶。
排序是一個經典的問題，它以一定的順序對一個數組或列表中的元素進行重新排序。而排序算法也是各有千秋，每個都有自身的優點和局限性。雖然這些算法平常根本就不用自己去編寫，但作為一個有追求的程式設計師，還是要了解它們從不同角度解決排序問題的思想。
看到visualgo.net/zh就是一個可視化算法的網站，第一次訪問的時候，真的是眼前一亮，自己被震撼了。我今天就總結一下，方便以後查閱。
01冒泡排序
冒泡排序的基本思想就是：把小的元素往前調或者把大的元素往後調。假設數組有 N 個元素，冒泡排序過程如下：
從當前元素起，向後依次比較每一對相鄰元素(a,b)如果 a>b 則交換這兩個數重複步驟1和2，直到比較最後一對元素（第 N-2 和 N-1 元素）此時最大的元素已位於數組最後的位置，然後將 N 減 1，並重複步驟1，直到 N=1冒泡排序的核心代碼：
public static void bubbleSort(int[] a, int n) {// 排序趟數，最後一個元素不用比較所以是 (n-1) 趟 for (int i = 0; i < n - 1; i++) { // 每趟比較的次數，第 i 趟比較 (n-1-i) 次 for (int j = 0; j < n - 1 - i; j++) { // 比較相鄰元素，若逆序則交換 if (a[j] > a[j+1]) { int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp; } } }}
難點在於邊界的確定，算法分析：
平均時間複雜度是 O(n^2)，最佳情況是 O(n)，最差情況是 O(n^2)；空間複雜度 O(1)；穩定的排序算法（相等元素的前後順序排序後不變）；
02選擇排序
選擇排序的基本思想就是：每次從未排序的列表中找到最小(大)的元素，放到已排序序列的末尾，直到所有元素排序完畢。假設數組有 N 個元素且 L=0，選擇排序過程如下：
從 [L...N-1] 範圍中找到最小元素的下標 X交換第 X 與第 L 位置的元素值L 加 1，重複以上步驟，直到 L=N-2選擇排序的核心代碼：
public static void selectionSort(int[] a, int n) {// 排序趟數，最後一個元素是最大的不用比較所以是 (n-1) 趟for (int i = 0; i < n-1; i++) {int minIndex = i; // 無序列表中最小元素的下標for (int j = i+1; j < n; j++) {// 在無序列表中查找最小元素的小標並記錄if (a[j] < a[minIndex]) {minIndex = j;}}// 將最小元素交換到本次循環的前端int tmp = a[minIndex];a[minIndex] = a[i];a[i] = tmp;}}
難點在於邊界的確定，算法分析：
平均時間複雜度是 O(n^2)，最佳和最差情況也是一樣；空間複雜度 O(1)；不穩定的排序算法（相等元素的前後順序排序後可能改變）；
03插入排序
插入排序的基本思想是：每次將待插入的元素，按照大小插入到前面已排序序列的適當位置上。插入排序過程如下：
從第一個元素開始，該元素可認為已排序取出下一個元素，在已排序的元素序列中從後向前掃描如果該元素（已排序）大於待插入元素 ，把它移到下一個位置重複步驟 3，直到找到一個小於或等於待插入元素的位置，將待插入元素插入到下一個位置重複步驟 2~5，直到取完數組元素
插入排序的核心代碼：
public static void insertionSort(int[] a, int n) {// a[0] 看做已排序 for (int i = 1; i < n; i++) { int x = a[i]; // 待插入元素 int j=i-1; // 插入的位置 while (j >= 0 && a[j] > x) { a[j+1] = a[j]; // 為待插入元素騰地 j--; } a[j+1] = x; // 插入到下一個位置 j+1 }}
難點在於邊界的確定，算法分析：
平均時間複雜度是 O(n^2)，最佳情況是 O(n)，最差情況是 O(n^2)；空間複雜度 O(1)；穩定的排序算法；
04希爾排序
希爾排序也稱為增量遞減排序，是對直接插入算法的改進，基於以下兩點性質：
插入排序在對幾乎已排好序的數據操作時，效率高，可以達到線性排序的效率但插入排序一般來說是低效的，因為插入排序每次只能移動一位數據希爾排序的改進是，使用一個增量將數組切分不同的分組，然後在組內進行插入排序，遞減增量，直到增量為 1，好處就是數據能跨多個元素移動，一次比較就可能消除多個元素的交換。基本過程如下：
選取一個遞增序列，一般使用x/2，或者x/3+1使用序列中最大的增量，對數組分組，在組內插入排序，遞減增量，直到為 1。
希爾排序的核心代碼：
public static void shellSort(int[] a, int n) {// 計算遞增序列，3x+1 : 1, 4, 13, 40, 121, 364, 1093, ... int h = 1; while (h < n/3) h = 3*h + 1; while (h >= 1) {// 直到間隔為 1 // 按間隔 h 切分數組 for (int i = h; i < n; i++) { // 對 a[i], a[i-h], a[i-2*h], a[i-3*h]...使用插入排序 int x = a[i]; // 待插入元素 int j=i; while (j >=h && x < a[j-h]) { a[j] = a[j-h];// 為待插入元素騰地 j -= h; } a[j] = x; // 插入 x } // 遞減增量 h /= 3; }}
難點在於邊界的確定，算法分析：
時間複雜度與選擇的增量序列有關，平均時間複雜度O(nlg2n)，最好 O(nlogn)，最差是 O(n^2)；空間複雜度 O(1)；不穩定的排序算法；
05歸併排序（遞歸&非遞歸）
歸併排序是分而治之的排序算法，基本思想是：將待排序序列拆分多個子序列，先使每個子序列有序，再使子序列間有序，最終得到完整的有序序列。歸併排序本質就是不斷合併兩個有序數組的過程，實現時主要分為兩個過程：
拆分 - 遞歸的將當前數組二分（如果N是偶數，兩邊個數平等，如果是奇數，則一邊多一個元素），直到只剩 0 或 1 個元素歸併 - 分別將左右半邊數組排序，然後歸併在一起形成一個大的有序數組
二路歸併遞歸實現，核心代碼：
public static void merge(int[] a, int low, int mid, int high) {int n = high - low + 1; // 合併後元素總數 int[] b = new int[n]; // 臨時合併數組 int left = low, // 左邊有序序列起始下標 right = mid + 1, // 右邊有序序列起始下標 bIdx = 0; // 按升序歸併到新數組 b 中 while (left <= mid && right <= high) { b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++]; } // 右邊序列已拷貝完畢，左邊還有剩餘，將其依次拷貝到合併數組中 while (left <= mid) { b[bIdx++] = a[left++]; } // 左邊序列已拷貝完畢，右邊還有剩餘，將其依次拷貝到合併數組中 while (right <= high) { b[bIdx++] = a[right++]; } // 將歸併後的數組元素拷貝到原數組適當位置 for (int k = 0; k < n; k++) { a[low + k] = b[k]; }}
遞歸的本質就是壓棧，對於 Java 來說，調用層次太深有可能造成棧溢出。一般的，遞歸都能轉為迭代實現，有時迭代也是對算法的優化。
歸併排序中的遞歸主要是拆分數組，所以，非遞歸的重點就是把這部分改成迭代，它們的終止條件不同：
遞歸是在遇到基本情況時終止，比如遇到了兩個各包含1個元素的數組，從大數組到小數組，自頂向下迭代則相反，自底向上，它首先按 1 切分保證數組中的每2個元素有序，然後按 2 切分，保證數組中的每4個元素有序，以此類推，直到整個數組有序核心代碼：
public static void unRecursiveMergeSort(int[] a, int n) {int low = 0, high = 0, mid = 0; // 待歸併數組長度，1 2 4 8 ... int len = 1; // 從最小分割單位 1 開始 while(len <= n) { // 按分割單位遍歷數組並合併 for (int i = 0; i + len <= n; i += len * 2) { low = i; // mid 變量主要是在合併時找到右半邊數組的起始下標 mid = i + len - 1; high = i + 2 * len - 1; // 防止超過數組長度 if (high > n - 1) { high = n - 1; } // 歸併兩個有序的子數組 merge(a, low, mid, high); } len *= 2; // 增加切分單位 }}
難點在於邊界的確定，算法分析：
平均時間複雜度，最佳和最差情況都是 O(nlgn)；空間複雜度 O(n)，需要一個大小為 n 的臨時數組；歸併排序也是一個穩定的排序算法；
06快速排序
快排可以說是應用最廣泛的算法了，它的特點是使用很小的輔助棧原地排序。它也是一個分而治之的排序算法，基本思想是：選取一個關鍵值，將數組分成兩部分，一部分小於關鍵值，一部分大於關鍵值，然後遞歸的對左右兩部分排序。過程如下：
選取 a[low] 作為關鍵值-切分元素 p使用兩個指針遍歷數組（既可一前一後，也可同方向移動），將比 p 小的元素前移，最後交換切分元素遞歸的對左右部分進行排序
快速排序的核心代碼：
public static int partition(int[] a, int low, int high) {// 將數組切分為 a[low..i-1], a[i], a[i+1..high] int p = a[low]; // 切分元素 int i = low; // 下一個小於切分元素可插入的位置 // 從切分元素下一個位置開始，遍歷整個數組，進行分區 for (int j = low + 1; j <= high; j++) { // 往前移動比切分元素小的元素 if (a[j] < p && (i++ != j)) { int tmp = a[j]; a[j] = a[i]; a[i] = tmp; } } // 交換中樞(切分)元素 int tmp = a[low]; a[low] = a[i]; a[i] = tmp; return i;}
難點在於邊界的確定，算法分析：
平均時間複雜度 O(nlgn)，最佳情況 O(nlgn)，最差情況是 O(n^2)；空間複雜度 O(lgn)，因為遞歸，佔用調用棧空間；快排是一個不穩定的排序算法；
07堆排序
堆排序是利用堆這種數據結構設計的算法。堆可看作一個完全二叉樹，它按層級在數組中存儲，數組下標為 k 的節點的父子節點位置分別如下：
k 位置的父節點位置在 (k-1)/2 向下取整k 位置的左子節點位置在 2k+1k 位置的右子節點位置在 2k+2堆的表示如下：
堆有序的定義是每個節點都大於等於它的兩個子節點，所以根節點是有序二叉堆中值最大的節點。堆排序就是一個不斷移除根節點，使用數組剩餘元素重新構建堆的過程，和選擇排序有點類似（只不過按降序取元素），構建堆有序數組基本步驟如下：
首先使用 (N-1)/2 之前的元素構建堆，完成後，整個堆最大元素位於數組的 0 下標位置把數組首尾數據交換，此時數組最大值以找到把堆的尺寸縮小 1，重複步驟 1 和 2，直到堆的尺寸為 1
堆排序的核心代碼：
/** 遞歸的構造大根堆 */private static void sink(int[] a, int k, int n) {// 是否存在左孩子節點 while ((2*k+1) <= n) { // 左孩子下標 int left = 2*k+1; // left < n 說明存在右孩子，判斷將根節點下沉到左還是右 // 如果左孩子小於右孩子，那麼下沉為右子樹的根，並且下次從右子樹開始判斷是否還要下沉 if (left < n && a[left] < a[left + 1]) left = left + 1; // 如果根節點不小於它的子節點，表示這個子樹根節點最大 if (a[k] >= a[left]) break; // 不用下沉，跳出 // 否則將根節點下沉為它的左子樹或右子樹的根，也就是將較大的值上調 int tmp = a[k]; a[k] = a[left]; a[left] = tmp; // 繼續從左子樹或右子樹開始，判斷根節點是否還要下沉 k = left; }}
難點在於邊界的確定，算法分析：
平均時間複雜度、最佳和最壞均是 O(nlgn)；空間複雜度 O(1)，原地排序；不穩定的排序算法；