您所在的位置:主页 > JAVA技术 >

将两个有序表组合成一个有序表

时间:2014-04-25 10:19来源:未知 作者:疯狂java 点击:

       二路归并排序
  二路归并排序,顾名思义就是指将两个有序表组合成一个新的有序表。那么对于一个任意的待排序的数组,又该如何实现呢?

  让我们假设一个整形数组为{1,3,4,2,5},我们需要对它进行归并排序。按照我们刚才对二路归并的定义可知,我们得把这个数组一分为二,然后对左右两边的数组分别排序之后,再把两者归并到一起,就能将无序变为有序了。也许你会有疑问,我将原数组分成左右两个数组之后,又要用什么方法来给左右数组排序呢?不难想到,我们可以继续拆分数组,即将左边的数组看成待排序的数组,继续将其拆分成两个数组。同理,右边亦是如此。那么到什么时候拆分结束呢?很简单,当我们将数组拆分成仅有一个元素的数组时,拆分结束!因为继续拆分已经没意义了哦。

  这样的话,你可能会问,拆分完成之后又该怎么归并呢?也许大家都会有或多或少的不习惯,因为我们是顺序将数组拆分,但需要逆序对数组归并。也就是说先归并元素个数为1的数组,再归并元素个数为2或更多的数组,直到最后只剩下两个数组,二者元素个数之和恰好为待排序数组元素之和。将二者归并之后,即得到顺序的数组。

  下面贴上我写的归并排序代码。

  Java代码

  /**

  * 归并排序

  *

  * @author Star

  *

  */

  public class MergeSortByStar {

  /**

  * @param args

  */

  public static void main(String[] args) {

  int array[] = { 1, 3, 4, 2, 5, 57, 78, 23, 1 };

  mergeSort(array);

  for (int i = 0; i < array.length; i++) {

  System.out.println(array[i]);

  }

  }

  /**

  *

  * @param array

  * 待排序的数组

  */

  public static void mergeSort(int array[]) {

  mSort(array, 0, array.length - 1);

  }

  /**

  *

  * @param array

  * 待排序数组

  * @param start

  * 排序的起点

  * @param end

  * 排序的终点

  */

  private static void mSort(int array[], int start, int end) {

  if (start >= end)

  return;

  int center = (start + end) / 2;// 将数组拆分成两段

  //二路归并

  mSort(array, start, center);// 给左边的数组排序

  mSort(array, center + 1, end);// 给右边的数组排序

  merge(array, start, center, end);// 将左右两边的数组进行归并

  }

  /**

  * 将左右两边的数组进行归并

  * @param array

  * 待排序数组

  * @param start

  * 排序起点

  * @param center

  * 排序中点

  * @param end

  * 排序终点

  */

  private static void merge(int array[], int start, int center, int end) {

  int index = start;// 从第一个位置出发

  int i = start;

  int j = center + 1;

  int[] tmp = new int[end+1];//创建一个缓存数组

  //比较左右两边数组,并用缓存数组接收较小的数

  for (; i <= center && j <= end; index++) {

  if (array[i] < array[j])

  tmp[index] = array[i++];

  else

  tmp[index] = array[j++];

  }

  //缓存数组接受剩下的数据

  //如果左边还有的话,接受左边

  while (i <= center) {

  tmp[index++] = array[i++];

  }

  //如果右边还有的话,接受右边

  while (j <= end) {

  tmp[index++] = array[j++];

  }

  // 将临时数组复制给原数组

  while (start <= end) {

  array[start] = tmp[start];

  start++;

  }

  }

  }