1 package com.gxf.merg; 2  3 /** 4  * 归并排序 5  * 初始状态，将数组看成n个单独有序的序列，两两合并成一个有序序列，把最后两个序列合并 6  * 用一个方法归并两个有序序列 7  * 用递归将数组分成两个有序序列，在对两个序列进行归并排序，得到有序序列 8  * @author xiangfei 9  *10  */11 public class Merg {12     public Rec rec = new Rec();13     /**14      * 将有序序列[start, middel][middle + 1, end]归并成一个有序序列，放到rec1数组中15      * 分别用三个指针i,j,k指向两个区间和rec1数组16      * 将rec[i]和rec[j]中较小的元素放到rec1[k]中17      * 直到其中一个区间结束，在把剩下元素放到rec1[]中18      * @param rec19      * @param start20      * @param middle21      * @param end22      * @param rec123      */24     public void merg(Rec rec[], int start, int middle, int end, Rec rec1[]){25         int first = start;26         int second = middle + 1;27         int dst = start;//三个指针28         29         while(first <= middle && second <= end){30             if(rec[first].key < rec[second].key) 31                 rec1[dst++].key = rec[first++].key;32             else33                 rec1[dst++].key = rec[second++].key;34         }//比较两个序列中的值，将较小的放到rec1[]中。直到其中一个全部放到rec1[]中35         while(first <= middle)36             rec1[dst++].key = rec[first++].key;//如果第一区间没有完全移动到rec1中37         while(second <= end)38             rec1[dst++].key = rec[second++].key;//如果第二个区间还有内容，将剩下的移动到rec1中39 //        for(int i = start; i < rec1.length ; i++){40 //            System.out.print(rec1[i].key + " ");41 //        }42 //        System.out.println();43     }44     45     /**46      * 将rec[]分成左右两个区间，通过递归将其分为左右两个有序区间，调用一次归并将其合并成一个有序序列47      * rec[]排好序放到rec1[]中48      * 如果只有一个元素，将rec放到rec1中49      * @param rec50      * @param start51      * @param end52      * @param rec153      */54     public void mergSort(Rec rec[], int start, int end, Rec rec1[]){55         Rec rec2[] = this.rec.getNewArray(end  + 1);//这里为毛不是end - start + 1?56         if(start == end){57             rec1[start].key = rec[start].key;58         }59         else{60             int middle = (start + end) / 2;61             mergSort(rec, start, middle, rec2);62             mergSort(rec, middle + 1, end, rec2);//将左右区间调整为有序63             merg(rec2, start, middle, end, rec1);64         }65     }66     67     /**68      * 向类调用者提供一个接口方便调用69      * @param rec70      */71     public void mergSort(Rec rec[]){72         Rec result[] = this.rec.getNewArray(rec.length);73         mergSort(rec, 0, rec.length - 1, result);74         System.arraycopy(result, 0, rec, 0, result.length);75     }76 }

 1 package com.gxf.merg; 2  3 /** 4  * 将关键字封装一下 5  * @author xiangfei 6  * 7  */ 8 public class Rec { 9     int key;10     11     public Rec(int key){12         this.key = key;13     }14     public Rec(){15         16     }17     18     /**19      * 根据整型数组构造一个Rec[]数组20      * @param array21      * @return22      */23     public Rec[] getRecArray(int array[]){24         Rec rec[] = new Rec[array.length];25         for(int i = 0; i < array.length; i++){26             rec[i] = new Rec(array[i]);27         }28         29         return rec;30     }31     public void showArray(Rec rec[]){32         for(int i = 0; i < rec.length ; i++){33             34             System.out.print(rec[i].key + " ");35         }36         System.out.println();37     }38     public Rec[] getNewArray(int size){39         Rec array[] = new Rec[size];//数组中每个对象都是null,这里需要注意40         for(int i = 0; i < size; i++){41             array[i] = new Rec();42         }43         return array;44     }45 }

 1 package com.gxf.merg; 2  3  4  5 public class Test { 6     public static void main(String args[]){ 7         Merg mergSort = new Merg(); 8         Rec rec = new Rec(); 9         int array[] = new int[]{40, 32, 1, 34, 54, 5, 6};10         Rec array_test[] = rec.getRecArray(array);11         System.out.println("归并排序之前:");12         rec.showArray(array_test);13         mergSort.mergSort(array_test);14         System.out.println("归并排序之后：");15         rec.showArray(array_test);16     }17 }