插入排序
思路；定义 i 和 j，默认 i 前面的数都是有序的，j 定义为 i 的前一个数，把 i 的值给tmp，tmp与j对应的值进行比较，如果arr[j] > tmp,将arr[j] (大的数前移一位)，如下图
代码：
//插入排序//每次循环i前面的值都是有序的public void insertSort(int[] arr){for (int i = 1; i < arr.length; i++) {int j = i-1; //j定义为i的前一个数int tmp = arr[i]; //将arr[i]设置为临时变量，插入i前面有序的数组中for(;j>=0;j--){if(arr[j]>tmp){arr[j+1]=arr[j]; //前移}else {//代表前面已经有序了//arr[j+1]=tmp; //将tmp放回到原来的位置break;}}arr[j+1]=tmp; //跳出循环的时候，j已经小于0了,}}特点：时间复杂度
最好情况下：数据都是有序的情况下：O(N)
最坏情况下：数据完全逆序的O(n^2)
空间复杂度 O(1)
稳定性：稳定的
希尔排序
思路：数组分组进行排序，如下
10个数，分5组，组内进行排序，组内使用插入排序，
再分两组，组内进行排序，
最后分一组，排序完成
代码如下
//希尔排序public void shellSort(int[] arr){int gap = arr.length; //gap分的组，while (gap>1){gap = gap/3 +1 ;shell( arr , gap); //将分好的组进行插入排序}}private void shell(int[] arr, int gap){ //这里和插入排序思路一样，只是插入排序中， //我们按照1来进行计算，这里按照gap来进行计算//建议：先把插入排序写完，再写希尔排序for(int i = gap;i<arr.length;i++){int j = i-gap;int tmp = arr[i];for(;j>=0;j-=gap){if(arr[j]>tmp){arr[j+gap]=arr[j]; //大的数后移}else {break;}}arr[j+gap]=tmp;}}特点：不稳定排序，时间复杂度不好计算
选择排序
思路；定义一个i下标，和 j= i + 1，将i下标定义为minIndex，j向后遍历，寻找i后面比minIndex还要小的值，找到了就重新定义minIndex，循环结束后和i的位置进行交换
代码如下：
//选择排序public void selectSort(int[] arr){for(int i = 0;i<arr.length;i++){int j = i+1; //j在i的前一个数，j向后寻找比i下标值小的数，找到了就和 //i下标的值交换，找不到就向后移动int minIndex = i;for(;j<arr.length;j++){if(arr[j]<arr[minIndex]){minIndex=j; //跟新最小值下标}}//循环结束后，找到了i前面的最小值小标//将i的位置和最小值下标交换Swap(arr,i,minIndex);}}private static void Swap(int[] arr,int a,int b){int tmp = arr[a];arr[a]=arr[b];arr[b]=tmp;}特点：时间复杂度O(N^2)
空间复杂度O(1)
稳定性：不稳定
堆排序
堆排序需要将数组变成大根堆。
因为是大根堆，所以头节点是最大的，将头节点和尾节点进行交换，让后向下调整，每次调整后都将最大的节点放到尾部，调整完后就是从小到大的排序
代码如下
//堆排序//堆排序首先需要创建大根堆，public void headSort(int[] arr){//先将数组变成大根堆createBigHead(arr);int end = arr.length -1;while (end > 0){Swap(arr,0,end); //交换头和最后一位节点进行向下调整shiftDown(arr,0,end);end--;}}
//创建大根堆/采用向下调整的方法public void createBigHead(int [] arr){int end = arr.length;int parent = (arr.length-1-1)/2; //最后一颗子树的父亲节点，开始向下调整for(;parent>=0;parent--){shiftDown(arr,parent,end);}}private static void shiftDown(int[] arr,int parent,int end){int child = 2*parent +1 ; //左孩子节点while (child<end){//找出孩子节点中最大的一个，和父亲节点进行交换if(child+1<end&&arr[child]<arr[child+1]){child=child+1;}if(arr[child]>arr[parent]){Swap(arr,child,parent);//交换完成后父亲和孩子节点向下调整parent=child;child = 2*parent+1;}else {break;}}}快速排序
思路：
代码如下
public void quickSort(int [] arr){int start = 0; //设置开始和结束int end = arr.length-1; quick(arr,start,end); //调用方法}public void quick(int[] arr,int start,int end){if(start>=end){ //当开始大于结束时，递归结束return;}int pivot = partition(arr,start,end); quick(arr,start,pivot-1);quick(arr,pivot+1,end);}public int partition(int[] arr, int left ,int right){int tmp = arr[left]; //设置第一个值为基准int i = left; //保留第一个值的位置while (left<right){while (left<right&&arr[right]>=tmp){right--; //从右边开始找，找到比tmp小的值让后停下来} while (left<right&&arr[left]<=tmp){ //第一个判定条件是防止整个数组的值都比tmp小，从而导致数组越界left++; //从左边开始找，找到比tmp大的值让后停下来}Swap(arr,left,right); //交换，两个值，有可能left和right相等，相等就交换自己}Swap(arr,i,left); //把相遇的点和第一位交换return left; //返回left和right相遇的点}上述是快速排序的一种方法，下面是第二种方法，挖坑法
public int partition2(int [] arr,int left,int right){int tmp = arr[left];int i = left;while (left<right){while (left<right&&arr[right]>=tmp){right--;}arr[left]=arr[right]; //右边找到比tmp小的，直接交换while (left<right&&arr[left]<=tmp){left++;}arr[right]=arr[left]; //左边找到比tmp大的，直接交换}arr[left]=tmp; //将取出的tmp放回到空格处return left;}这里有个疑问，为啥
while (left<right&&arr[left]<=tmp){left++;
}
arr[right]=arr[left]; //左边找到比tmp大的，直接交换
while (left<right&&arr[right]>=tmp){right--;
}
arr[left]=arr[right]; //右边找到比tmp小的，直接交换
这两个循环换一下执行顺序就出错了，不理解我就死记了
特点：时间复杂度n*logn，是不稳定的排序
归并排序
思路：将数组分裂，分裂结束后再进行组内合并
合并的时候需要创建一个新的数组用来存放排序好的数组
//归并排序public void mergeSort(int[] arr){mergeFunc(arr,0,arr.length-1);}public void mergeFunc(int[] arr,int left,int right){if(left>=right){return;}//进行分裂int mid = (left+right)/2;mergeFunc(arr,left,mid); //分裂左边mergeFunc(arr,mid+1,right); //分裂右边//分裂完后进行合并merge( arr, left,mid,right);}public void merge(int[] arr,int left,int mid,int right){int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;int[] tmp = new int[(right-left)+1];int k = 0;while (s1<=e1&&s2<=e2){ //代表分裂的这段有数据//s1和s2进行比较if(arr[s1]<=arr[s2]){tmp[k++]=arr[s1++]; //谁小放谁进去}else {tmp[k++]=arr[s2++];}}while (s1<=e1){ //如果有一个没有数据了，直接把剩下的全放进去tmp[k++]=arr[s1++];}while (s2<=e2){tmp[k++]=arr[s2++];}//再把数据拷贝回原来的数组中for (int i = 0; i < k; i++) {arr[i+left]=tmp[i]; //拷贝回原来的数组}}
