归并排序
归并排序
1.将两个有序序列归并成一个有序序列
2.将带排序数组,通过递归调整成左右两个有序序列,在调用归并算法,将其归并成一个有序序列,完成排序
Merg.java
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 rec 19 * @param start 20 * @param middle 21 * @param end 22 * @param rec1 23 */ 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 else 33 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 rec 50 * @param start 51 * @param end 52 * @param rec1 53 */ 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 rec 70 */ 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 }
Rec.java
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 array 21 * @return 22 */ 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 }
Test.java
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 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。