复习递归正式学习归并排序之前我们得先复习一下递归算法。定义定义方法时在方法内部调用方法本身称之为递归.作用它通常把一个大型复杂的问题层层转换为一个与原问题相似的规模较小的问题来求解。递归策略只需要少量的程序就可以描述出解题过程所需要的多次重复计算大大地减少了程序的代码量。注意事项容易造成栈内存溢出。在递归中不能无限制的调用自己必须要有边界条件能够让递归结束因为每一次递归调用都会在栈内存开辟新的空间重新执行方法如果递归的层级太深很容易造成栈内存溢出。案例:请定义一个方法使用递归完成求N的阶乘publicclassTest01{publicstaticvoidmain(String[]args)throwsException{intresultfactorial(5);System.out.println(result);}publicstaticintfactorial(intn){if(n1){return1;}returnn*factorial(n-1);}}归并排序定义:归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。分治法:分治法将问题分(divide)成一些小的问题然后递归求解而治(conquer)的阶段则将分的阶段得到的各答案修补在一起即分而治之排序原理尽可能的一组数据拆分成两个元素相等的子组并对每一个子组继续拆分直到拆分后的每个子组的元素个数是 1为止。将相邻的两个子组进行合并成一个有序的大组3. 不断的重复步骤2直到最终只有一个组为止。归并原理代码实现 1:API设计publicclassMerge{//归并所需要的辅助数组privatestaticComparable[]assist;/* 比较v元素是否小于w元素 */privatestaticbooleanless(Comparablev,Comparablew){returnv.compareTo(w)0;}/* 数组元素i和j交换位置 */privatestaticvoidexch(Comparable[]a,inti,intj){Comparableta[i];a[i]a[j];a[j]t;}/* 对数组a中的元素进行排序 */publicstaticvoidsort(Comparable[]a){//1.初始化辅助数组assistassistnewComparable[a.length];//2.定义一个lo变量和hi变量分别记录数组中最小的索引和最大的索引intlo0;inthia.length-1;//3.调用sort重载方法完成数组a中从索引lo到索引hi的元素的排序sort(a,lo,hi);}/* 对数组a中从lo到hi的元素进行排序 */privatestaticvoidsort(Comparable[]a,intlo,inthi){//做安全性校验if(hilo){return;}//对lo到hi之间的数据进行分为两个组intmidlo(hi-lo)/2;// 5,9 mid7//分别对每一组数据进行排序sort(a,lo,mid);sort(a,mid1,hi);//再把两个组中的数据进行归并merge(a,lo,mid,hi);}/* 对数组中从lo到mid为一组从mid1到hi为一组对这两组数据进行归并 */privatestaticvoidmerge(Comparable[]a,intlo,intmid,inthi){//定义三个指针intilo;//定义一个指针指向assist数组中开始填充数据的索引intp1lo;//定义一个指针指向第一组数据的第一个元素intp2mid1;//定义一个指针指向第二组数据的第一个元素//遍历移动p1指针和p2指针比较对应索引处的值找出小的那个放到辅助数组的对应索引处while(p1midp2hi){//比较对应索引处的值if(less(a[p1],a[p2])){assist[i]a[p1];}else{assist[i]a[p2];}}//遍历如果p1的指针没有走完那么顺序移动p1指针把对应的元素放到辅助数组的对应索引处while(p1mid){assist[i]a[p1];}//遍历如果p2的指针没有走完那么顺序移动p2指针把对应的元素放到辅助数组的对应索引处while(p2hi){assist[i]a[p2];}//把辅助数组中的元素拷贝到原数组中for(intindexlo;indexhi;index){a[index]assist[index];}}}测试类:publicstaticvoidmain(String[]args){Integer[]data{9,-16,21,23,-30,-49,21,30,30};System.out.println(排序之前\njava.util.Arrays.toString(data));Merge.sort(data);System.out.println(排序之后\njava.util.Arrays.toString(data));}代码实现 2:MergeSortpublicclassMergeSort{publicstaticvoidmergeSort(int[]data){// 归并排序sort(data,0,data.length-1);}// 将索引从left到right范围的数组元素进行归并排序privatestaticvoidsort(int[]data,intleft,intright){if(leftright){//找出中间索引intcenter(leftright)/2;sort(data,left,center);sort(data,center1,right);//合并merge(data,left,center,right);}}// 将两个数组进行归并归并前两个数组已经有序归并后依然有序privatestaticvoidmerge(int[]data,intleft,intcenter,intright){int[]tempArrnewint[data.length];intmidcenter1;intthirdleft;inttempleft;while(leftcentermidright){if(data[left]-data[mid]0){tempArr[third]data[left];}else{tempArr[third]data[mid];}}while(midright){tempArr[third]data[mid];}while(leftcenter){tempArr[third]data[left];}while(tempright){data[temp]tempArr[temp];}}publicstaticvoidmain(String[]args){int[]data{9,-16,21,23,-30,-49,21,30,30};System.out.println(排序之前\njava.util.Arrays.toString(data));mergeSort(data);System.out.println(排序之后\njava.util.Arrays.toString(data));}}对象排序:publicclassMergeSort02{publicstaticvoidmergeSort(DataWrap[]data){// 归并排序sort(data,0,data.length-1);}// 将索引从left到right范围的数组元素进行归并排序privatestaticvoidsort(DataWrap[]data,intleft,intright){if(leftright){//找出中间索引intcenter(leftright)/2;sort(data,left,center);sort(data,center1,right);//合并merge(data,left,center,right);}}// 将两个数组进行归并归并前两个数组已经有序归并后依然有序privatestaticvoidmerge(DataWrap[]data,intleft,intcenter,intright){DataWrap[]tempArrnewDataWrap[data.length];intmidcenter1;intthirdleft;inttempleft;while(leftcentermidright){if(data[left].compareTo(data[mid])0){tempArr[third]data[left];}else{tempArr[third]data[mid];}}while(midright){tempArr[third]data[mid];}while(leftcenter){tempArr[third]data[left];}while(tempright){data[temp]tempArr[temp];}}publicstaticvoidmain(String[]args){DataWrap[]data{newDataWrap(9,),newDataWrap(-16,),newDataWrap(21,*),newDataWrap(23,),newDataWrap(-30,),newDataWrap(-49,),newDataWrap(21,),newDataWrap(30,*),newDataWrap(30,)};System.out.println(排序之前\njava.util.Arrays.toString(data));mergeSort(data);System.out.println(排序之后\njava.util.Arrays.toString(data));}}归并排序稳定归并排序在归并的过程中只有arr[i]arr[i1]的时候才会交换位置如果两个元素相等则不会交换位置所以它并不会破坏稳定性归并排序是稳定的。时间复杂度分析解析:时间复杂度为O(nlogn);归并排序的缺点需要申请额外的数组空间导致空间复杂度提升是典型的以空间换时间的操作。归并排序与希尔排序性能测试importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.util.ArrayList;publicclassSortCompare{//调用不同的测试方法完成测试publicstaticvoidmain(String[]args)throwsException{//1.创建一个ArrayList集合保存读取出来的整数ArrayListIntegerlistnewArrayList();//2.创建缓存读取流BufferedReader读取数据并存储到ArrayList中BufferedReaderreadernewBufferedReader(newInputStreamReader(SortCompare.class.getClassLoader().getResourceAsStream(reverse_arr.txt)));Stringlinenull;while((linereader.readLine())!null){//line是字符串把line转换成Integer存储到集合中intiInteger.parseInt(line);list.add(i);}reader.close();//3.把ArrayList集合转换成数组Integer[]anewInteger[list.size()];list.toArray(a);//4.调用测试代码完成测试// testInsertion(a);// testShell(a); //17testMerge(a);}//测试希尔排序publicstaticvoidtestShell(Integer[]a){//1.获取执行之前的时间longstartSystem.currentTimeMillis();//2.执行算法代码Shell.sort(a);//3.获取执行之后的时间longendSystem.currentTimeMillis();//4.算出程序执行的时间并输出System.out.println(希尔排序执行的时间为(end-start)毫秒);}//测试插入排序publicstaticvoidtestInsertion(Integer[]a){//1.获取执行之前的时间longstartSystem.currentTimeMillis();//2.执行算法代码Insertion.sort(a);//3.获取执行之后的时间longendSystem.currentTimeMillis();//4.算出程序执行的时间并输出System.out.println(插入排序执行的时间为(end-start)毫秒);}//测试插入排序publicstaticvoidtestMerge(Integer[]a){//1.获取执行之前的时间longstartSystem.currentTimeMillis();//2.执行算法代码Merge.sort(a);//3.获取执行之后的时间longendSystem.currentTimeMillis();//4.算出程序执行的时间并输出System.out.println(归并排序执行的时间为(end-start)毫秒);}}通过测试发现希尔排序和归并排序在处理大批量数据时差别不是很大。但归并是稳定排序,希尔是非稳定排序小结:时间复杂度T(n) O(nlogn)稳定