1.插入排序

插入排序的主要思想是額外申請一個空間cur，讓cur一開始等于數組的第1號位置,設置i=1，讓i-1的元素與其比較，如果arr[i-1]>arr[i]，就讓arr[i+1] = arr[i]，當進行到最后一次對比結束，i=-1,再讓arr[i+1] = cur。

?
private static void insertsort(int[] arr) {for (int i = 1; i < arr.length; i++) {int cur = arr[i];int j = i-1;for ( ;j>=0; j--) {if(cur>arr[j]){arr[j+1] = arr[j];}else{break;}}arr[j+1] = cur;}}?

排序算法的特點是序列越有序，時間效率越高，下面的希爾排序也體現出來。

時間復雜度：O(n^2)

空間復雜度：O（1）

是一種穩定的排序算法。

2.希爾排序

希爾排序的思想是設置一個常量gap，將數組每個相距gap距離的兩個數進行分組，然后組內進行排序，每進行一次gap排序后，將gap/2，直到gap為1，排序完成。

    private static void shellsort(int[] arr) {int gep = arr.length;while(gep>1){gep/=2;shell(arr,gep);}}private static void shell(int[] arr, int gep) {for(int i = gep;i< arr.length;i++){int cur = arr[i];int j = i-gep;for(;j>=0;j-=gep){if(cur<arr[j]){arr[j+gep] = arr[j];}else{break;}}arr[j+gep] = cur;}}

這里的希爾排序是先拿出gap間距，進行直接插入排序，所以shell方法的實現和插入排序相似。

希爾排序是對插入排序的優化，當gap>1時，都是對序列有序化，直到gap=1時，數組已經趨于有序，就會排序很快，對于整體來說，就有一個優化的效果。

希爾排序的時間復雜度不好計算，因為每次數組長度不確定，gap的取值不確定。

希爾排序的穩定性：不穩定。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

3.選擇排序

選擇排序非常好理解，類似于打擂臺，取出一個元素，將它設置為擂主，依次取后面的元素進行比較，如果小于擂主，就進行交換，如果大于，就繼續遍歷，直到遍歷結束。

private static void selectsort(int [] arr) {for(int i= 0;i< arr.length;i++){for (int j = i+1; j < arr.length; j++) {if(arr[i]>arr[j]){int tem = arr[i];arr[i] = arr[j];arr[j] = tem;}}}}

選擇排序非常好理解，但效率不是特別高，實際很少使用。

時間復雜度：O（n^2）

空間復雜度：O（1）

不穩定。

4.堆排序

堆排序是基于堆這種數據結構實現的，首先要將數組進行建大堆操作，設置bound記錄末尾的位置，然后將數組的頭和bound位置元素交換，此時堆中最大的元素在數組末尾，bound--，此時[0，bound]位置就是待排序位置，在進行向下調整，重復過程。

private static void heapsort(int[] arr) {//建堆creatheap(arr);int bound = arr.length-1;for (int i = 0; i < arr.length; i++) {int tem = arr[0];arr[0] = arr[bound];arr[bound] = tem;bound--;shifsort(arr,0,bound);}}private static void shifsort(int[] arr, int index, int bound) {int parent = index;int child = 2*parent + 1;while(child<bound){if(child+1<bound&&arr[child+1]>arr[child]){child+=1;}if(arr[child]>arr[parent]){int tem = arr[child];arr[child] = arr[parent];arr[parent] = tem;}else{break;}parent = child;child = 2*parent + 1;}}private static void creatheap(int[] arr) {for(int i = (arr.length-1-1)/2;i>=0;i--){shifsort(arr,i,arr.length);}}

升序要進行建大堆，降序則建小堆。

堆排序使用堆來調整數據，效率就快很多。

時間復雜度：O(n*logn)

空間復雜度：O(1)

穩定性：不穩定。

5.冒泡排序

冒泡排序非常好理解，我們取數組最后一個元素，依次與前面的數對比。

 private static void pooubsort(int[] arr) {for (int i = 0; i < arr.length; i++) {for (int j = arr.length-1; j > 0 ; j--) {if(arr[j-1] > arr[j]){int tem = arr[j-1];arr[j-1] = arr[j];arr[j] = tem;}}}}

時間復雜度：O(n^2)

空間復雜度：O（1）

穩定性：穩定。

6.快速排序

快速排序是一種非常重要的排序，這里提供Hoare法和挖坑法，Hoare法的思想是取數組最左/右邊的值，將它設為基準值，先從右邊的第一個值開始，找到比基準值小的值，停下，開始從最左邊開始找? 比基準值大的值，也停下，交換兩個數，當left和right重合，交換基準值和兩下標重合位置的值。此時就完成了一次尋找。接下來就是對區間[left,pos-1]和[pos+1,right]分別進行上述調整。因此快排要運用到遞歸。

//快速排序Hoare法private static void quicksort1(int[] arr) {quick(arr,0,arr.length-1);}private static void quick(int[] arr, int left, int right) {if(left>=right){return;}int pos = parttion(arr,left,right);quick(arr,left,pos-1);quick(arr, pos+1, right);}private static int parttion(int[] arr, int left, int right) {int k = arr[left];int i = left;while(left<right){while(left<right&&arr[right]>=k){right--;}while(left<right&&arr[left]<=k){k++;}sweap(arr,left,right);}sweap(arr,left,i);return left;}private static void sweap(int[] arr, int left, int right) {int tem = arr[left];arr[left] = arr[right];arr[right] = tem;}

挖坑法：挖坑法是先將第一個數據放到一個臨時變量，形成一個坑位，從最右邊開始找比基準值小的數，讓它進入坑位，形成新的坑位，再從左邊開始找比基準值大的數，進坑。

private static void quicksort2(int[] arr) {quick1(arr,0,arr.length-1);}private static void quick1( int []arr,int left,int right) {if(left>=right){return;}int pos = parttion1(arr,left,right);quick1(arr,left,pos-1);quick1(arr,pos+1,right);}private static int parttion1(int[] arr, int left, int right) {int key = arr[left];while(left<right){while(left<right&&arr[right]>=key){right--;}arr[left] = arr[right];while(left<right&&arr[left]<=key){left++;}arr[right] = arr[left];}arr[left] = key;return left;}

時間復雜度：O（n*logn）

空間復雜度：O（logn）

穩定性：不穩定

7.歸并排序

歸并排序也是通過遞歸（分治法）進行排序，通過將數組分組，使子序列有序，然后讓子序列合并。

 private static void mergesort(int[] arr) {mergesortfunc(arr,0,arr.length-1);}private static void mergesortfunc(int [] arr,int left,int right) {if(left>=right){return;}int mid = (left+right)/2;mergesortfunc(arr,left,mid);mergesortfunc(arr,mid+1,right);merger(arr,left,mid,right);}private static void merger(int[] arr, int left, int mid, int right) {int s1 = left;int s2 = mid+1;int [] newarry = new int [right-left+1];int k = 0;while(s1<=mid&&s2<=right){if(arr[s1]>=arr[s2]){newarry[k] = arr[s2];k++;s2++;} else if (arr[s2]>arr[s1]) {newarry[k] = arr[s1];k++;s1++;}}while(s1<=mid){newarry[k++] = arr[s1++];}while(s2<=right){newarry[k++] = arr[s2++];}for (int i = 0; i < newarry.length; i++) {arr[i+left] = newarry[i];}}

歸并排序的缺點在于空間復雜度為O（N），歸并排序的思考更多在于磁盤外的排序，因為內存無法存儲這么多數據，所以要進行外部排序，歸并排序是最常用的外部排序。

時間復雜度：O(n*logn)

空間復雜度：O(N)

穩定性：穩定

8.快速排序的非遞歸實現

快排：首先要有一個棧，設置一個內置類，類中有left,right，將初始的范圍[0,arr.length-1]入棧。

 public Range(int right, int left) {this.right = right;this.left = left;}}private static void quicksortbyLoop(int[] arr) {Stack<Range> stack = new Stack<>();stack.push(new Range(0,arr.length-1));while(!stack.isEmpty()){Range range = stack.pop();while(range.left>=range.right){continue;}int pos = parttion(arr,range.left, range.right);stack.push(new Range(range.left,pos-1));stack.push(new Range(pos+1,range.right));}}