插入排序

思路；定义 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];        //拷贝回原来的数组}}