本章講述數據結構中的六大排序算法 歡迎大佬們踴躍討論，感謝大家支持！ 我的博客主頁鏈接

一.插入排序

1.1 直接插入排序

1.已知第一個元素如果不包含其他元素，沒有元素可以比較，為有序。
2.我們可以直接從第二個元素i開始，創建一個對象tmp來接下標元素，如果比前一個元素小，前一個元素往后移動，tmp插入i-1下標
3.當元素大于或者等于時，則tmp直接放在i位置即可。

  public static void insertSort(int[] array){for(int i=1;i<array.length;i++){//由數組1下標開始進行比較int tmp=array[i];int j=i-1;for(;j>=0;j--){if(tmp<array[j]){array[j+1]=array[j];//將j放入j+1位置}else{//進入else則為有序，break跳出嵌套循環break;}}//當嵌套的for循環一直在比較最小值tmp，知道為-1跳出循環，這里需要j+1//當大于時候，因為i-1賦值給j，break跳出后j需要+1下標值得到tmparray[j+1]=tmp;}}

時間復雜度:最壞情況時間復雜度為O(N*N)
最好情況時間復雜度為O(N)
空間復雜度O(1)
穩定排序

---

1.2 希爾排序

希爾排序又稱縮小增量法。
希爾排序的思想，定義一個整數，將待排序數組元素長度分成多個組，每一個組進行插入排序，重復上述分組，此時為預排序。當到達1時，將所有記錄好的元素在一組中進行排序。
每一次分組排序后都變為有序，每組數據由少變多，越來越有序。

劃分為n/2組進行比較，根據n/2的距離來劃分每一組的數量。

   public static void shellSort(int[] array){int gap=array.length;while(gap>1){gap/=2;//將數組/2，有多組變少組直到為1shell(array,gap);}}public static void shell(int[] arr,int gap){//從gap開始遍歷for(int i=gap;i<arr.length;i++){//獲取gap下標的值int tmp=arr[i];求i-gap個差距得到j值int j=i-gap;for(;j>=0;j-=gap){if(tmp<arr[j]){arr[j+gap]=arr[j];}else{break;}}arr[j+gap]=tmp;}}

時間復雜度O(N^1.25)
空間復雜度O(1)

---

二.選擇排序

2.1 單向選擇排序

單向選擇排序通過定義minIndex值來獲取最小的元素下標，然后與0下標進行交換

   public static void selectSort2(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,minIndex,i);}}

---

2.2雙向選擇排序

雙向選擇排序是我們通過定義起始位置和終點位置的下標作為條件，通過初始位置篩選最大值和最小值的下標，將最大值下標與尾部交換，最小值下標與初始位置交換，然后繼續重復上述，知道篩選完成。

這里如果max的最大值為0下標的時候，max已經被 minIndex交換，maxIndex等于minIndex獲取最大元素的下標值即可。

 public static void selectSort(int[] array){//起始位置和末尾的下標值int left=0;int right=array.length-1;while(left<right){//都從0下標開始比較int maxIndex=left;int minIndex=left;for(int i=left+1;i<=right;i++){if(array[i]<array[minIndex]) minIndex=i;if(array[i]>array[maxIndex]) maxIndex=i;}swap(array,left,minIndex);//如果0下標就是maxIndex的最大值，minIndex的位置就是maxIndex的最大值if(maxIndex==left)maxIndex=minIndex;swap(array,right,maxIndex);left++;right--;}}

時間復雜度：O(N^2)
空間復雜度：O(1)

---

2.3 堆排序

堆序詳情堆排序

 //創建二叉堆public static void createHeap(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 size) {int child=2*parent+1;while(child<size){if(child+1<size&&array[child]<array[child+1]){//child是左右孩子的最大值child=child+1;}if(array[child]>array[parent]){//交換孩子與父親swap(array,child,parent);//調整父親節點和孩子節點parent=child;child=(2*parent)+1;}else{break;}}}//根據創建好的大跟堆，通過最后一個下標與0下標交換后縮小堆的范圍，直到稱為有序數組public static void heapSort(int[] array){createHeap(array);int end=array.length-1;while(end>0){swap(array,0,end);siftDown(array,0,end);end--;}}

時間復雜度O(N*logN)
空間復雜度O(1)

---

三.交換排序

3.1 冒泡排序

冒泡排序是一種較為簡單的排序算法，它循環需要排序的元素，依次比較相鄰的兩個元素，如果順序錯誤就進行交換，直至沒有元素交換，完成排序，若對數組n個元素進行比較，則需要比較n-1次，最后一個元素已經被前n-1個元素排序好。
排序一次將len-1最大值放到最后，直到有序
本代碼中的flag來記錄是否有序，如果有序，則直接跳出循環。

 public static void bubbleSort(int[] array){for(int i=0;i<array.length-1;i++){boolean flag=false;//這里標記一下，每一趟中，給flag置為false，當每趟為有序后，則不進入if語句直接停止循環for(int j=0;j<array.length-1-i;j++){if(array[j]>array[j+1]){swap(array,j,j+1);flag=true;}}if(!flag){break;}}}

時間復雜度：最好情況下：O(n)
最壞情況下：O(n^2)
空間復雜度:O(1)
穩定排序

---

3.2 快速排序

3.2.1 Hoare排序

1.首先設定一個分界值，通過該分界值將數組分成左右兩部分。
2、將大于或等于分界值的數據集中到數組右邊，小于分界值的數據集中到數組的左邊。此時，左邊部分中各元素都小于分界值，而右邊部分中各元素都大于或等于分界值。
3、然后，左邊和右邊的數據可以獨立排序。對于左側的數組數據，又可以取一個分界值，將該部分數據分成左右兩部分，同樣在左邊放置較小值，右邊放置較大值。右側的數組數據也可以做類似處理。
4、重復上述過程，可以看出，這是一個遞歸定義。通過遞歸將左側部分排好序后，再遞歸排好右側部分的順序。當左、右兩個部分各數據排序完成后，整個數組的排序也就完成了。

這里定義一個left為左，right為右，將任意左右位置兩邊定義一個基準值，根據基準值的大小，直到left為大于基準值數，right為小于基準值數停下，若定義左邊為基準值則右邊先走，同理右邊為基準值左邊先走。

 //快速排序public static void quickSort(int[] array){//記錄左起始位置和右邊的結束位置進行遞歸quick(array,0,array.length-1);}
public static void inSert(int[] array,int left,int right){for(int i=left+1;i<=right;i++){int tmp=array[i];int j=i-1;for(;j>=left;j--){if(array[j]>tmp){array[j+1]=array[j];}else {break;}}array[j+1]=tmp;}}private static int middleNum(int[] array, int left, int right) {int mid=(left+right)/2;if(array[left]>array[right]){//說明left大if(array[right]>array[mid]){return right;} else if (array[left]<array[mid]) {return left;}else{return mid;}}else{//right大判斷中間值if(array[left]>array[mid]){return left;}else if(array[right]<array[mid]){return right;}else{return mid;}}}private static void quick(int[] array, int left, int right) {if(left>=right)return ;//說明兩個相遇或者走出范圍//當長度少時直接插入排序if(right-left+1<=10){inSert(array,left,right);return ;}int index = middleNum(array,left,right);System.out.println("index下標值:"+index);//用來交換left和right范圍內元素且最終將首位元素與相遇值交換swap(array,left,index);int pos=partitionPointer(array,left,right);//遞歸quick(array,left,pos-1);quick(array,pos+1,right);}private static int partitionHoare(int[] array, int left, int right) {int record=left;//記錄left最后交換int tmp=array[left];//比較大小while(left<right){while(left<right&&array[right]>=tmp){//右邊找到小于tmpright--;}while(left<right&&array[left]<=tmp){//左邊找到大于tmpleft++;}swap(array,left,right);}//這里left與right相遇swap(array,record,left);return left;}

時間復雜度：最壞情況下N*(logN)
最好情況下：O(N^2) 有序或者逆序情況下
空間復雜度:最好情況下O(logN)
最壞情況下：O(N) 有序或者逆序情況下
數據多時因遞歸可能容易棧溢出

---

3.2.2 挖坑法

1.由左或者右選出第一個坑位記錄元素值，放入key中，創建left和right對數組遍歷，當選左坑右走，右坑左走，直到right和left相遇后將記錄的坑位元素值放入即可。

 public static void quickSort(int[] array){//記錄左起始位置和右邊的結束位置進行遞歸quick(array,0,array.length-1);}public static void inSert(int[] array,int left,int right){for(int i=left+1;i<=right;i++){int tmp=array[i];int j=i-1;for(;j>=left;j--){if(array[j]>tmp){array[j+1]=array[j];}else {break;}}array[j+1]=tmp;}}private static int middleNum(int[] array, int left, int right) {int mid=(left+right)/2;if(array[left]>array[right]){//說明left大if(array[right]>array[mid]){return right;} else if (array[left]<array[mid]) {return left;}else{return mid;}}else{//right大判斷中間值if(array[left]>array[mid]){return left;}else if(array[right]<array[mid]){return right;}else{return mid;}}}private static void quick(int[] array, int left, int right) {if(left>=right)return ;//說明兩個相遇或者走出范圍if(right-left+1<=10){inSert(array,left,right);return ;}int index = middleNum(array,left,right);System.out.println("index下標值:"+index);//用來交換left和right范圍內元素且最終將首位元素與相遇值交換swap(array,left,index);int pos=partitionPointer(array,left,right);//遞歸quick(array,left,pos-1);quick(array,pos+1,right);}private static int partitionPit(int[] array, int left, int right) {int record=array[left];//記錄起始坑位while(left<right){while(left<right&&array[right]>=record){//右邊找到小于tmpright--;}//說明找到小于tmp的值array[left]=array[right];while(left<right&&array[left]<=record){//左邊找到大于tmpleft++;}//說明找到大于tmp的值array[right]=array[left];}//這里left與right相遇后將記錄的首個坑填入array[left]=record;return left;}

---

3.2.3 前后指針法

cur指向起始位置+1，pre是cur的前一位
判斷條件：如果cur找到基準值（最初位置key為5），前一項的條件滿足后prev向后走不為cur（為cur則不交換），直到prev在前cur在后且cur<基準值
cur如果大于基準值，直到cur找到小于基準值的數或者走完，直到遞歸調整為升序。

   public static void quickSort(int[] array){//記錄左起始位置和右邊的結束位置進行遞歸quick(array,0,array.length-1);}public static void inSert(int[] array,int left,int right){for(int i=left+1;i<=right;i++){int tmp=array[i];int j=i-1;for(;j>=left;j--){if(array[j]>tmp){array[j+1]=array[j];}else {break;}}array[j+1]=tmp;}}private static int middleNum(int[] array, int left, int right) {int mid=(left+right)/2;if(array[left]>array[right]){//說明left大if(array[right]>array[mid]){return right;} else if (array[left]<array[mid]) {return left;}else{return mid;}}else{//right大判斷中間值if(array[left]>array[mid]){return left;}else if(array[right]<array[mid]){return right;}else{return mid;}}}private static void quick(int[] array, int left, int right) {if(left>=right)return ;//說明兩個相遇或者走出范圍if(right-left+1<=10){inSert(array,left,right);return ;}int index = middleNum(array,left,right);System.out.println("index下標值:"+index);//用來交換left和right范圍內元素且最終將首位元素與相遇值交換swap(array,left,index);int pos=partitionPointer(array,left,right);//遞歸quick(array,left,pos-1);quick(array,pos+1,right);}private static int partitionPointer(int[] array, int left, int right) {//記錄cur的前一項int Prev=left;int cur=left+1;while(cur<=right){//cur與起始位置比較只有小于才能進行交換且prev不為curif(array[cur]<array[left]&&array[++Prev]!=array[cur]){swap(array,cur,Prev);}cur++;}//交換最后記錄的cur的值swap(array,left,Prev);return Prev;}

---

3.4 非遞歸快速排序

這里非遞歸排序的情況下，因為每次最左邊的數我們需要申請一個棧來記錄其區間值，出棧由區間值一步步縮小取值的范圍并進行交換，重復上述即可。

 public static void quickNor(int[] array){quickSortNor(array,0,array.length-1);}private static void quickSortNor(int[] array, int left, int right) {Stack<Integer> stack=new Stack<>();int pivot=partitionHoare(array,left,right);if(pivot>left+1){stack.push(left);stack.push(pivot-1);}if(pivot+1<right){stack.push(pivot+1);stack.push(right);}while(!stack.isEmpty()){right = stack.pop();left = stack.pop();pivot=partitionHoare(array,left,right);if(pivot>left+1){stack.push(left);stack.push(pivot-1);}if(pivot+1<right){stack.push(pivot+1);stack.push(right);}}

---

四.歸并排序

4.1 遞歸歸并排序

定義一個分界線mid來獲取其中間值，遞歸左邊和右邊，每次進入方法進行排序
將左起始到中間值與中間值到右側比較，創建一個數組來記錄，排序后放到數組中，最后讓原數組接收。

    public static void mergeSort(int[] array){mergeSortM(array,0,array.length-1);}private static void mergeSortM(int[] array, int left, int right) {//知道left和right相遇返回if(left>=right)return ;int mid=(left+right)/2;//以中間值作為分區，遞歸左邊和右邊mergeSortM(array,left,mid);mergeSortM(array,mid+1,right);//每次遞歸傳入后進行排序merge(array,left,mid,right);}private static void merge(int[] array, int left, int mid, int right) {int[] tmpArr=new int[right-left+1];//創建一個數組接收每一次遞歸的數組int k=0;//記錄左邊的起始位置與右邊起始位置int s1=left;int s2=mid+1;while(s1<= mid &&s2<= right){if(array[s1]<=array[s2]){tmpArr[k++]=array[s1++];}else{tmpArr[k++]=array[s2++];}}while(s1<= mid){tmpArr[k++]=array[s1++];}while(s2<= right){tmpArr[k++]=array[s2++];}for(int i=0;i<tmpArr.length;i++){//這里的left跟隨著mid改變，當遞歸右側時，left為mid+1array[i+left]=tmpArr[i];}}
}

時間復雜度：O(N*logN)
空間復雜度:O(logN)
穩定排序

---

4.2非遞歸歸并排序

以每組兩個形式分開進行排序，在以每組四個形式排序持續，直到為有序數組。
定義一個gap來每組存儲幾個數據，通過i下標遍歷將每組進行排序，而i下標遍歷是以組的形式遍歷的，這里直接i+gap*2。
這里left下標就是i，而mid下標是以gap第幾組+left-1獲取mid值，right值為mid+gap獲取最后下標，這里注意可能mid和right會超出范圍，如果超出范圍，一定是最后一個下標

  private static void merge(int[] array, int left, int mid, int right) {int[] tmpArr=new int[right-left+1];//創建一個數組接收每一次遞歸的數組int k=0;//記錄左邊的起始位置與右邊起始位置int s1=left;int s2=mid+1;while(s1<= mid &&s2<= right){if(array[s1]<=array[s2]){tmpArr[k++]=array[s1++];}else{tmpArr[k++]=array[s2++];}}while(s1<= mid){tmpArr[k++]=array[s1++];}while(s2<= right){tmpArr[k++]=array[s2++];}for(int i=0;i<tmpArr.length;i++){array[i+left]=tmpArr[i];}}public static void mergeNor(int[] array){int gap=1;//每組共有幾個數據while(gap<array.length){for(int i=0;i<array.length;i=i+gap*2){int left=i;int mid=left+gap-1;int right=mid+gap;if(mid>=array.length)mid=array.length-1;if(right>=array.length){right=array.length-1;}merge(array,left,mid,right);}gap*=2;}}

---

五.計數排序

計數排序是不需要對兩個數值進行比較的排序，他應用于一個數組中指定的區間范圍內。
取數組中最大值與最小值
最大值與最小值的差+1作為新的數組長度len不是指定范圍內的話，會浪費很多空間。
創建一個臨時數組大小為len來進行計數，將array[i]下標-最小值的差放入臨時數組中，循環直到結束
臨時數組中的計數i需要大于0才證明有計數最后將臨時數組給到array數組中即可，之需要將i差值+最小值得到array下標的值即可。

private static void sortCount(int[] array) {int maxVal=array[0];int minVal=array[0];for (int i = 0; i < array.length; i++) {if(array[i]>maxVal)maxVal=array[i];if(array[i]<minVal)minVal=array[i];}int len=maxVal-minVal+1;int[] count=new int[len];for(int i=0;i<array.length;i++){count[array[i]-minVal]++;}int index=0;for(int i=0;i<count.length;i++){while(count[i]>0){array[index]=i+minVal;index++;count[i]--;}}}

---

六.測試運行時間代碼

  // 有序public static void order(int[] arr){for(int i=0;i<arr.length;i++){arr[i]=i;}}//逆序public static void reverse(int[] arr){for(int i=0;i<arr.length;i++){arr[i]= arr.length-i;}}//無序public static void disorder(int[] arr){Random random=new Random();for(int i=0;i<arr.length;i++){arr[i]= random.nextInt(100);}}//測試public static void testSort1(int[] arr){int[] tmpArray= Arrays.copyOf(arr,arr.length);long startTime=System.currentTimeMillis();//開始結束記錄Sort.shellSort(tmpArray);long endTime=System.currentTimeMillis();System.out.println("希爾排序時間："+(endTime-startTime));}public static void testSort2(int[] arr){int[] tmpArray= Arrays.copyOf(arr,arr.length);long startTime=System.currentTimeMillis();//開始結束記錄Sort.inSert(tmpArray);long endTime=System.currentTimeMillis();System.out.println("插入排序時間："+(endTime-startTime));}public static void testSort3(int[] arr){int[] tmpArray= Arrays.copyOf(arr,arr.length);long startTime=System.currentTimeMillis();//開始結束記錄Sort.selectSort2(tmpArray);long endTime=System.currentTimeMillis();System.out.println("雙向選擇排序時間："+(endTime-startTime));}public static void testSort4(int[] arr){int[] tmpArray= Arrays.copyOf(arr,arr.length);long startTime=System.currentTimeMillis();//開始結束記錄Sort.bubbleSort(tmpArray);long endTime=System.currentTimeMillis();System.out.println("冒泡排序時間："+(endTime-startTime));}public static void testSort5(int[] arr){int[] tmpArray= Arrays.copyOf(arr,arr.length);long startTime=System.currentTimeMillis();//開始結束記錄Sort.heapSort(tmpArray);long endTime=System.currentTimeMillis();System.out.println("堆排序時間："+(endTime-startTime));}public static void testSort6(int[] arr){int[] tmpArray= Arrays.copyOf(arr,arr.length);long startTime=System.currentTimeMillis();//開始結束記錄Sort.quickSort(tmpArray);long endTime=System.currentTimeMillis();System.out.println("Hoare快速排序時間："+(endTime-startTime));}public static void testSort7(int[] arr){int[] tmpArray= Arrays.copyOf(arr,arr.length);long startTime=System.currentTimeMillis();//開始結束記錄Sort.quickSort(tmpArray);long endTime=System.currentTimeMillis();System.out.println("挖坑法快速排序時間："+(endTime-startTime));}public static void testSort8(int[] arr){int[] tmpArray= Arrays.copyOf(arr,arr.length);long startTime=System.currentTimeMillis();//開始結束記錄Sort.quickSort(tmpArray);long endTime=System.currentTimeMillis();System.out.println("前后指針法快速排序時間："+(endTime-startTime));}