排序算法----归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，在使子序列段有序。若将两个有序表合并成一个有序表，称为2路归并。

时间复杂度：O（nlog2n）空间复杂度：O（n）稳定性：稳定

package 排序算法; import java.util.Arrays; import java.util.Random; public class MergSort { public static void main(String[] args) { int arr[]=new int[20]; Random random=new Random(); for (int i=0;i<arr.length;i++){ arr[i]=random.nextInt(50); } mergSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } private static void mergSort(int[] arr, int l, int r) { //优化：如果元素少 则直接排序 if(r-l<=10){ ShellSort.shellSort(arr,l,r); return; } int mid=(l+r)/2; mergSort(arr,l,mid); mergSort(arr,mid+1,r); //2.优化：如果左边的尾<右边的头 则没必要并 if(arr[mid]>arr[mid+1]){ merge(arr,l,mid,r); } } private static void merge(int[] arr, int l, int mid, int r) { int [] aux=new int [r-l+1]; for (int i=l;i<=r;i++){ aux[i-l]=arr[i]; } int i=l; int j=mid+1; for (int k=l;k<=r;k++){ if(i>mid){ arr[k]=aux[j-l]; j++; }else if(j>r){ arr[k]=aux[i-l]; i++; }else if (aux[i-l]<aux[j-l]){ arr[k]=aux[i-l]; i++; }else { arr[k]=aux[j-l]; j++; } } } }

执行结果

[1, 3, 3, 5, 7, 10, 10, 18, 18, 21, 22, 26, 26, 27, 35, 35, 38, 43, 48, 49]

测试（完全随机情况下）

package 排序算法; import java.util.Arrays; import java.util.Random; public class TestSort { /* 数据分布情况 1.完全随机 2.大致有序 3.方差小 */ public static int[] getTotalRandom(){ Random random=new Random(); int [] arr=new int[10000]; for (int i=0;i<arr.length;i++){ arr[i]=random.nextInt(10000); } return arr; } public static void main(String[] args) { int [] arr1=getTotalRandom(); int [] arr2= Arrays.copyOf(arr1, arr1.length); int [] arr3= Arrays.copyOf(arr1, arr1.length); int [] arr4= Arrays.copyOf(arr1, arr1.length); int [] arr5= Arrays.copyOf(arr1, arr1.length); testSelectionSort(arr1); testBubbleSort(arr2); testInsertSort(arr3); testShellSort(arr4); testMergSort(arr5); } private static void testInsertSort(int[] arr3) { long startTime=System.currentTimeMillis(); BubbleSort.bubbleSort(arr3); long endTime=System.currentTimeMillis(); System.out.println("冒泡排序"+(endTime-startTime)); } private static void testBubbleSort(int[] arr2) { long startTime=System.currentTimeMillis(); insertionSort.lnsertionSortUpper(arr2); long endTime=System.currentTimeMillis(); System.out.println("插入排序"+(endTime-startTime)); } private static void testSelectionSort(int[] arr) { long startTime=System.currentTimeMillis(); SelectionSort.selectionSort(arr); long endTime=System.currentTimeMillis(); System.out.println("选择排序"+(endTime-startTime)); } private static void testShellSort(int[] arr) { long startTime=System.currentTimeMillis(); ShellSort.shellSort(arr); long endTime=System.currentTimeMillis(); System.out.println("希尔排序"+(endTime-startTime)); } private static void testMergSort(int[] arr) { long startTime=System.currentTimeMillis(); MergSort.mergSort(arr,0,arr.length-1); long endTime=System.currentTimeMillis(); System.out.println("归并排序"+(endTime-startTime)); } }

执行结果

选择排序207 插入排序14 冒泡排序181 希尔排序12 归并排序29