排序算法总结java
难易程度：★
重要性：★★★★★
包含了：链表的快速排序和链表的归并排序
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<a.length-1&&!terminated;i++) {terminated = true;for(int j=a.length-2;j>=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<a.length-1;i++) {int min = a[i];int minIndex = i;for(int j=i+1;j<a.length;j++) {count++;if(a[j]<min) {minIndex = j;min = a[j];}}swap(a,i,minIndex);}System.out.println("选择排序比较次数: "+count);return a;}public static int[] insertSort(int[] a) {a = Arrays.copyOf(a, a.length);int count = 0;for(int i=1;i<a.length;i++) {// i之前有序,i指向待排序的元素if(a[i]<a[i-1]) {int temp = a[i];int j = i-1;//j指向当前元素的前一个for(;j>=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<a.length;i=i+increment) {if(a[i]<a[i-increment]) {int temp = a[i];int j=i-increment;for(;j>=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<length;j=2*i+1){//刚开始时指向左孩子if(j+1<length && a[j+1]>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++];elsea[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<high) {while(low<high&&a[high]>=tempt)high--;// swap(a,low,high);a[low] = a[high];while(low<high&&a[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<a.length;i++)System.out.print(a[i]+" ");System.out.println("\n");}/*** 下面是链表的快速排序* @param str* @param a*/public static ListNode quickSort(ListNode begin, ListNode end) {//判断为空，判断是不是只有一个节点if (begin == null || end == null || begin == end)return begin;//从第一个节点和第一个节点的后面一个几点//begin指向的是当前遍历到的最后一个<= nMidValue的节点ListNode first = begin;ListNode second = begin.next;int nMidValue = begin.val;//结束条件，second到最后了while (second != end.next && second != null) {//结束条件//一直往后寻找<=nMidValue的节点，然后与fir的后继节点交换if (second.val < nMidValue) {first = first.next;//判断一下，避免后面的数比第一个数小，不用换的局面if (first != second) {int temp = first.val;first.val = second.val;second.val = temp;}}second = second.next;}//判断，有些情况是不用换的，提升性能if (begin != first) {int temp = begin.val;begin.val = first.val;first.val = temp;}//前部分递归quickSort(begin, first);//后部分递归quickSort(first.next, end);return begin;}/*** 链表的归并排序*/public ListNode sortList1(ListNode head) {if(head==null||head.next==null) return head;quickSort(null,null);return mergeSort(head);}private ListNode mergeSort(ListNode head){if(head==null || head.next==null) return head;ListNode mid = getMid(head);ListNode second = mid.next;mid.next = null;ListNode left = mergeSort(head);ListNode right = mergeSort(second);return merge(right,left);}private ListNode merge(ListNode l1,ListNode l2){ListNode dummy = new ListNode(0);ListNode cur = dummy;while(l1!=null&&l2!=null){if(l1.val<=l2.val){cur.next = l1;l1 = l1.next;}else{cur.next = l2;l2 = l2.next;}cur = cur.next;}if(l1!=null)cur.next = l1;elsecur.next = l2;return dummy.next;}private ListNode getMid(ListNode head){if(head==null ||head.next==null) return head;ListNode slow = head;ListNode faster = head.next;while(faster!=null&&faster.next!=null){slow = slow.next;faster = faster.next.next;}return slow;}}
在理解的基础上掌握上述算法的实现，其中快速排序、归并排序、堆排序和链表的排序是重点中的重点，要求三分钟内可以正确手写实现任何一种排序算法，以及对应的复杂度、稳定性等特征。算法稳定性的考察也是面试中的另外一个重点，在理解的基础上，牢记下表：
扫描下方二维码，及时获取更多互联网求职面经、java、python、爬虫、大数据等技术，和海量资料分享：
公众号菜鸟名企梦后台发送“csdn”即可免费领取【csdn】和【百度文库】下载服务；
公众号菜鸟名企梦后台发送“资料”:即可领取5T精品学习资料、java面试考点和java面经总结，以及几十个java、大数据项目，资料很全，你想找的几乎都有
扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）
- 日理万妓
野性酷女
系统管理员
骑猪看日落
灰太狼
还没有评论，来说两句吧...