演算法—排序
排序過程詳細的動態圖可參考//www.cnblogs.com/onepixel/articles/7674659.html
1.插入排序 穩定O(n^2)
穩定的意思是a=b，原本a在b前面，排序完成後a也在b前面。
插入排序的思路就是將數組邏輯上分成兩段，一段是排好序的，一段是未排序的，每次從未排序的段中取出來一個，去排好序的裡面找位置插入。
找的過程將排好序的那段位置進行移動，這樣就一直有個位置可以放當前這個元素。
開始認為第一個元素是排好序的。
public static void insertSort(int[] arr) { int length = arr.length; for (int i = 1; i < length; i++) { int data = arr[i]; for (int j = i - 1; j >= 0; j--) { //反向遍歷比較 if (arr[j] > data) { arr[j + 1] = arr[j]; //位置後移 arr[j] = data; } else { break; // 前面都是排好序的，有一個比它小的，再前面肯定更小，直接可以跳出，不用再比較 } } } }
2.希爾排序 不穩定 n*log2n-O(n^2)
希爾排序其實是插入排序的一個改進版本，如上插入排序的程式碼，我們發現有一個break的操作。遇到前面已經排好序了。我們就不用再去遍歷了。希爾排序就是增加這種有序段的數量。
希爾排序是按下標增量進行分組，對每一組進行插入排序，隨著下標增量的減少，數組中有序段也越來越多。最後下標增量到1的時候便是整組排序了。
{1,5,8,9,6,3}
如果按下標增量2那麼就是1,8,6一組進行排序，5,9,3 一組進行排序
第一次：{1,3,6,5,8,9}
…增量依次遞減直到1
public static void shellSort(int[] arr) { int len = arr.length; //增量每次折半,最後增量為1的時候就是最後一次排序 for (int increment = len / 2; increment >= 1; increment /= 2) { //類似插入排序 for (int i = increment; i < len; i++) { //按增量分開使用插入排序 int data = arr[i]; for (int j = i - increment; j >= 0 ; j -= increment) { if (arr[j] > data) { arr[j + increment] = arr[j]; //位置後移 arr[j] = data; } else { break; // 前面都是排好序的，有一個比它小的，再前面肯定更小，直接可以跳出，不用再比較 } } } } }
3.冒泡排序 穩定 O(n^2)
依次比較相鄰兩個元素大小，進行交換，每次就可以選擇最大或者最小的。
/** * 冒泡排序 穩定 依次比較相鄰的兩個元素大小，每輪結束就可以選出來一個最大或者最小的 * @param arr */ public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length; i++) { //外層循環控制輪次 for (int j = 0; j < arr.length - 1 - i; j++) { //內層循環次數越來越少，因為內層跑完一次就找到一個數 if (arr[j] > arr[j+1]) { //交換位置 arr[j] = arr[j] + arr[j+1]; arr[j+1] = arr[j] - arr[j+1]; arr[j] = arr[j] - arr[j+1]; } } } }
4. 選擇排序 不穩定 O(n^2)
有點類似插入排序會將數組分成兩段，去未排序段中每次選擇中最大或者最小的到另一段中。
比如從最左邊開始，去依次遍歷，找到最大或者最小的索引下標，然後交換位置。這樣就找到了最大/最小的數。每輪只換一次位置，冒泡是每次比較都可能會換位置。
/** * 選擇排序 不穩定 先拿出一個數，去依次遍歷，找到最大或者最小的。每輪換一次位置，冒泡是每次比較都可能會換位置。 * @param arr */ public static void selectionSort(int[] arr) { int tempIndex; for (int i = 0; i < arr.length; i++) { tempIndex = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[tempIndex]) { //比較大小 記錄下標位置 tempIndex = j; } } if (tempIndex != i) { //交換位置 arr[i] = arr[i] + arr[tempIndex]; arr[tempIndex] = arr[i] - arr[tempIndex]; arr[i] = arr[i] - arr[tempIndex]; } } }
5. 歸併排序 穩定 O(nlogn)
歸併排序是採用分治的思想，將要排序的數據拆分，再合併，過程如下圖，合併的時候如下塗鴉線條，第一次紅色線條，6和5比，5下去，左邊的指針位置後移一位到9，第二次藍色線條，6和9比，6下去，右邊指針後移一位到8，第三次8和9比，8下去，最後剩下的9直接移下去。JDK的排序就是使用的歸併排序java.util.Arrays#mergeSort()
程式碼
/** * 歸併排序 JDK源碼java.util.Arrays#mergeSort() * @param arr * @param left * @param right */ public static void mergeSort(int[] arr, int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, left, mid); //拆了之後的左 mergeSort(arr, mid + 1, right); //拆了之後的右 merge(arr, left, mid, right); //合併 } } /** * 歸併 */ private static void merge(int[] arr, int left, int mid, int right) { int[] arrTemp = new int[arr.length]; int leftPoint = left; //左邊第一個下標 int rightPoint = mid + 1; //右邊第一個下標 int currentPoint = left; //當前下標 //左右兩邊的數據對於自己來說都已經是有序的，所以就拿右邊的依次和左邊的進行大小比較，將對應的大小關係放入臨時數組對應下標 //左邊指針走到mid位置或者右邊指針走到right位置，既結束循環，兩邊剩下的有序數據，直接追加在臨時數組後面，先左後右 while (leftPoint <= mid && rightPoint <= right) { if (arr[leftPoint] < arr[rightPoint]) { arrTemp[currentPoint] = arr[leftPoint]; leftPoint++; } else { arrTemp[currentPoint] = arr[rightPoint]; rightPoint++; } currentPoint++; } //先處理左邊剩下的直接放入對應位置 while (leftPoint <= mid) { arrTemp[currentPoint++] = arr[leftPoint++]; } //再處理右邊剩下的 while (rightPoint <= right) { arrTemp[currentPoint++] = arr[rightPoint++]; } //將臨時數組裡面的數據放入原始數組中，注意只放merge的那一段的數據 for (int i = left; i <= right; i++) { arr[i] = arrTemp[i]; } }
6.快速排序 不穩定 O(nlogn)
需要先選擇一個基準數，一般選擇第一個，和右邊最後一個數據比較，如果比基準數小就交換位置，如果大則不交換，下標遞減比較前一個，直到交換為止。然後切換成和左邊第一個比較，如果比基準數大就換，否則下標遞增繼續判斷，直到交換為止，然後切換到右邊。。。就這樣左右左右左右，直到碰到一起結束。次輪下來基準數左邊是比它小的，右邊是比它大的；將其左右的數據各自選一個基準數，執行一樣的操作，如此反覆，拆到最後就是一個有序的序列了。
如上圖，最後分完就已經是一個排好的序列了，快排是邊拆邊排，歸併是先拆，合併的時候再排。由上邏輯可以看出，快速排序中基準數的大小是至關重要的，最好的結果就是每次都取偏中間的數作為基準數。我們可以多隨機選出來幾個數，再從其中選一個出來作為基準數。和歸併排序相比快排沒有數據合併的過程，從下面的過程中也可以看出來快排就是之前遞歸裡面說到的尾遞歸
/** * 快速排序 * @param arr */ private static void quicklySort(int[] arr, int left, int right) { int base = arr[left]; //我們選第一個作為基準數,也就是每次的進來left下標 int leftPoint = left; //左邊找的位置 int rightPoint = right; //右邊找的位置 while (leftPoint < rightPoint) { //左邊指針小於右邊 說明還沒碰到一起 //從後往前找 如果後面的數大於等於基準數不交換，指針前移，需要的交換的時候跳出循環 while (leftPoint < rightPoint && arr[rightPoint] >= base) { rightPoint--; } //上述循環跳出，並且左邊指針小於右邊指針 說明需要交換數據，左邊因為換一個小的數據過去所以指針後移 if (leftPoint < rightPoint) { int temp = arr[rightPoint]; arr[rightPoint] = arr[leftPoint]; arr[leftPoint] = temp; leftPoint++; } //切換 從前往後找 如果左邊的數小於等於基準數不交換，指針後移，需要的交換的時候跳出循環 while (leftPoint < rightPoint && arr[leftPoint] <= base) { leftPoint++; } //上述循環跳出，並且左邊指針小於右邊指針 說明需要交換數據，右邊因為換了一個大的數據過去所以指針前移 if (leftPoint < rightPoint) { int temp = arr[rightPoint]; arr[rightPoint] = arr[leftPoint]; arr[leftPoint] = temp; rightPoint--; } } if (left < leftPoint) { //左邊 quicklySort(arr, left, leftPoint - 1); } if (leftPoint < right) { //右邊 quicklySort(arr, leftPoint + 1, right); } }
