归并排序
2021-09-29 03:14
标签：imp lex size mergesort for amp 图片 tostring int 归并排序的算法是分治法的一个范例 Like QuickSort, Merge Sort is a Divide and Conquer algorithm.它被分成两半，调用自己来分两半，最后归并两半。merge()功能用于合并两半。The merge (arr,l,m,r)是关键的处理arr[l...m]和arr[m+1,r]被存储并合并两个子数组成为一个。 接下来是代码思想： MergeSort(arr[],l,r) If r>l: 1.Find the middle point to divide the array into two halves: middle m = (l+r)/2 2.Call mergeSort for first half: Call mergeSort(arr,l,m) 3.Call mergeSort for second half: Call mergeSort(arr,m+1,r) 4.Merge the two halves sorted in step 2 and 3: Call merge(arr,l,m,r) 下面的流程图展示了完成一个merge排序的处理流程{38,27,43,3,9,82,10}。我们可以发现这个数组被递归分割成两部分知道大小变成1，一旦size到达1，merge处理流程合并生效，开始归并数组直到整个数组完成。 import java.util.Arrays; public class mergSort { public static void main(String[] args) { int[] array = {5,2,3,7,9,10}; //sort(array,0,array.length-1); sort(array,0,array.length-1); System.out.println(Arrays.toString(array)); } public static void sort(int[] array,int l,int r) { if(l