疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

几大排序算法的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

  System.out.print(a[i]+" ");

  }

  }

  public static void bubbleSort(int[] a){

  int len = a.length;//数组长度

  for(int i=0;i

  for(int j=0;j

  if(a[j+1]

  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

  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

  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

  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

  for(int i=low;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]

  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

  System.out.print(a[i]+" ");

  }

  }

  public static void insertSort(int[] a){

  int len = a.length;//数组长度

  for(int i=1;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

  System.out.print(a[i]+" ");

  }

  }

  public static void selectSort(int[] a){

  int len = a.length;

  for(int i=0;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]

  }

  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

  System.out.print(a[i]+" ");

  }

  }

  public static void selectSort(int[] a){

  int len = a.length;

  int l = 0;

  int h = len-1;

  while(l

  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]-max

  for(int i=s;i<=t;i++){

  if(a[i]

  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

  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

  if((j+1)

  if(a[j]

  a[i] = a[j];

  i=j;

  j=2*j+1;

  }

  a[i] = temp;

  }

  }

  复制代码

  5.快速排序:选第一个元素作为基准元素,把小于这个基准元素的值放到前面,把大于这个基准元素的值放到后面。每次这个基准元素的最后位置也就是有序数列最后的位置,

  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

  System.out.print(a[i]+" ");

  }

  }

  public static void quickSort(int[] a,int s,int t){

  if(s

  int x = a[s];

  int i = s;

  int j = t;

  while(i

  while(i

  int temp = a[i];

  a[i] = a[j];

  a[j] = temp;

  while(i

  temp = a[j];

  a[j] = a[i];

  a[i] = temp;

  }

  quickSort(a,s,i-1);

  quickSort(a,i+1,t);

  }

  }

  }

  复制代码

  这边都是自己参照算法描述实现的Java代码,其中堆排序理解起来会比较困难,里面可能有一些边缘条件没有考虑到,如果有错请大家积极纠正。