难易程度：★
重要性：★★★★★
包含了：链表的快速排序和链表的归并排序
package com.sort;import java.util.Arrays;public class SortSummarize { public static void main(String[] args) { int[] a = {9,8,7,6,5,1,3,0,10,-1,99,-10}; int[] b = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,17,16}; b = a; print("选择排序 ",selectSort(b)); print("冒泡排序 ",bubbleSort(b)); print("插入排序 ",insertSort(b)); print("归并排序 ",mergeSort(b)); print("希尔排序 ",shellSort(b)); print("堆排序 ",heapSort(b)); print("快速排序 ",quickSort(b)); } /** * 冒泡排序算法：每次将最小的一个数”浮“上去 * 最好情况O(n),即数组本身有序 * 最坏情况O(n^2) */ public static int[] bubbleSort(int[] a) { a = Arrays.copyOf(a, a.length); int count = 0; boolean terminated = false; for(int i=0;i =i;j--) { count++; if(a[j]>a[j+1]) { swap(a,j+1,j); terminated = false; } } } System.out.println("冒泡排序比较次数: "+count); return a; } /** * 选择排序：每次选出待排序中最小的一个 */ public static int[] selectSort(int[] a) { a = Arrays.copyOf(a, a.length); int count = 0; for(int i=0;i =0&&a[j]>temp;j--) { count++; a[j+1] = a[j]; } a[j+1] = temp; } } System.out.println("插入排序比较次数: "+count); return a; } private static void swap(int[] a,int i,int j) { if (i==j) return; int temp = a[i]; a[i] = a[j]; a[j] = temp; } /** * 希尔排序 * @param a * @return */ public static int[] shellSort(int[] a) { a = Arrays.copyOf(a, a.length); int count = 0; int increment = a.length; do { increment = increment/3 + 1; for(int i=increment;i =0&&a[j]>temp;j -= increment) { count++; a[j+increment] = a[j]; } a[j+increment] = temp; } } }while(increment>1); System.out.println("希尔排序比较次数： "+count); return a; } /** * 堆排序 * @param a * @return */ public static int[] heapSort(int[] a) { a = Arrays.copyOf(a, a.length); int length = a.length; for(int i=length/2-1;i>=0;i--)//2*i+1<=length-1,最后一个有左孩子的节点 heapAdjust(a,i,length); for(int i=length-1;i>=0;i--) { swap(a,0,i); heapAdjust(a,0,i);// } return a; } //每次将以i为root的子树满足最大堆特性;i指向待调整的节点 private static void heapAdjust(int[] a,int i,int length) { int temp = a[i]; for(int j=2*i+1;j a[j])//如果有做右孩子，且右孩子比左孩子大 j++;//j指向左右孩子中值较大的一个 if(temp>=a[j]) break; a[i] = a[j]; i=j; } a[i] = temp; } public static int[] mergeSort(int[] a) { a = Arrays.copyOf(a, a.length); int[] aux = new int[a.length]; mergeSort(a,aux,0,a.length-1); return a; } private static void mergeSort(int[] a,int[] aux,int lo,int high) { if(lo>=high) return; int mid = (lo+high)/2; mergeSort(a,aux,lo,mid); mergeSort(a,aux,mid+1,high); merge(a,aux,lo,mid,high); } private static void merge(int[] a,int aux[],int lo,int mid,int high) { for(int i=lo;i<=high;i++) { aux[i] = a[i]; } int lo_h = mid+1; for(int i=lo;i<=high;i++) { if(lo>mid) a[i] = aux[lo_h++]; else if(lo_h>high) a[i] = aux[lo++]; else { if(aux[lo]<=aux[lo_h]) a[i] = aux[lo++]; else a[i] = aux[lo_h++]; } } } /** * 快速排序 * @param a * @return */ public static int[] quickSort(int[] a) { a = Arrays.copyOf(a, a.length); quickSort(a,0,a.length-1); return a; } private static void quickSort(int[] a,int low,int high) { if(low>=high) return; int partition = partition(a,low,high); quickSort(a,low,partition-1); quickSort(a,partition+1,high); } private static int partition(int[] a,int low,int high) { int tempt = a[low]; while(low =tempt) high--;// swap(a,low,high); a[low] = a[high]; while(low <=tempt) low++;// swap(a,low,high); a[high] = a[low]; } a[low] = tempt; return low; } private static void print(String str,int[] a) { System.out.println(str); for(int i=0;i 在理解的基础上掌握上述算法的实现，其中快速排序、归并排序、堆排序和链表的排序是重点中的重点，要求三分钟内可以正确手写实现任何一种排序算法，以及对应的复杂度、稳定性等特征。算法稳定性的考察也是面试中的另外一个重点，在理解的基础上，牢记下表：
扫描下方二维码，及时获取更多互联网求职面经、java、python、爬虫、大数据等技术，和海量资料分享：公众号后台回复“csdn”即可免费领取【csdn】和【百度文库】下载服务；公众号后台回复“资料”:即可领取5T精品学习资料、java面试考点和java面经总结，以及几十个java、大数据项目，资料很全，你想找的几乎都有