面试手撕排序

手撕排序

（写的时候别忘了关提示，很多时候负面，给我错的代码还分心自己）

（小心别敲错一些变量，算法对了但是结果有问题，顺着逻辑梳理，看变量敲没敲错）

冒泡排序

原理：

扫描比较相邻不按顺序就交换（也可以理解为把第几大的依次放到后面）

packagesort;importjava.util.Scanner;publicclassmaopao{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt(),a[]=newint[n];for(inti=0;i<n;i++){a[i]=sc.nextInt();}for(inti=0;i<n;i++){for(intj=0;j<n-i;j++){if(j!=n-i-1&&a[j]>a[j+1]){inttemp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}for(inti=0;i<n;i++){System.out.print(a[i]+" ");}}}

选择排序

原理：

依次选最几小/大放到前面

packagesort;importjava.util.Scanner;publicclassxuanze{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt(),a[]=newint[n];for(inti=0;i<n;i++){a[i]=sc.nextInt();}for(inti=0;i<n;i++){intmin=Integer.MAX_VALUE,wz=-1;for(intj=i;j<=n-1;j++){if(a[j]<min){min=a[j];wz=j;}}intsum=a[i];a[i]=min;a[wz]=sum;}for(inti=0;i<n;i++){System.out.print(a[i]+" ");}}}

快速排序

原理：

分治+分区，核心是分区，每次选基准值，要保证基准最左边的都比他小，右边的都比他大，可以理解为每次排好基准值对应的那个元素，分治就全排完。

packagesort;importjava.util.Scanner;publicclassquick{staticintn,a[]=newint[100005];publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);n=sc.nextInt();for(inti=0;i<n;i++){a[i]=sc.nextInt();}sort(0,n-1);for(inti=0;i<n;i++){System.out.print(a[i]+" ");}}staticvoidsort(intl,intr){if(l>=r)return;intzj=kp(l,r);sort(l,zj-1);sort(zj+1,r);}staticintkp(intl,intr){intsum=a[l];while(l<r){while(l<r&&a[r]>sum){r--;}if(l<r){a[l]=a[r];l++;}while(l<r&&a[l]<sum){l++;}if(l<r){a[r]=a[l];r--;}}a[l]=sum;returnl;}}

归并排序

原理：

分治+合并两个有序数组，合并细节可能有点麻烦，hot100应该都做过来链表版本的合并吧，这里就是换成了数组，主要也是注意一些边界细节啥的

packageguibing;importjava.util.Scanner;publicclassguibing{staticintn,a[]=newint[100005];publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);n=sc.nextInt();for(inti=0;i<n;i++){a[i]=sc.nextInt();}guib(0,n-1);for(inti=0;i<n;i++){System.out.print(a[i]+" ");}}staticvoidguib(intl,intr){if(l>=r)return;intmid=l+(r-l)/2;guib(l,mid);guib(mid+1,r);intcd1=mid-l+1,cd2=r-mid,az[]=newint[cd1],ar[]=newint[cd2],f1=0,f2=0,qd=l,f3=0,f4=0;for(inti=l;i<=mid;i++){az[f1++]=a[i];}for(inti=mid+1;i<=r;i++){ar[f2++]=a[i];}while(f3<cd1&&f4<cd2){if(az[f3]<=ar[f4]){a[qd++]=az[f3++];}else{a[qd++]=ar[f4++];}}while(f3<cd1){a[qd++]=az[f3++];}while(f4<cd2){a[qd++]=ar[f4++];}}}