排序的概念
排序：就是將一串東西，按照要求進行排序，按照遞增或遞減排序起來

穩定性：就是比如排序中有兩個相同的數，如果排序后，這兩個相同的數相對位置不變，這說明是穩定的，反之不穩定

插?排序

思想：就是將一個后面未排序的數，從后向前面有序的數進行掃描，找到對應為止插入，就像平時玩撲克牌一樣

1.遍歷整個數組，定義一個臨時遍歷tem存儲當前要排序的值的值
2.當前元素與其前面元素進行比較
如果當前值大于tem就將這個值向后移動，反之就找到了退出，將該下標后面的值賦值為tem，array[ j + 1] = tem

public class Test {public static void main(String[] args) {int[] array = {3,1,2,3,4};insertSort(array);System.out.println(Arrays.toString(array));}//快速排序public static void insertSort(int[] array){for (int i = 1; i < array.length; i++) {int tem = array[i];int j = i-1;for (; j >=0 ; j--) {//如果存在下標j的值大于tem//就將這個值向后移動if(array[j]>tem){array[j+1] = array[j];}else {break;}}//最后將找到的j的后面那個值賦值給temarray[j+1] = tem;}}
}

運行結果如下

時間復雜度：O(N^2) ，因為這里最慢是1+2+3……+n,求和 n(n+1) / 2
空間復雜度：O(1)，這里就多開辟了tem
穩定性：穩定，這里再遇到<=tem就會退出循環，所以說遇到相同的并不會改變位置
并且可以發現如果元素集合越接近有序，其方式更高效

希爾排序

希爾排序（Shell Sort）是插入排序的一種改進版本
思想：它通過將待排序的列表分成若干子列表，對每個子列表進行插入排序，逐步縮小子列表的間隔，最終完成整個序列的排序

1.先選擇增量序列：選擇gap，用于將其分為若干子序列，經常就是采用（n / 2 ,n/4……1）
2 .分組進行插入排序，逐漸的縮小增量，直到增量為1，在對整個序列進行一次插入排序，就完成排序了

public class Test {public static void main(String[] args) {int[] array = {3,1,2,3,4};shellSort(array);System.out.println(Arrays.toString(array));}public static void shellSort(int[] array){int gap = array.length;//先進行分組進行插入排序while(gap>1){gap = gap/2;//確定分幾組shell(array,gap);}}public  static void shell(int[] array,int gap){for (int i = gap; i < array.length; i++) {//根據組進行排序int tem = array[i];int j = i-gap;for (; j >=0 ; j-=gap) {//如果存在下標j的值大于tem//就將這個值向后移動if(array[j]>tem){array[j+gap] = array[j];}else {break;}}array[j+gap] = tem;}}
}

運行結果如下

希爾排序是直接插入排序的一種優化
穩定性：不穩定
時間復雜度：O(N) ~ O(N ^ 2)
空間復雜度：O(1)

直接選擇排序

思想：每次從待排序數據元素中找到最小或最大的一個元素，放在待排序的起始位置，直到全部都排完
實現：遍歷整個待排序列，記錄當前下標i，再遍歷其后面的元素，判斷是否有比它小的，如果有記錄當前下標，然后進行交換

public class Test {public static void main(String[] args) {int[] array = {3,1,2,3,4};selectSort(array);System.out.println(Arrays.toString(array));}//選擇排序public static void selectSort(int[] array){for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i+1; j <array.length ; j++) {if(array[j]<array[minIndex]){//記錄最小元素下標minIndex=j;}}//進行交換swap(array,i,minIndex);}}public static void swap(int[] array,int i,int j){int tem = array[i];array[i] = array[j];array[j] = tem;}
}

時間復雜度：O(N^2)
空間復雜度：O(1)
穩定性：不穩定

堆排序

思想：就是利用堆這種數據結構進行排序
大根堆：用于排升序序列
小根堆：用于排降序序列

思路：以排升序為例
1.先將其數組創建為大根堆
2.定義一個end表示最后一個元素下標，每次堆頂元素都是最大的，將堆頂元素和堆底元素交換，將end–，相當于將堆底元素刪除，這時就還要重新向下調整為大根堆
3.直到end為0的時候截止

public class Test {public static void main(String[] args) {int[] array = {3,1,2,3,4};heapSort(array);System.out.println(Arrays.toString(array));}//堆排序//從小到大，就使用大堆，每次把最后一個元素確定public static void heapSort(int[] array){//創建大根堆creatHeap(array);//每次將最后一個與第一個交換int end = array.length-1;while(end>0){swap(array,0,end);siftDown(array,0,end);//去掉最后一個從新排序end--;}}//建立大根堆堆private static void creatHeap(int[] array) {//從最下面的父親節點開始調整for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {siftDown(array,parent,array.length);}}//向下調整private static void siftDown(int[] array, int parent, int length) {int child = 2*parent+1;while (child<length){if(child+1<length&&array[child]<array[child+1]){child++;}if(array[child]>array[parent]){swap(array,child,parent);parent = child;child = 2*parent+1;}else{break;}}}public static void swap(int[] array,int i,int j){int tem = array[i];array[i] = array[j];array[j] = tem;}
}

時間復雜度：O(N*logN)，調整堆O(logN)，需要遍歷整個數組，每次可能都要調整堆
空間復雜度：O(1)
穩定性：不穩定

冒泡排序

冒泡排序（Bubble Sort）是一種簡單的排序算法，它通過重復地遍歷待排序的列表，比較相鄰的元素并交換它們的位置來實現排序。每遍歷一次就確定一個最后一個元素

public class Test {public static void main(String[] args) {int[] array = {3,1,2,3,4};bubberSort(array);System.out.println(Arrays.toString(array));}public static void bubberSort(int[] array){//外層確定比較幾趟/for (int i = 0; i < array.length-1; i++) {//內層確定每趟比較次數for (int j = 0; j < array.length-i-1; j++) {if(array[j]>array[j+1]){int tem = array[j];array[j] = array[j+1];array[j+1] = tem;}}}}
}

快速排序

快速排序（Quick Sort）是一種高效的排序算法，使用的是分治法的思想
就是找到一個基準值，將列表分為兩部分，左邊一部分是小于基準值，右邊一部分是大于基準值，分別在此基準值的左邊和右邊，重復同樣的操作
因此這里可以是使用遞歸來寫的

1.通常以第一個為基準值，然后進行調整左右
2.遞歸其這個基準值下標左邊 和 右邊 ，直到左邊下標>=右邊下標就結束遞歸
3.這里找到基準值使用Hoare方法來來進行調整，就是high下標先從右向左找到比基準值小的值，low下標從左向右找到比基準值大的值，進行交換，low >= high ，就說明結束了，將此時的low下標與基準值進行交換

public class Test {public static void main(String[] args) {int[] array = {3,1,2,11,4};QuickSort(array);System.out.println(Arrays.toString(array));}//快速排序public static void QuickSort(int[] array){Quick(array, 0, array.length-1);}public static void Quick(int[] array,int left,int right){//截止條件if(left>=right){return;}//遞歸，先將其以key為界限分為兩組//key左右兩邊又可以分組int key = Hoare(array,left,right);Quick(array,left,key-1);//遞歸左邊Quick(array,key+1,right);//遞歸右邊}//調整基準值位置，并返回其下標private static int Hoare(int[] array, int low, int high) {int i = low;int tem = array[low];while (low<high){//1.后面找到比前面基準值小的while (low<high&&array[high]>=tem){high--;}//2.從前面找比基準值大的while (low<high&&array[low]<=tem){low++;}//2.交換swap(array,low,high);}//與基準值進行交換swap(array,i,low);return low;}public static void swap(int[] array,int i,int j){int tem = array[i];array[i] = array[j];array[j] = tem;}
}

上面是使用的是Hoare方法來調整其列表

當然這里也可以使用挖坑法
挖坑法：就是先定義一個臨時變量來存放我們的基準值
1.先從后向前找high下標一個小于臨時變量的值，將這個值放入放入low下標
2.從前向后找low下標一個大于臨時變量的值，將這個值放入high下標地方
重復操作，直到low>=high就結束，最后將low下標的值修改為tem基準值

這里調整基準值方法不僅可以使用Hoare方法，這里也可以使用挖坑法
1.先將基準值拿出來
2.先從后向左找一個小于基準值的值放入坑中，此時該位置就便相當于為坑
3.在從左向右找一個大于基準值的值放入坑中, 此時該位置就便相當于為坑

//挖坑法private static int parttion(int[] array,int low,int high){int tem =array[low];while (low<high){while (low<high&&array[high]>=tem){high--;}array[low] = array[high];while (low<high&&array[low]<=tem){low++;}array[high] = array[low];}array[low] = tem;return low;}

快速排序優化：三數取中
比如序列：1 2 3 4進行快速排序，這樣會使其時間復雜度為N^2,因為其快速排序像構建二叉樹一樣，這樣會浪費時間，因此可以使用一個方法
將low 、mid 和 high下標的值其中最中間的值作為基準值

上面找基準值就是找其第一個元素，但有時候第一個元素并不是最好的，所以可以找第一個、中間、最后一個其中中間的值，作為基準值這樣更合理

//這里利用三數取中，獲取其三個鐘最中間元素的下標private static int mid(int[] array, int low, int high) {int mid = (low+high)/2;if(array[low]<array[high]){if(array[mid]<array[low]){return low;}else if(array[mid]>array[high]){return high;}else {return mid;}}else{if(array[mid]<array[high]){return high;}else if(array[mid]>array[low]){return low;}else {return mid;}}}

時間復雜度：O(N * log N) ~ O (N ^2)，因為每次進行基準值調整就像在構建一顆完全二叉樹，構建數的復雜度為log N
這里又要重復N次 ，但是如果其數列有序的話，時間復雜度可能為O (N ^2)
空間復雜度：O(log N)，因為底層就像一顆二叉樹
穩定性：不穩定

快速排序非遞歸形式
這里采用非遞歸，但是還是要使用挖坑法或者Hoare 方法進行基準值調整
這里是使用stack進行操作，這里如果符合條件就將其下標入棧，縮小其基準值調整范圍，一部分一部分調整，不斷的將下標入棧和出棧操作，當棧為空的時候就結束了

public class Test {public static void main(String[] args) {int[] array = {3,1,2,11,99,33,22,11,4,7,8};quickSortNor(array);System.out.println(Arrays.toString(array));}//快速排序非遞歸public static void quickSortNor(int[] array) {int start = 0;int end = array.length-1;int par = parttion(array,0,end);Stack<Integer> stack = new Stack<>();if(par>start+1){stack.push(start);stack.push(par-1);}if(par<end-1){stack.push(par+1);stack.push(end);}while (!stack.isEmpty()){end = stack.pop();start = stack.pop();par = parttion(array,start,end);if(par>start+1){stack.push(start);stack.push(par-1);}if(par<end-1){stack.push(par+1);stack.push(end);}}}private static int parttion(int[] array,int low,int high){int tem =array[low];while (low<high){while (low<high&&array[high]>=tem){high--;}array[low] = array[high];while (low<high&&array[low]<=tem){low++;}array[high] = array[low];}array[low] = tem;return low;}
}

運行結果如下

歸并排序

歸并排序（Merge sort）就是采用分治法將其分為子序列，先將子序列變為有序，在將子序列歸并進行排序，最終整體就有序了

就是分解和合并兩個操作
先將其分解到不能分解，合并過程中并且注意合并成是有序的數列，就這樣一直和并子序列，最后整體的序列就有序了

public class Test {public static void main(String[] args) {int[] array = {3,1,2,11,4,7,8};mergeSort(array);System.out.println(Arrays.toString(array));}//歸并排序public static void mergeSort(int[] array){mergeSortChild(array,0,array.length-1);}//使用遞歸實現private static void mergeSortChild(int[] array, int left, int right) {if(left>=right){return;}//每次將其分為兩部分進行排序int mid = (left+right)/2;//遞歸左邊mergeSortChild(array,left,mid);//遞歸右邊mergeSortChild(array,mid+1,right);//合并merge(array,left,mid,right);}//合并private static void merge(int[] array,int left,int mid,int right){int tem[] = new int[right-left+1];int k = 0;int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;//將這兩個合并成一個有序數組while (s1<=e1&&s2<=e2){if(array[s1]<=array[s2]){tem[k++] = array[s1++];}else {tem[k++] = array[s2++];}}//最后將另一個沒有放進去的放進去while (s1<=e1){tem[k++] = array[s1++];}while (s2<=e2){tem[k++] = array[s2++];}//最后將這個合并好的放入array數組中for (int i = 0;i<tem.length;i++){array[i+left] = tem[i];}}
}

運行結果如下

時間復雜度：O(N*log N)，和快速排序一樣
空間復雜度：O(N)
穩定性能：穩定

計數排序

上面的排序都是不斷的進行比較移動進行排序，而計數排序是非比較型
1.他就是通過數組下標來存放對應的值，如果這個值和某個下標相同，就將該下標的對應的值++，相當于用一個count數組來記錄每個數出現的次數放在對應下標上
2. 全部放完以后，循環這個count數組，如果對應count[i] ! = 0 ，說明此下標存放值了，就將下標放入array數組中

注意這里再對應下標存放的時候，可能出現92  -  99這樣范圍的序列
因此這里再存放的時候下標可以減去最前面的值，下標-92，將這個作為下標
最后取出放入array數組的時候，要加上92

public class Test {public static void main(String[] args) {int[] array = {3,1,2,11,4,7,8};countSort(array);System.out.println(Arrays.toString(array));}//計算排序public static void countSort(int[] array){int min = array[0];int max = array[0];//1.獲取其最大值和最小值for (int i = 1; i < array.length; i++) {if(array[i]>max){max = array[i];}if(array[i]<min){min = array[i];}}//確定數組長度//在對應下標存放于下標相同的值int range = max - min + 1;int[] count = new int[range];for (int i = 0; i < array.length; i++) {//將array[i]對應的值為count的下標，遇到就++int index = array[i];//這里之所以要減去min，是因為這里可能出現越界問題//如果是92 - 99的值，但是下標并不是這樣的,減去最前面的值count[index-min]++;}int k = 0;for (int i = 0; i < count.length; i++) {while (count[i]!=0){//由于前面下標減去一個min,這里要加回來array[k] = i+min;count[i]--;k++;}}}
}

時間復雜度：O(n + k)，n是列表長度，k是數據范圍
空間復雜度：O(n + k) ，需要額外的計數數組和結果數組

排序方式	最好	最壞	空間復雜度	穩定性
冒泡排序	O(N^2)	O(N^2)	O(1)	穩定
插入排序	O(N)	O(N^2)	O(1)	穩定
選擇排序	O(N^2)	O(N^2)	O(1)	不穩定
希爾排序	O(N)	O(N^2)	O(1)	不穩定
堆排序	O(N*logN)	O(N*logN)	O(1)	不穩定
快速排序	O(N*logN)	O(N^2)	O(logN~N)	不穩定
歸并排序	O(N*logN)	O(N*logN)	O(N)	穩定