Java 面试手撕排序封神版！八大排序算法（快排 / 堆排 / 归并）手敲无 bug，面试直接默写

面试手撕排序整理完整版面试中常考的手撕排序算法整理可以直接照抄包含快速排序归并排序堆排序希尔排序直接插入排序选择排序计数排序冒泡排序快速排序丐版实现publicstaticvoidquickSort(ArrayListIntegerarr,intbegin,intend){if(beginend){return;}intleftbegin;intrightend;intpivotarr.get(begin);//pivot是基准值while(leftright){while(leftrightarr.get(right)pivot){right--;}while(leftrightarr.get(left)pivot){left;}Collections.swap(arr,left,right);}Collections.swap(arr,left,begin);quickSort(arr,begin,left-1);quickSort(arr,left1,end);}小区间优化 随机数优化避免递归过深publicstaticvoidquickSort(ArrayListIntegerarr,intbegin,intend){if(beginend){return;}if(end-begin110){insertSort(arr,begin,end);return;}intleftbegin;intrightend;intrandrandom.nextInt(end-begin1)begin;Collections.swap(arr,rand,begin);intpivotarr.get(begin);//pivot是基准值while(leftright){while(leftrightarr.get(right)pivot){right--;}while(leftrightarr.get(left)pivot){left;}Collections.swap(arr,left,right);}Collections.swap(arr,left,begin);quickSort(arr,begin,left-1);quickSort(arr,left1,end);}这里也可以不采取随机数其他方法也可以比如三数取中。核心思想就是避免有序数组对排序造成递归过深的问题堆排序publicstaticvoidheapSort(ArrayListIntegerarr){intnarr.size();for(inti(n-1-1)/2;i0;i--){adjustDown(arr,i,arr.size()-1);}intendarr.size()-1;while(end0){Collections.swap(arr,0,end);end--;adjustDown(arr,0,end);}}privatestaticvoidadjustDown(ArrayListIntegerarr,intparent,intend){intchildparent*21;while(childend){if(child1endarr.get(child)arr.get(child1)){child1;}if(arr.get(child)arr.get(parent)){Collections.swap(arr,child,parent);parentchild;childparent*21;}else{break;}}}归并排序publicstaticvoidmergeSort(ArrayListIntegerarr){ArrayListIntegerbuffernewArrayList(arr);_mergeSort(arr,0,arr.size()-1,buffer);}publicstaticvoid_mergeSort(ArrayListIntegerarr,intbegin,intend,ArrayListIntegerbuffer){if(beginend){return;}intmidi(beginend)/2;_mergeSort(arr,begin,midi,buffer);_mergeSort(arr,midi1,end,buffer);intleftbegin;intrightmidi1;intibegin;while(leftmidirightend){if(arr.get(left)arr.get(right)){buffer.set(i,arr.get(left));}else{buffer.set(i,arr.get(right));}}while(leftmidi){buffer.set(i,arr.get(left));}while(rightend){buffer.set(i,arr.get(right));}for(intjbegin;jend;j){arr.set(j,buffer.get(j));}}希尔排序publicstaticvoidshellSort(ArrayListIntegerarr){intnarr.size();intgaparr.size();while(gap1){gapgap/2;for(inti0;in-gap;i){intendi;inttmparr.get(endgap);while(end0){if(arr.get(end)tmp){arr.set(endgap,arr.get(end));end-gap;}else{break;}}arr.set(endgap,tmp);}}}插入排序publicstaticvoidinsertSort(ArrayListIntegerarr){for(inti0;iarr.size()-1;i){intendi;inttmparr.get(end1);while(end0){if(arr.get(end)tmp){arr.set(end1,arr.get(end));end--;}else{break;}}arr.set(end1,tmp);}}选择排序publicstaticvoidselectSort(ArrayListIntegerarr){intleft0,rightarr.size()-1;for(inti0;iarr.size();i){if(leftright){break;}intminleft;intmaxleft;for(intjleft;jright;j){if(arr.get(j)arr.get(min)){minj;}if(arr.get(j)arr.get(max)){maxj;}}Collections.swap(arr,left,min);if(maxleft){maxmin;}Collections.swap(arr,right,max);left;right--;}}计数排序publicstaticvoidcountSort(ArrayListIntegerarr){intmaxInteger.MIN_VALUE,minInteger.MAX_VALUE;for(inti0;iarr.size();i){if(arr.get(i)max){maxarr.get(i);}if(arr.get(i)min){minarr.get(i);}}intsizemax-min1;int[]bufnewint[size];for(inti0;iarr.size();i){buf[arr.get(i)-min];}intm0;for(intn0;nsize;n){while(buf[n]!0){arr.set(m,nmin);buf[n]--;}}}冒泡排序publicstaticvoidbubbleSort(ArrayListIntegerarr){if(arr.size()1){return;}for(inti0;iarr.size();i){booleanflagfalse;for(intj1;jarr.size()-i;j){if(arr.get(j-1)arr.get(j)){Collections.swap(arr,j-1,j);flagtrue;}}if(flagfalse){break;}}}