package data; import java.util.Arrays; import java.util.Random; /** * 并歸排序 * @author JYC506 * */ public class MergeSort { /** * 對(duì)部份排好序的數(shù)組進(jìn)行歸并 * @param arr 要操作的數(shù)組 * @param start1 排好序的數(shù)組部份1出發(fā)點(diǎn) * @param end1 排好序的數(shù)組部份1終點(diǎn) * @param start2 排好序的數(shù)組部份2出發(fā)點(diǎn) * @param end2 排好序的數(shù)組部份2終點(diǎn) * @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; /*比較兩個(gè)數(shù)組排好序的部份，從這兩部份開始出發(fā)點(diǎn)做比較，比較小的插入新數(shù)組 例如比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第1個(gè)有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1；否則將第2 個(gè)有序表中的元素a[j]復(fù)制到r[k]中，并令j和k分別加上1，如此循環(huán)下去，直到其中1個(gè)有序表取完*/ while (index1 <= end1 && index2 <= end2) { if (arr[index1] < arr[index2]) { newArr[index] = arr[index1]; index++; index1++; } else { newArr[index] = arr[index2]; index++; index2++; } } /*然后再將另外一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元*/ while (index1 <= end1) { newArr[index] = arr[index1]; index++; index1++; } while (index2 <= end2) { newArr[index] = arr[index2]; index++; index2++; } return newArr; } /** * 對(duì)部份且相鄰了排好序的數(shù)組進(jìn)行歸并 * @param arr 要操作的數(shù)組 * @param start1 排好序的數(shù)組部份1出發(fā)點(diǎn) * @param start2 排好序的數(shù)組部份2出發(fā)點(diǎn) * @param end2 排好序的數(shù)組部份2終點(diǎn) */ 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 要操作的數(shù)組 * @param start 起始坐標(biāo) * @param size 分組后每組的元素?cái)?shù) */ private static void mergerSort(int[] arr, int start, int size) { /*由于是成對(duì)照較,所以要乘以2*/ int length=arr.length; int dSize=size*2; int num=length/dSize; int residue=length%dSize; //　歸并到只剩1個(gè)有序集合的時(shí)候結(jié)束算法，也是就是余數(shù)為0的時(shí)候 if(num==0){ return; } //　進(jìn)行1趟歸并（注意，第1次并歸只有1個(gè)元素，就是兩兩比較時(shí)已算排序了） for(int i=0;i<num;i++){ int sta=start+(size*2)*i; merger(arr,sta,sta+size,sta+size*2⑴); } //將剩下的數(shù)和最后1個(gè)有序集合歸并（這個(gè)要注意理解） if(residue!=0){ merger(arr,length-residue-size*2,length-residue,length⑴); } //　遞歸履行下1趟歸并排序,并歸元素師成倍增加 mergerSort(arr, 0, 2 * size); } /** * * @param arr 要操作的數(shù)組 */ public static void mergerSort(int[] arr){ /*默許 起始坐標(biāo)為0,并且分組元素為1個(gè)開始，由于1個(gè)是不用排序的*/ mergerSort(arr, 0,1); } public static void main(String[] args) { /*測(cè)試并歸排序*/ int[] ar1=new int[]{10,4,6,3,8,2,5}; MergeSort.mergerSort(ar1); System.out.println(Arrays.toString(ar1)); /*測(cè)試100萬(wàn)隨機(jī)數(shù)并歸排序和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)); } }