ITPub博客

首页 > 应用开发 > Java > Java实现归并排序

Java实现归并排序

原创 Java 作者:541732025 时间:2014-04-14 19:51:39 0 删除 编辑

点击(此处)折叠或打开

  1. public class MergeSort {
  2.     //将有二个有序数列a[first...mid]和a[mid...last]合并。
  3.     static void mergearray(int a[], int first, int mid, int last, int temp[]) {
  4.         int i = first, j = mid + 1;
  5.         int m = mid, n = last;
  6.         int k = 0;


  7.         while (i <= m && j <= n) {
  8.             if (a[i] <= a[j])
  9.                 temp[k++] = a[i++];
  10.             else
  11.                 temp[k++] = a[j++];
  12.         }


  13.         //如果从mid到last的数据已经遍历完毕,将first到mid剩余的数据拷贝至sorted
  14.         while (i <= m) {
  15.             temp[k++] = a[i++];
  16.         }


  17.         //如果从first到mid的数据已经遍历完毕,将mid到last剩余的数据拷贝至sorted
  18.         while (j <= n) {
  19.             temp[k++] = a[j++];
  20.         }


  21.         //至此,temp[]为有序的数组


  22.         //更改a[]中first至last元素顺序,使其排序
  23.         for (i = 0; i < k; i++) {
  24.             a[first + i] = temp[i];
  25.         }
  26.     }


  27.     static void mergesort(int a[], int first, int last, int temp[]) {
  28.         if (first < last) {
  29.             int mid = (first + last) / 2;
  30.             mergesort(a, first, mid, temp); //递归,将数组切割至最小(1个元素)
  31.             mergesort(a, mid + 1, last, temp); //同上
  32.             mergearray(a, first, mid, last, temp); //再将相邻的二个元素合并、排序,往上递归,直至最后合并成一个最大的有序数组
  33.         }
  34.     }


  35.     public static void main(String[] args) {
  36.         int[] x = { 6, 2, 4, 1, 5, 9, 3 };
  37.         int[] sorted = new int[x.length];
  38.         mergesort(x, 0, x.length - 1, sorted);


  39.         for (int i = 0; i < sorted.length; i++) {
  40.             System.out.println(sorted[i]);
  41.         }
  42.     }
  43. }


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/28912557/viewspace-1141973/,如需转载,请注明出处,否则将追究法律责任。

下一篇: 生产者与消费者
请登录后发表评论 登录
全部评论

注册时间:2013-05-23

  • 博文量
    127
  • 访问量
    481915