常用的八種內排序算法分別是：

1. 交換排序：冒泡排序、快速排序
2. 選擇排序：簡單選擇排序、堆排序
3. 插入排序：直接插入排序、希爾排序
4. 歸并排序
5. 基數排序

內排序巧記：選(選擇)艦(簡單選擇)隊(堆)的時候腳(交換)毛(冒泡)快(快速)，需要把軌(歸并)跡(基數)擦(插入)仔(直接插入)細(希爾)

一、算法的概念和編碼實現（Java）

1、冒泡排序

冒泡排序的基本思想是，對相鄰的元素進行兩兩比較，順序相反則進行交換，這樣，每一趟會將最小或最大的元素“浮”到頂端，最終達到完全有序

代碼實現（升序）

	public static void selectSort(int[] array) {int len = array.length;boolean flag = true;for (int i = 0; i < len - 1 && flag; i++) {flag = false;for (int j = 0; j < len - i - 1; j++) {if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;flag = true;}}}}

?

最好情況的時間復雜度	最壞情況的時間復雜度	特點	穩定性
T(n)=O(n)	T(n)=O(n2)	如果數據已經排序好，一次都不交換或者交換次數很少，效率很高；如果是完全逆序，則要不停的兩兩交換，效率很低	穩定

2、簡單選擇排序

簡單選擇排序的基本思想是，每一趟從待排序的數據元素中選擇一個最小（或者最大）的元素作為首元素，直到所有元素排完為止。

代碼實現（升序）：

	public static void selectSort(int[] array) {int len = array.length;for (int i = 0; i < len-1; i++) {int min = i;// 每趟排序默認第一個元素是最小的元素，記住下標for (int j = i + 1; j < len; j++) {// 從i+1的位置開始，依次同最小元素比較，若比最小元素小，則記住當前下標if (array[j] < array[min]) {min = j;}}// 無序區最小元素同無序區的第一個元素交換if (min != i) {int temp = array[min];array[min] = array[i];array[i] = temp;}}}

時間復雜度	特點	穩定性
T(n)=O(n2)	簡單，相對于冒泡排序來說交換次數少	不穩定

3、直接插入排序

直接插入排序基本思想是不斷將無序區的元素插入到有序區的適當位置，直到無序區沒有元素排完為止

代碼實現（升序）：

	private static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int j ;int temp = array[i];for (j = i; j>0 && temp < array[j-1]; j--) {array[j] = array[j-1];}array[j] = temp;}}

?

最好情況的時間復雜度	最壞情況的時間復雜度	特點	穩定性
T(n)=O(n)	T(n)=O(n2)	簡單	穩定

4、快速排序

對冒泡排序的一種改進，它的思想是：將元素分為兩組，一組的元素比另外一組的所有元素都要小，然后再按照此方法對兩組元素進行排序。

快速排序我這里就不寫了，快速排序相對于前面三種排序方式來說要復雜很多，看了一些博客，發現寫得都不怎么樣，這里推薦一個講快速排序的視頻https://www.bilibili.com/video/av39519566/?redirectFrom=h5

附上代碼實現（參考視頻中的）：

public static void quickSort(int[] arr,int left,int right){//如果左邊索引比右邊索引更大或者相等，直接使用return結束這個方法if(left >= right){return;}//定義變量保存基準數int base = arr[left];//定義變量i，指向最左邊int i = left;//定義變量j，指向最右邊int j = right;//當i和j不相遇的時候，在循環中進行檢索while(i!=j){//先由j從右向左檢索比基準數小的就停下，否則繼續檢索while(arr[j]>=base && i<j){j--;}//在由i從左向右檢索比基準數大的就停下,否則繼續檢索while(arr[i]<=base && i<j){i++;}//代碼走到這里，i停下了，j也停下了，然后交換i和j位置的元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}//交換基準數和相遇位置的元素arr[left] = arr[i];arr[i] = base;//排基準數左邊的quickSort(arr,left,i-1);//排基準數右邊的quickSort(arr,j+1,right);}

最好情況的時間復雜度	最壞情況的時間復雜度	平均時間復雜度	特點	穩定性
T(n)=O(nlogn)	T(n)=O(n2)	T(n)=O(nlogn)	較復雜	不穩定

5、希爾排序

希爾排序是對直接插入排序的優化，原理是：將數據按照步長dk分為dk個子列，然后再對每個子列運用直接插入排序。

當步長為5的時候，分組情況如下：

?

每個子列排好序后，變成：

代碼實現（升序）：

	public static void main(String[] args) {int[] array = {49,38,65,97,76,13,27,49,55,4};print(array);ShellSort(array,5);print(array);ShellSort(array,3);print(array);ShellSort(array,1);print(array);}private static void print(int[] array){for (int i = 0; i < array.length; i++) {System.out.print(array[i]+"\t");}System.out.println("\n");}//希爾排序,dk表示步長private static void ShellSort(int[] array,int dk) {for(int k = 0;k<dk;k++){//每個子組做直接插入插入排序for(int i = dk+k;i<array.length;){int j ;int temp = array[i];for (j = i; j-dk>=0 && temp < array[j-dk]; ) {j -= dk;//上一個元素的索引需要減去dk，而不是減1array[j] = array[j-dk];}array[j] = temp;i += dk;//下一個元素索引加上dk，而不是加1}}}

說明：從代碼層面來看，希爾排序相對于直接插入排序的不同點在于希爾排序外層多了一層循環，用來將原序列分層若干個子列。內部的直接插入排序做減減或者加加時要改成減去步長或者加上步長

二、時間復雜度和空間復雜度分析

排序的穩定性：根據關鍵字相同（如果數值比較的話是指大小）的記錄排序前后相對位置的變化，可以分為穩定性排序算法和不穩定性排序算法。在排序的序列中，如果存在兩個記錄Ri和Rj，其關鍵字分別為Ki和Kj,并且i<=j,Ki=Kj,即記錄Ri在Rj之前，排序完成后，如果記錄Ri和Rj的相對位置不發生改變，那么該算法是穩定性排序，否則是不穩定排序。

排序方法	時間復雜度（最壞情況）	空間復雜度（輔助空間）	穩定性	復雜性
簡單選擇排序	O(n2)	O(1)	不穩定	簡單
冒泡排序	O(n2)	O(1)	穩定	簡單
快速排序	O(n2)	?	不穩定	較復雜
直接插入排序	O(n2)	O(1)	穩定	簡單
希爾排序	O(n2)	O(1)	不穩定	較復雜