1.插入排序

1.1直接插入排序

給定一組數據，若數據只有一個肯定是有序的，我們將無序數據一個個插入到已有序的數據中。用i遍歷無序數據，j遍歷有序數據，找到合適插入位置，用tmp存放目標插入數據，將其與j對應數據對比，若大于j就放在j后面，小于j就把j數據往前移一位，j–再次判斷。具體代碼如下：

 public static void insertSort(int [] array){for(int i=1;i<array.length;i++){int tmp=array[i];//無序數據int j=i-1;for(;j>=0;j--){if(array[j]>tmp){array[j+1]=array[j];}else{array[j+1]=tmp;break;}}array[j+1]=tmp;}}

1.2希爾排序

希爾排序可以說時直插排序的plus版本，因為直接插入排序的特性是數據越有序排序越快，所以希爾排序會先把數據分成gap組，gap不固定,將每組中的數據進行排序，gap不斷減小，最終當gap等于1時排序完畢。具體代碼如下：

 public static void shellSort(int [] array){int gap=array.length;while(gap>1){gap=gap/2;shell111(array,gap);}}private static void shell(int [] array ,int gap){for(int i=gap;i<array.length;i++){int tmp=array[i];int j=i-gap;for(;j>=0;j=j-gap){if(array[j]>tmp){array[j+gap]=array[j];}else {array[j+gap]=tmp;break;}}array[j+gap]=tmp;}}

2.選擇排序

2.1直接選擇排序

思想：j從第一個開始遍歷，每次遍歷找到當前最小的值的下標，存入minIndex,然后跟下標為i的交換，隨后i++,直到整個數據遍歷完畢。具體代碼實現：

  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,minIndex,i);}}

2.2堆排序

思想：先把一組數據建成堆（升序就大根堆，降序就小根堆），然后將堆首元素與堆尾元素交換，因為堆首元素一定是max/min值，具體代碼如下：

 public static void heapSort(int[] array){createHeap111(array);int end=array.length-1;while(end>0){swap(array,end,0);siftDown111(array,0,end-1);end--;}}private static void createHeap(int [] array){int parent=(array.length-2)/2;for(;parent>=0;parent--){siftDown111(array,parent,array.length-1);}}private static void siftDown(int[] array, int parent,int end) {int child=parent*2+1;while(child<=end){if(child+1<=end&&array[child]<array[child+1]){child++;}if(array[child]>array[parent]){swap(array,parent,child);parent=child;child=2*parent+1;}else{break;}}}

3.交換排序

3.1冒泡排序

比較i趟，每一趟都將找出當前范圍的最小值/最大值，讓它排到末尾，也就是每一趟都定義一個j，j從0開始遍歷，如果j大于j+1就叫喚，然后j++，直到循環結束，這樣一趟下來就能將一個最值交換到末尾。具體代碼實現：

  public static void bubbleSort(int [] array){for(int i=0;i<array.length-1;i++){for(int j=0;j<array.length-1-i;j++){if(array[j]>array[j+1]){swap(array,j,j+1);}}}}

3.2快速排序（挖坑法）

思路;首先找出一個基準值tmp，通常由left對應值擔任，當left值賦給tmp后，left就可以看作一個坑，此時right往前走，直到找到比tmp小的值將這個值“填”到left坑中，此時right也成了一個坑，left開始走，直到找到比tmp大的值將其“填”到right，就這樣直到left和right相遇，這時將tmp“填”到相遇這個坑中。具體代碼如下：

public static void rapidSort(int [] array){rapid111(array,0,array.length-1);
}
private static void rapid(int [] array,int left,int right){if(left>=right){return;}int mid=getMid111(array,left,right);rapid111(array,0,mid-1);rapid111(array,mid+1,right);
}
private static int  getMid(int [] array,int left,int right){int tmp=array[left];while(left<right){while(left<right&&array[right]>tmp){right--;}array[left]=array[right];while(left<right&&array[left]<tmp){left++;}array[right]=array[left];}array[left]=tmp;return left;
}

4.歸并排序

思想：將一大組數據分解成小組數據，然后將小組數據有序，然后將小組數據合并為大組數據。
所以整個過程就分為：分割——合并
先說分割：結束條件——left==right。若不滿足，則計算mid，通過mid將該范圍分割為兩部分，具體代碼如下：

private static void mergeNum(int [] array,int left,int right){
if(left==right){
return ;}
int mid=(left+right)/2;
mergeNum(array,left,mid);
mergeNum(array,mid+1,right);
}

再說合并：假設有兩組數據，設計變量s1 e1,s2 e2表示兩組數據的頭和尾，然后創建一個數組，按從小到大將兩組數據放在數組中，然后將這個數組元素復制到array數組中對應的位置。具體代碼如下：

 private static void merge(int [] array,int left,int mid,int right){int [] num=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]){num[k++]=array[s1++];}else{num[k++]=array[s2++];}}//必有一敗  將剩余組數據放在數組while(s2<=e2){num[k++]=array[s2++];}while(s1<=e1){num[k++]=array[s1++];}//數組元素有序，還給arrayfor(int i=0;i<num.length;i++){array[i+left]=num[i];}}

5.計數排序

具體代碼如下：

 public static void countSort(int [] array){int left=0;int right=array.length-1;int maxVal=array[0];int minVal=array[0];for(int i=1;i<array.length;i++){if(array[i]>maxVal){maxVal=array[i];}if(array[i]<minVal){minVal=array[i];}}int [] number=new int[maxVal-minVal+1];//初始化計數數組for(int i=0;i<array.length;i++){int index=array[i];number[index-minVal]++;}//將計數數組元素打印到原數組中int index=0;for(int i=0;i<number.length;i++){while(number[i]!=0){array[index]=i+ minVal;index++;number[i]--;}}}