当然我下面写的程序，数组还是同个数组，分解的时候是直接按最小分解开始，就是直接按最细粒度分解package data;import java.util.Arrays;import java.util.Random;/** * 并归排序 * @author JYC506 * */public class MergeSort {/*** 对部分排好序的数组进行归并* @param arr 要操作的数组* @param start1 排好序的数组部分1起点* @param end1 排好序的数组部分1终点* @param start2 排好序的数组部分2起点* @param end2 排好序的数组部分2终点* @return*/private static int[] merger(int[] arr, int start1, int end1, int start2, int end2) {int[] newArr = new int[(end1 – start1) + (end2 – start2) + 2];int index1 = start1;int index2 = start2;int index = 0;/*比较两个数组排好序的部分，从这两部分开始起点做比较，比较小的插入新数组例如比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二 个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完*/while (index1 <= end1 && index2 <= end2) {if (arr[index1] < arr[index2]) {newArr[index] = arr[index1];index++;index1++;} else {newArr[index] = arr[index2];index++;index2++;}}/*然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元*/while (index1 <= end1) {newArr[index] = arr[index1];index++;index1++;}while (index2 <= end2) {newArr[index] = arr[index2];index++;index2++;}return newArr;}/*** 对部分且相邻了排好序的数组进行归并* @param arr 要操作的数组* @param start1 排好序的数组部分1起点* @param start2 排好序的数组部分2起点* @param end2 排好序的数组部分2终点*/private static void merger(int[] arr, int start1, int start2, int end2) { int end1 = start2 – 1;int[] newArr = merger(arr, start1, end1, start2, end2);System.arraycopy(newArr, 0, arr, start1, newArr.length);}/*** 并归排序* @param arr 要操作的数组* @param start 起始坐标* @param size 分组后每一组的元素数*/private static void mergerSort(int[] arr, int start, int size) {/*因为是成对比较,所以要乘以2*/int length=arr.length;int dSize=size*2;int num=length/dSize;int residue=length%dSize;// 归并到只剩一个有序集合的时候结束算法，，也是就是余数为0的时候if(num==0){return;}// 进行一趟归并（注意，第一次并归只有一个元素，就是两两比较时已经算排序了）for(int i=0;i<num;i++){int sta=start+(size*2)*i;merger(arr,sta,sta+size,sta+size*2-1);}//将剩下的数和最后一个有序集合归并（这个要注意理解）if(residue!=0){merger(arr,length-residue-size*2,length-residue,length-1);}// 递归执行下一趟归并排序,并归元素师成倍增加mergerSort(arr, 0, 2 * size);}/** * * @param arr 要操作的数组 */public static void mergerSort(int[] arr){/*默认 起始坐标为0,并且分组元素为一个开始，因为一个是不用排序的*/mergerSort(arr, 0,1);}public static void main(String[] args) {/*测试并归排序*/int[] ar1=new int[]{10,4,6,3,8,2,5};MergeSort.mergerSort(ar1);System.out.println(Arrays.toString(ar1));/*测试100万随机数并归排序和java自带快速排序*/int size=1000000;int[] arr1=new int[size];int[] arr2=new int[size];Random ran=new Random();for(int i=0;i<size;i++){int data=ran.nextInt(size);arr1[i]=data;arr2[i]=data;}long start=System.currentTimeMillis();MergeSort.mergerSort(arr1);long end1=System.currentTimeMillis();Arrays.sort(arr2);long end2=System.currentTimeMillis();System.out.println((end1-start));System.out.println((end2-end1));}}运行结果如下
快速排序算法的确比并归算法速度快点
好好扮演自己的角色，做自己该做的事
