《排序的底层逻辑比较、交换与分治》0.总览一.插入排序1.1直接插入排序1.2希尔排序这个希尔排序其实就是直接插入排序的延伸,它是分成好多的组,好多个组在进行插入排序最后保底gap为1,其实就是直接插入排序二.选择排序2.1选择排序2.2堆排序三.交换排序3.1冒泡排序3.2快速排序3.3快速排序非递归实现四.归并排序4.1归并排序4.2归并排序非递归实现0.总览一.插入排序1.1直接插入排序1).首先我们将元素划分为两组,分别是已排序区间[0,bound)和待排序区间[bound,size)2).取待排序区间的第一个元素[bound]往已排序区间插入3).中间要与已排序区间的元素排大小,不断覆盖时间复杂度:o(n2)空间复杂度:o(1);是否稳定:稳定publicstaticvoidinsertSort(int[]arr){intbound1;for(;boundarr.length;bound){intvaluearr[bound];intcurbound-1;for(;cur0;cur--){if(arr[cur]value){arr[cur1]arr[cur];}else{break;}}arr[cur1]value;}}测试:publicstaticvoidmain(String[]args){// 测试直接插入排序int[]arrnewint[]{9,1,2,5,7,4,8,1,3,5};insertSort(arr);System.out.println(Arrays.toString(arr));}1.2希尔排序这个希尔排序其实就是直接插入排序的延伸,它是分成好多的组,好多个组在进行插入排序1)首先要分间隔,例如元素 9,1,2,5,7,4,8,1,3,5当gap取5可以看到明显有序多了看下标元素,然后再继续逐步缩小gap,一直到整体有序最后保底gap为1,其实就是直接插入排序时间复杂度取决于BAP,最好能达到o(n1.3)gap大:分组的元素比较少gap下:分组的元素整体比较有序是否稳定:不稳定二.选择排序2.1选择排序.选择排序的代码非常简单,就类似于打擂台,给一个最大值,谁打赢了就是最大的,;privatestaticvoidswap(int[]arr,inti,intj){inttemparr[i];arr[i]arr[j];arr[j]temp;}publicstaticvoidselectSort(int[]arr){intbound0;for(;boundarr.length;bound){intminindexbound;for(intcurbound1;curarr.length;cur){if(arr[cur]arr[minindex]){minindexcur;}}swap(arr,bound,minindex);}}2.2堆排序1)把数组创建成优先级队列堆;2)这里取从小到大的堆排序,将跟节点与最后一个有效节点heapSize节点交换,heapSiz–;3)不断循环;建堆publicstaticvoidcreatHeap(int[]arr){for(inti(arr.length-1-1)/2;i0;i--){shifDown(arr,arr.length,i);}}向下publicstaticvoidshifDown(int[]arr,intsize,introot){intparentroot;intchild2*parent1;while(childsize){if(child1sizearr[child1]arr[child]){childchild1;}if(arr[parent]arr[child]){swap(arr,parent,child);childparent;child2*parent1;}else{break;}}}堆排序// 堆排序publicstaticvoidheapSort(int[]arr){intheapSizearr.length;creatHeap(arr);for(inti0;iarr.length-1;i){swap(arr,0,heapSize-1);heapSize--;shifDown(arr,heapSize,0);}}测试// 测试堆排序heapSort(arr);System.out.println(Arrays.toString(arr));三.交换排序3.1冒泡排序时间复杂度:o(n2)空间复杂度:o(1)是否稳定:稳定// 冒泡排序publicstaticvoidbubbleSort(int[]arr){for(inti0;iarr.length;i){booleanflatrue;for(intj0;jarr.length-1-i;j){if(arr[j]arr[j1]){swap(arr,j,j1);flafalse;}}if(flatrue){break;}}}测试bubbleSort(arr);System.out.println(Arrays.toString(arr));3.2快速排序这个非常重要,至少在古法编程中是非常重要的;1)先写快速排序的辅助方法,寻找基准值2)根据基准值划分两个区间,然后递归的进行区分拆解;3)基准值取最右边// 快速排序publicstaticvoidquickSort(int[]arr){quickSortHelper(arr,0,arr.length-1);}publicstaticvoidquickSortHelper(int[]arr,intleft,intright){if(leftright){return;}// 先拿到基准值,分组大致整体有序intindexpartition(arr,left,right);quickSortHelper(arr,left,index-1);quickSortHelper(arr,index1,right);}publicstaticintpartition(int[]arr,intleft,intright){intlleft;intrright;while(lr){while(lrarr[l]arr[right]){l;}while(lrarr[r]arr[right]){r--;}swap(arr,l,r);}swap(arr,l,right);returnl;}测试// 测试快速排序quickSort(arr);System.out.println(Arrays.toString(arr));}3.3快速排序非递归实现1)先将区间左右界限依次入栈;2)找到基准值,把基准值的左右排好整体顺序3)注意栈是后进先出,不然出入栈会出现问题// 非递归快速排序;publicstaticvoidquickSortByloop(int[]arr){StackIntegerstacknewStack();stack.push(arr.length-1);stack.push(0);while(!stack.empty()){intleftstack.pop();intrightstack.pop();if(leftright){continue;}intindexpartition(arr,left,right);//先传右边区间stack.push(right);stack.push(index1);// 在传左边区间stack.push(index-1);stack.push(left);}}测试// 测试非递归快速排序quickSortByloop(arr);System.out.println(Arrays.toString(arr));四.归并排序归并排序和快速排序的思想是一样的,都是分治思想4.1归并排序1)图解手绘,可以看到先分出来,然后再往回归并,最后变得有序1)找到中间值,进行区间划分,一直到最后不能分2)运用递归不断划分区间// 归并排序publicstaticvoidmergeSort(int[]arr){mergeSortHelper(arr,0,arr.length);}publicstaticvoidmergeSortHelper(int[]arr,intleft,intright){if(right-left1){return;}intmid(leftright)/2;mergeSortHelper(arr,left,mid);mergeSortHelper(arr,mid,right);merge(arr,left,mid,right);}publicstaticvoidmerge(int[]arr,intleft,intmid,intright){int[]tempnewint[right-left];inttempIndex0;intcur1left;intcur2mid;while(cur1cur2cur2right){if(arr[cur1]cur2){arr[tempIndex]arr[cur1];tempIndex;}else{arr[tempIndex]arr[cur2];tempIndex;}}while(cur1cur2){arr[tempIndex]arr[cur1];tempIndex;}while(cur2right){arr[tempIndex]arr[cur2];tempIndex;}}4.2归并排序非递归实现这个很容易理解,就是合并尺寸为1的数组,有了尺寸为2的数组然后依次往后合并1)初始设置尺寸为1;2)合并完成在合并2的数组publicstaticvoidmergeSortByloop(int[]arr){intsize1;for(;sizearr.length;size*2){for(inti0;iarr.length;i2*size){intlefti;intmidisize;if(midarr.length){midarr.length;}intrighti2*size;if(rightarr.length){rightarr.length;}merge(arr,left,mid,right);}}}