Go语言视频零基础入门到精通

javalearner

一.归并排序的思路
①把 n 个记录看成 n 个长度为 l 的有序子表；

②进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表；

③重复第②步直到所有记录归并成一个长度为 n 的有序表为止。

二.归并排序算法实例
   对于归并排序算法这类的分治算法，其核心就是"分解"和"递归求解"。对于"分解"实例，会在下面分析msort()方法中给出。我们先看合并的过程。

    以下面描述的序列为例，在索引范围内[first , last)的序列还有九个整数元素，它由索引范围为[first , mid]的四个元素有序子列表A和索引范围[mid , last]的五个元素有序子列表B组成。
   
  
   
   
     
   

     
   
  
   

步骤1：比较arr[indexA]=7与arr[indexB]=12。将较小的元素7复制到数组tempArr的索引indexC处。并将indexA和indexC都指向下一个位置。


步骤2：比较arr[indexA]=10与arr[indexB]=12。将较小的元素10复制到数组tempArr的索引indexC处。并将indexA和indexC都指向下一个位置。


步骤3：比较arr[indexA]=19与arr[indexB]=12。将较小的元素12复制到数组tempArr的索引indexC处。并将indexB和indexC都指向下一个位置。

步骤4-7：依次成对比较两子表的元素将17，19，21，25复制到数组tempArr。此时，indexA到达子表A的未尾(indexA = mid)，indexB引用的值为30。

?步骤8-9：将未到尾部的子表剩余数据复制到tempArr中。



三.归并排序算法的实现
了解了合并过程，那么理解下面的代码并不是一件难事。下面提供了归并算法的非泛型版本和泛型版本。

1. public class MergeSort {
   
2.    
   
3.     public static void sort(Object[] arr) {
   
4.        //创建临时数组
   
5.         Object[] tempArr = arr.clone();
   
6.         msort(arr, tempArr, 0, arr.length);
   
7.     }
   
8.     public static < T extends Comparable< ? super T>> void sort(T[] arr) {
   
9.        //创建临时数组
   
10.         T[] tempArr = (T[]) arr.clone();   
    
11.         msort(arr, tempArr, 0, arr.length);
    
12.     }
    
13.     private static void msort(Object[] arr, Object[] tempArr, int first,int last) {
    
14.          if (first + 1 < last) {
    
15.            
    
16.             int midpt = (last + first) / 2;
    
17.             msort(arr, tempArr, first, midpt);
    
18.             msort(arr, tempArr, midpt, last);
    
19.            
    
20.             if (((Comparable) arr[midpt - 1]).compareTo(arr[midpt]) <= 0)
    
21.                 return;
    
22.            
    
23.             int indexA, indexB, indexC;
    
24.             indexA = first;
    
25.             indexB = midpt;
    
26.             indexC = first;
    
27.             while (indexA < midpt && indexB < last) {
    
28.                 if (((Comparable) arr[indexA]).compareTo(arr[indexB]) < 0) {
    
29.                     tempArr[indexC] = arr[indexA]; //copyto tempArr
    
30.                     indexA++;
    
31.                 } else {
    
32.                     tempArr[indexC] = arr[indexB]; //copyto tempArr
    
33.                     indexB++;
    
34.                 }
    
35.                 indexC++;
    
36.             }
    
37.             //copy the tail of the sublist that is not exhausted
    
38.             while (indexA < midpt) {
    
39.                 tempArr[indexC++] = arr[indexA++];
    
40.             } while (indexB < last) {
    
41.                 tempArr[indexC++] = arr[indexB++];
    
42.             }
    
43.            
    
44.             for (int i = first; i < last; i++)
    
45.                 arr[i] = tempArr[i];
    
46.         }
    
47.     }
    
48.     public static void main(String[] args){
    
49.      // Integer  a[]={7,10,19,25,12,17,21,30,48};
    
50.       Integer a[]={30,-1};
    
51.       sort(a);
    
52.       for(Integer i:a)
    
53.         System.out.print(i+",");
    
54.    }
    
55. }

复制代码

上述代码中最核心的msort()方法是一递归算法。下图说明了msort()方法中子列表的分割与合并。



  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/7/000711203.zip