归并排序Java代码实现

归并排序复习：

结论：归并排序时间复杂度为O(nlgn),额外空间复杂度为O(n)，实现可以做到稳定；

核心思想：典型的分冶策略思想：

第一步：拆分：递归对半拆分无序数组为无数的子数组；

第二步：排序：将子数组排好序；

第三步：合并：将子数组合并为和原先一样的长度的大数组；排序结束；

代码实现：

  1 package com.cmbc.test1;
  2 
  3 import java.util.Arrays;
  4 
  5 /**
  6  * 归并排序
  7  * @author itqcy
  8  *
  9  */
 10 public class MergeSortion {
 11     public static void mergeSort(int[] arr){
 12         if(arr==null||arr.length<2){
 13             return;
 14         }
 15         mergeSort(arr,0,arr.length-1);
 16     }
 17 
 18     public static void mergeSort(int[] arr, int l, int r) {
 19         if(l==r){
 20             return;
 21         }
 22         int mid = l+((r-l)>>1);
 23         mergeSort(arr,l,mid);
 24         mergeSort(arr,mid+1,r);
 25         merge(arr,l,mid,r);
 26     }
 27     public static void merge(int[] arr,int l,int mid,int r){
 28         int[] help = new int[r-l+1];
 29         int count = 0;
 30         int p1 = l;
 31         int p2 = mid+1;
 32         while(p1<=mid&&p2<=r){
 33             help[count++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
 34         }
 35         while(p1<=mid){
 36             help[count++] = arr[p1++];
 37         }
 38         while(p2<=r){
 39             help[count++] = arr[p2++];
 40         }
 41         for(int i = 0;i<help.length;i++){
 42             arr[l+i] = help[i];
 43         }
 44     }
 45     
 46     public static void printArray(int[] arr) {
 47         if (arr == null) {
 48             return;
 49         }
 50         for (int i = 0; i < arr.length; i++) {
 51             System.out.print(arr[i] + " ");
 52         }
 53         
 54     }
 55     
 56     public static int[] copyArray(int[] arr) {
 57         if (arr == null) {
 58             return null;
 59         }
 60         int[] res = new int[arr.length];
 61         for (int i = 0; i < arr.length; i++) {
 62             res[i] = arr[i];
 63         }
 64         return res;
 65     }
 66 
 67     public static boolean isEqual(int[] arr1, int[] arr2) {
 68         if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
 69             return false;
 70         }
 71         if (arr1 == null && arr2 == null) {
 72             return true;
 73         }
 74         if (arr1.length != arr2.length) {
 75             return false;
 76         }
 77         for (int i = 0; i < arr1.length; i++) {
 78             if (arr1[i] != arr2[i]) {
 79                 return false;
 80             }
 81         }
 82         return true;
 83     }
 84     
 85     public static int[] generateRandomArray(int maxSize, int maxValue) {
 86         int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
 87         for (int i = 0; i < arr.length; i++) {
 88             arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
 89         }
 90         return arr;
 91     }
 92     
 93     public static void main(String[] args) {
 94         int testTime = 500000;
 95         int maxSize = 100;
 96         int maxValue = 100;
 97         boolean succeed = true;
 98         for (int i = 0; i < testTime; i++) {
 99             int[] arr1 = generateRandomArray(maxSize, maxValue);
100             int[] arr2 = copyArray(arr1);
101             mergeSort(arr1);
102             Arrays.sort(arr2);
103             if (!isEqual(arr1, arr2)) {
104                 succeed = false;
105                 printArray(arr1);
106                 printArray(arr2);
107                 break;
108             }
109         }
110         System.out.println(succeed ? "归并排序结果正确!" : "错误!");
111 
112         int[] arr = generateRandomArray(maxSize, maxValue);
113         printArray(arr);
114         mergeSort(arr);
115         printArray(arr);
116     }
117 }