java核心技术|面试手撕代码总结(一)-排序篇

1.冒泡排序:
(1)从右往左进行比较,小的冒泡

public void bubbleSort(int[] a,int n){ for(int i=0; i i; j--) { // 比较相邻的元素,如果前面的数大于后面的数,则交换 if(a[j-1]>a[j]){ int temp=a[j-1]; a[j-1]=a[j]; a[j]=temp; } } } for (int i = 0; i < n; i++) { System.out.print(a[i]+" "); } }

(1)从左往右进行比较,大的沉底
public void bubbleSort(int[] a,int n){ for(int i=0; i
2.快速排序:
public static void sort(int[] a,int low,int high){ if(low>=high){ return; } int start=low; int end=high; int key=a[start]; while(end>start){ while(end>start&&a[end]>=key){ end--; } if(a[end]<=key){ int temp=a[end]; a[end]=a[start]; a[start]=temp; }while(end>start&&a[start]<=key){ start++; } if(a[start]>=key){ int temp=a[start]; a[start]=a[end]; a[end]=temp; }} if (low

3.直接选择排序
public static void selectionSort(int[] array) { int n= array.length; for (int i = 0; i < n; i++) { int min=i; for (int j = i; j < n; j++) { if (array[j]

4.堆排序
public static void adjustMinHeap(int[] a,int pos,int len){ int temp,child; for(temp=a[pos]; 2*pos+1<=len; pos=child){ child=2*pos+1; //孩子节点 if(childa[child+1]) child++; if(a[child]=0; i--) adjustMinHeap(array,i,len-1); //首先进行比较,小值进行浮现 for(i=len-1; i>=0; i--){ int temp=array[0]; //把最小的值与最后面的值交换,相当于小值沉底,然后固定这最小值 array[0]=array[i]; array[i]=temp; adjustMinHeap(array, 0, i-1); } }

5.插入排序:
public static void sort(int[] a){ if(a!=null){ for (int i = 1; i < a.length; i++) { int temp=a[i]; int j=i; if(a[j-1]>temp){ while(j>=1&&a[j-1]>temp){ a[j]=a[j-1]; j--; } } a[j]=temp; } } for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } }

6.希尔排序
public static void ShellSort(int[] array) { int n = array.length; int temp, gap = n / 2; while (gap > 0) { for (int i = gap; i < n; i++) { temp = array[i]; int j = i - gap; while (j >= 0 && array[j] > temp) { array[j + gap] = array[j]; j -= gap; } array[j + gap] = temp; } gap /= 2; } for (int i = 0; i < n; i++) { System.out.println(array[i]); } }

【java核心技术|面试手撕代码总结(一)-排序篇】7.归并排序
public static void mergeSort(int[] arr) { mSort(arr, 0, arr.length-1); } public static void mSort(int[] arr, int left, int right) { if(left >= right) return ; int mid = (left + right) / 2; mSort(arr, left, mid); //递归排序左边 mSort(arr, mid+1, right); //递归排序右边 merge(arr, left, mid, right); //合并 } public static void merge(int[] arr, int left, int mid, int right) { //[left, mid] [mid+1, right] int[] temp = new int[right - left + 1]; //中间数组 int i = left; int j = mid + 1; int k = 0; while(i <= mid && j <= right) { if(arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } }while(i <= mid) { temp[k++] = arr[i++]; }while(j <= right) { temp[k++] = arr[j++]; }for(int p=0; p

    推荐阅读