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]--;}}}