欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java编程中实现归并排序算法的实例教程

程序员文章站 2024-03-09 17:27:11
算法概述/思路 归并排序是基于一种被称为“分治”(divide and conquer)的策略。其基本思路是这样的: 1.对于两个有序的数组,要将其合并为一个有序数组,...

算法概述/思路
归并排序是基于一种被称为“分治”(divide and conquer)的策略。其基本思路是这样的:
1.对于两个有序的数组,要将其合并为一个有序数组,我们可以很容易地写出如下代码:

//both a and b is ascend.
public void merge(int[] a, int[] b, int[] c){
  int i=0,j=0,k=0;
  while (i<=a.length && j<=b.length){
    if (a[i]<=b[i]){
      c[k++]=a[i++];
    }
    else{
      c[k++]=b[j++];
    }
  }
  while (i<=a.length){
    c[k++]=a[i++];
  }
  while (j<=b.length){
    c[k++]=b[j++];
  }
}

容易看出,这样的合并算法是高效的,其时间复杂度可达到o(n)。
2.假如有一个无序数组需要排序,但它的两个完全划分的子数组a和b分别有序,借助上述代码,我们也可以很容易实现;
3.那么,如果a,b无序,怎么办呢?可以把它们再分成更小的数组。
4.如此一直划分到最小,每个子数组都只有一个元素,则可以视为有序数组。
5.从这些最小的数组开始,逆着上面的步骤合并回去,整个数组就排好了。
总而言之,归并排序就是使用递归,先分解数组为子数组,再合并数组。

例子
下面举例说明,假如要对数组a={2,1,3,5,2,3}进行排序,那么把数组划分为{2,1,3}和{5,2,3}两个子数组,这两个子数组排序后变为{1,2,3}和{2,3,5},然后对这两个数组进行归并操作便得到最终的有序数组。代码实现如下:

void sort(int[] a) {
  int[] aux = new int[a.length];  //辅助数组
  mergesort(a, 0, a.length - 1, aux);
}

void mergesort(int[] a, int lo, int hi, int[] aux) {
  if (hi <= lo)
    return;
  int mid = lo + (hi - lo) / 2;
  mergesort(a, lo, mid, aux);
  mergesort(a, mid + 1, hi, aux);
  merge(a, lo, mid, hi, aux);

}

void merge(int[] a, int lo, int mid, int hi, int[] aux) {
  int i = lo, j = mid + 1;
  for (int k = lo; k <= hi; k++) {
    aux[k] = a[k];
  }
  for (int k = lo; k <= hi; k++) {
    if (i > mid)
      a[k] = aux[j++];
    else if (j > hi)
      a[k] = aux[i++];
    else if (aux[i] <= aux[j])
      a[k] = aux[i++];
    else
      a[k] = aux[j++];

  }
}

另一种实现:自底向上的归并排序
在上面的实现中,相当于将一个大问题分割成小问题分别解决,然后用所有小问题的答案来解决整个大问题。将一个大的数组的排序划分为小数组的排序是自顶向下的排序。还有一种实现是自底向上的排序,即先两两归并,然后四四归并......代码实现如下:

void sort(int[] a) {
  int n = a.length;
  int[] aux = new int[n];
  for (int sz = 1; sz < n; sz += sz) {
    for (int lo = 0; lo < n - sz; lo += sz + sz) {
      //在每轮归并中,最后一次归并的第二个子数组可能比第一个子数组要小
      merge(a, lo, lo + sz - 1, math.min(lo + sz + sz - 1, n - 1), aux);
    }
  }
}