Java实现归并排序 MergeSort的解析

归并排序 mergeSort 的解析和java实现

mergeSort是稳定的O(nlogn)的排序算法，但是相比起其他的排序算法来说需要额外O(n)的空间。
归并排序的主体思想就是把一整个数组不断的对半拆分，直到每一个子数组中都只有两个元素。然后对这两个元素进行排序。在对最小的子数组进行排序之后，进行合并，把两个子数组中最小的一个放到新数组的头部然后指针向后移。

class MergeSort{ public static void mergeSort(int[] arr){ int[] copy = new int[arr.length]; for(int i = 0; i < arr.length;i++){ copy[i] = arr[i]; } helper(arr,copy,0,arr.length-1); } public static void helper(int[]arr,int[] copy,int start,int end){ int mid = (end-start)/2 + start; helper(arr,copy,start,mid); helper(arr,copy,mid+1,end); merge(arr,start,mid,end,copy); } public static void merge(int[] arr,int start,int mid,int end, int[] copy){ int i = start; int j = mid+1; int t = 0; while(i <= mid && j <= end){ if(arr[i] <= arr[j]){ copy[t++] = arr[i++]; }else{ copy[t++] = arr[j++]; } } while( i <= mid){ copy[t++] = arr[i++]; } while( j <= right){ copy[t++] = arr[j++]; } t = 0; while(left <= right){ arr[left++] = copy[t++]; } } } 

这样我们通过不断的分解数组成为最小的子数组的helper和merge有序的子数组就可以完成mergeSort了

本文地址：https://blog.csdn.net/Dh0le/article/details/107888922