几大排序算法的Java实现

很多的面试题都问到了排序算法，中间的算法和思想比较重要，这边我选择了5种常用排序算法并用Java进行了实现。自己写一个模板已防以后面试用到。大家可以看过算法之后，自己去实现一下。1.冒泡排序：大数向下沉，小数向上浮。package TestProject;/** * 冒泡排序 * @author xuhui * */public class SortAll {public static void main（String[] args）{int[] a = {0,8,1,2,8,6,1};bubbleSort（a）;for（int i=0;i<a.length;i++）{System.out.print（a[i]+" "）;}}public static void bubbleSort（int[] a）{int len = a.length;//数组长度for（int i=0;i<len;i++）{//每趟把最大数下沉到数组最后面for（int j=0;j<len-1;j++）{if（a[j+1]<a[j]）{//如果数组后面的数比前面的小，则往后换下沉int temp = a[j];a[j] = a[j+1];a[j+1] = temp;}}}}}1.1冒泡排序的优化一：用一个变量记录每趟大数下沉的位置，标量值说明该变量后面数组已排序完成。package TestProject;/** * 冒泡排序优化 * @author xuhui * */public class SortAll {public static void main（String[] args）{int[] a = {0,8,1,2,8,6,1};bubbleSort_1（a）;for（int i=0;i<a.length;i++）{System.out.print（a[i]+" "）;}}public static void bubbleSort_1（int[] a）{int len = a.length;//数组长度int i = len-1;while（i>0）{int pos = 0;for（int j=0;j<i;j++）{//只需排序a[0,1,...,pos]if（a[j]>a[j+1]）{int temp = a[j];a[j] = a[j+1];a[j+1] = temp;pos = j;}}i = pos;//下一摊，a[pos+1,...,len-1]已排序好}}}1.2冒泡排序的优化二：将大数向下沉同时小数向下浮。package TestProject;/** * 冒泡排序优化 * @author xuhui * */public class SortAll {public static void main（String[] args）{int[] a = {0,8,1,2,8,6,1};bubbleSort_2（a）;for（int i=0;i<a.length;i++）{System.out.print（a[i]+" "）;}}public static void bubbleSort_2（int[] a）{int len = a.length;//数组长度int hight = len-1;int low = 0;while（low<hight）{for（int i=low;i<hight;i++）{//大数下沉if（a[i]>a[i+1]）{int temp = a[i];a[i] = a[i+1];a[i+1] = temp;}}hight--;//每趟数组大数下沉到无序数组最后面，后面大数已排序好（这地方可以优化，可以每趟给一个变量记录其最后交换的位置，说明变量后面的数组已排序好）for（int i=hight;i>low;i--）{//小数上浮if（a[i]<a[i-1]）{int temp = a[i];a[i] = a[i-1];a[i-1] = temp;}}low++;//每趟数组小数上浮到无序数组最前面，前面的小数已排序好}}}2.插入排序：大致思想就是两个数组，一个有序数组，一个无序数组，将无序数组插入有序数列中。其中将a[0]看成有序数组,a[1,...,len-1]看成无序数组。package TestProject;/** * 插入排序 * @author xuhui * */public class SortAll {public static void main（String[] args）{int[] a = {0,8,1,2,8,6,1};insertSort（a）;for（int i=0;i<a.length;i++）{System.out.print（a[i]+" "）;}}public static void insertSort（int[] a）{int len = a.length;//数组长度for（int i=1;i<len;i++）{int temp = a[i];int j;for（j=i-1;j>=0;j--）{//将a[i]插入a[0,..,i]序列中if（a[j]<=temp）{break;}else{a[j+1]=a[j];//插入有序数组时（从小到大），如果插入的数比当前数小，则向前插入，此时的数向后挪一位}}a[j+1] = temp;//此时插入数在有序数列的位置}}}3.选择排序：每趟选择出最小的数放在数组最前面。package TestProject;/** * 选择排序 * @author xuhui * */public class SortAll {public static void main（String[] args）{int[] a = {0,8,1,2,8,6,1};selectSort（a）;for（int i=0;i<a.length;i++）{System.out.print（a[i]+" "）;}}public static void selectSort（int[] a）{int len = a.length;for（int i=0;i<len;i++）{int min = selectMin（a,i,len-1）;int temp = a[min];//将无序数列的最小值换到前面a[min] = a[i];a[i] = temp;}}public static int selectMin（int[] a,int s,int t）{int count = s;for（int i=s;i<=t;i++）{if（a[i]<a[count]）count=i;}return count;}}3.1选择排序优化一：二元选择排序，每次将无序数列的最大值换到后面，将最小值换到前面。package TestProject;/** * 选择排序 * @author xuhui * */public class SortAll {public static void main（String[] args）{int[] a = {8,1,0,2,8,6,1};selectSort（a）;for（int i=0;i<a.length;i++）{System.out.print（a[i]+" "）;}}public static void selectSort（int[] a）{int len = a.length;int l = 0;int h = len-1;while（l<h）{int[] count = selectMinMax（a,l,h）;int temp = a[count[0]];//将无序数列的最小值换到前面a[count[0]] = a[l];a[l] = temp;if（count[1]==l）{//count[0]为无序数列的最小值位置，count[1]为无序数列的最大值位置，如果当count[0]挪到l位置时（a[1,..,l-1]为有序序列），可能会出现l位置就是最大值位置temp = a[count[0]];a[count[0]] = a[h];a[h] = temp;}else{temp = a[count[1]];a[count[1]] = a[h];a[h] = temp;}l++;h--;}}public static int[] selectMinMax（int[] a,int s,int t）{int[] count = {s,t};//count[0]-min,count[1]-maxfor（int i=s;i<=t;i++）{if（a[i]<a[count[0]]）{count[0]=i;}if（a[i]>a[count[1]]）{count[1]=i;}}return count;}} 4.堆排序：首先建立一个最大堆，堆顶元素为最大值，每次将堆顶元素换到数组后面，这样一次循环就可以得到从小到大的有序数组。package TestProject;/** * 堆排序 * @author xuhui * */public class SortAll {public static void main（String[] args）{int[] a = {0,8,1,2,8,6,1};int len = a.length;for（int i=（len/2-1）;i>=0;i--）{//建立一个最大堆maxHeapFixDown（a,i,len）;//从有叶子的父节点建立最大堆，从下到上}for（int i=a.length-1;i>=0;i--）{//堆顶元素为堆的最大值，每次把堆顶换到数组后面，一次次循环就使数组变成从小到大排序int temp = a[i];a[i] = a[0];a[0] = temp;maxHeapFixDown（a,0,i）;}for（int i=0;i<a.length;i++）{System.out.print（a[i]+" "）;}}/** * 因为我们要从小到大排序，所以需要建立一个最大堆，从i开始到n-1，此时应满足a[i]>a[i+1,...,n-1] */public static void maxHeapFixDown（int[] a,int i,int n）{int temp = a[i];int j = 2*i+1;while（j<n）{if（（j+1）<n&&a[j]<a[j+1]）j++;if（a[j]<temp）break;a[i] = a[j];i=j;j=2*j+1;}a[i] = temp;}} 5.快速排序：选第一个元素作为基准元素，把小于这个基准元素的值放到前面，把大于这个基准元素的值放到后面。每次这个基准元素的最后位置也就是有序数列最后的位置，a[0,...,m-1] <a[m]<a[m+1,..,n]，再从前面的a[0,...,m-1]进行上面的重复操作即可。 package TestProject;/** * 快排 * @author xuhui * */public class SortAll {public static void main（String[] args）{int[] a = {0,8,1,2,8,6,1};int len = a.length;quickSort（a,0,len-1）;for（int i=0;i<a.length;i++）{System.out.print（a[i]+" "）;}} public static void quickSort（int[] a,int s,int t）{if（s<t）{int x = a[s];int i = s;int j = t;while（i<j）{while（i<j&&a[j]>=x）j--;int temp = a[i];a[i] = a[j];a[j] = temp;while（i<j&&a[i]<=x）i++;temp = a[j];a[j] = a[i];a[i] = temp;}quickSort（a,s,i-1）;quickSort（a,i+1,t）;}}}这边都是自己参照算法描述实现的Java代码，其中堆排序理解起来会比较困难，里面可能有一些边缘条件没有考虑到，如果有错请大家积极纠正。本文永久更新链接地址：http://www.linuxidc.com/Linux/2016-07/133655.htm