黑马程序员技术交流社区

标题: 分享，Java归并排序的算法实现 [打印本页]
作者: heshiwei    时间: 2015-10-7 16:18
标题: 分享，Java归并排序的算法实现
（1）基本排序：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
  1. import java.util.Arrays;

  3. publicclass mergingSort {

  5. inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};

  7. publicmergingSort(){
  8.     sort(a,0,a.length-1);
  9.     for(int i=0;i<a.length;i++)
  10.        System.out.println(a[i]);
  11. }

  13. publicvoid sort(int[] data, int left, int right) {
  14.     // TODO Auto-generatedmethod stub
  15.     if(left<right){
  16.         //找出中间索引
  17.         int center=(left+right)/2;
  18.         //对左边数组进行递归
  19.         sort(data,left,center);
  20.         //对右边数组进行递归
  21.         sort(data,center+1,right);
  22.         //合并
  23.         merge(data,left,center,right);      
  24.     }

  26. }

  28. publicvoid merge(int[] data, int left, int center, int right) {
  29.     // TODO Auto-generatedmethod stub
  30.     int [] tmpArr=newint[data.length];
  31.     int mid=center+1;
  32.     //third记录中间数组的索引
  33.     int third=left;
  34.     int tmp=left;
  35.     while(left<=center&&mid<=right){
  36.         //从两个数组中取出最小的放入中间数组
  37.         if(data[left]<=data[mid]){
  38.             tmpArr[third++]=data[left++];
  39.         }else{
  40.             tmpArr[third++]=data[mid++];
  41.         }

  43.     }

  45.     //剩余部分依次放入中间数组
  46.     while(mid<=right){
  47.         tmpArr[third++]=data[mid++];
  48.     }

  50.     while(left<=center){
  51.         tmpArr[third++]=data[left++];
  52.     }

  54.     //将中间数组中的内容复制回原数组
  55.     while(tmp<=right){
  56.         data[tmp]=tmpArr[tmp++];
  57.     }
  58.     System.out.println(Arrays.toString(data));
  59. }
  60. }
复制代码



1347009541_6721.jpg (46.63 KB, 下载次数: 0)

1347009541_6721.jpg




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2