疯狂java


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

归并排序的Java实现


 

   

  归并排序的优点不说了。

  做归并排序之前,我先试着将两个有序数组进行排序,合并成一个有序数组。

  思路:定义好两个有序数组,理解的时候我先思考了数组只有一个数组的排序,然后是两个元素的数组的排序,思路就有了,先比较两个数组的首元素,谁更小就放入结果数组里面,然后指针下移,继续比较,直到有一个数组为空,停止比较,因为是有序数组,那么不为空的数组后面的元素都比之前存入结果数组的要大,且是有序的,因此,只需将后面的数组存入结果数组即可。

  接下来是代码实现:

  /*

  * 分治算法利用

  * 两个有序数组的合并

  * 将有序数组i,数组j,合并成c

  */

  public Integer[] sort(Integer[] i, Integer[] j, Integer[] c){

  c = new Integer[i.length+j.length];

  int i1 = 0; //i的数组指针

  int j1 = 0; //j的数组指针

  int c1 = 0; //c的数组指针

  while(i1 < i.length&&j1 < j.length){

  if(i[i1] > j[j1]){

  c[c1++] = j[j1];

  j[j1++] = null;

  }else{

  c[c1++] = i[i1];

  i[i1++] = null;

  }

  }

  /*

  * i之后还有元素

  */

  while(i1

  c[c1++] = i[i1];

  i[i1++] = null;

  }

  /*

  * j之后还有元素

  */

  while(j1 < j.length){

  c[c1++] = j[j1];

  j[j1++] = null;

  }

  return c;

  }

  以上实现了将两个有序数组的合并,而归并排序,那么将一条无序数组分组成任意多个有序数组即可,并不需要确认是否是有序数组,一个数组里一个元素肯定是有序的,那么我要做的只是,递归实现数组分解,然后将有两个序数组合并。

  将一个数组分解,可以用分治的方法,定义头,尾,和中间指针,然后下次的递归,只需变换中间指针即可。

  而排序最开始只需要比较头部的一个元素和尾部的一个元素;

  依次向上递归。

  算了,贴代码吧。

  public int[] mergeSort(int[] num,int first,int last){

  int mid = (first+last)/2;

  if(first < last){

  mergeSort(num,first,mid);

  mergeSort(num,mid+1,last);

  merge(num,first,mid,last);

  }

  return num;

  }

  public void merge(int[] num,int first,int mid,int last){

  int _left = first; //左指针

  int _right = mid+1; //右指针

  int[] temp = new int[last - first + 1];

  int temp_p = 0;

  while(_left<=mid&&_right<=last){

  if(num[_left]

  temp[temp_p++] = num[_left++];

  }else{

  temp[temp_p++] = num[_right++];

  }

  }

  while(_left<=mid){

  temp[temp_p++] = num[_left++];

  }

  while(_right<=last){

  temp[temp_p++] = num[_right++];

  }

  _left = 0;

  //因为没有返回数组,所以排序好的数组应该放在num数组里面,直接覆盖即可,注意下标。

  for(int i : temp){

  num[(_left++)+first] = i;

  }

  }

  first,last为数组头尾指针。