复习递归
正式学习归并排序之前，我们得先复习一下递归算法。
定义：
- 定义方法时，在方法内部调用方法本身，称之为递归.
作用：
- 它通常把一个大型复杂的问题，层层转换为一个与原问题相似的，规模较小的问题来求解。递归策略只需要少量的程序就可以描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
注意事项：==>容易造成栈内存溢出。
- 在递归中，不能无限制的调用自己，必须要有边界条件，能够让递归结束，因为每一次递归调用都会在栈内存开辟新的空间，重新执行方法，如果递归的层级太深，很容易造成栈内存溢出。
案例:
请定义一个方法，使用递归完成求N的阶乘
publicclassTest01{publicstaticvoidmain(String[]args)throwsException{intresult=factorial(5);System.out.println(result);}publicstaticintfactorial(intn){if(n==1){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){Comparablet=a[i];a[i]=a[j];a[j]=t;}/* 对数组a中的元素进行排序 */publicstaticvoidsort(Comparable[]a){//1.初始化辅助数组assist；assist=newComparable[a.length];//2.定义一个lo变量，和hi变量，分别记录数组中最小的索引和最大的索引；intlo=0;inthi=a.length-1;//3.调用sort重载方法完成数组a中，从索引lo到索引hi的元素的排序sort(a,lo,hi);}/* 对数组a中从lo到hi的元素进行排序 */privatestaticvoidsort(Comparable[]a,intlo,inthi){//做安全性校验；if(hi<=lo){return;}//对lo到hi之间的数据进行分为两个组intmid=lo+(hi-lo)/2;// 5,9 mid=7//分别对每一组数据进行排序sort(a,lo,mid);sort(a,mid+1,hi);//再把两个组中的数据进行归并merge(a,lo,mid,hi);}/* 对数组中，从lo到mid为一组，从mid+1到hi为一组，对这两组数据进行归并 */privatestaticvoidmerge(Comparable[]a,intlo,intmid,inthi){//定义三个指针inti=lo;//定义一个指针，指向assist数组中开始填充数据的索引intp1=lo;//定义一个指针，指向第一组数据的第一个元素intp2=mid+1;//定义一个指针，指向第二组数据的第一个元素//遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处while(p1<=mid&&p2<=hi){//比较对应索引处的值if(less(a[p1],a[p2])){assist[i++]=a[p1++];}else{assist[i++]=a[p2++];}}//遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处while(p1<=mid){assist[i++]=a[p1++];}//遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处while(p2<=hi){assist[i++]=a[p2++];}//把辅助数组中的元素拷贝到原数组中for(intindex=lo;index<=hi;index++){a[index]=assist[index];}}}测试类:
publicstaticvoidmain(String[]args){Integer[]data={9,-16,21,23,-30,-49,21,30,30};System.out.println("排序之前：\n"+java.util.Arrays.toString(data));Merge.sort(data);System.out.println("排序之后：\n"+java.util.Arrays.toString(data));}代码实现 2:
MergeSort
publicclassMergeSort{publicstaticvoidmergeSort(int[]data){// 归并排序sort(data,0,data.length-1);}// 将索引从left到right范围的数组元素进行归并排序privatestaticvoidsort(int[]data,intleft,intright){if(left<right){//找出中间索引intcenter=(left+right)/2;sort(data,left,center);sort(data,center+1,right);//合并merge(data,left,center,right);}}// 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序privatestaticvoidmerge(int[]data,intleft,intcenter,intright){int[]tempArr=newint[data.length];intmid=center+1;intthird=left;inttemp=left;while(left<=center&&mid<=right){if(data[left]-data[mid]<=0){tempArr[third++]=data[left++];}else{tempArr[third++]=data[mid++];}}while(mid<=right){tempArr[third++]=data[mid++];}while(left<=center){tempArr[third++]=data[left++];}while(temp<=right){data[temp]=tempArr[temp++];}}publicstaticvoidmain(String[]args){int[]data={9,-16,21,23,-30,-49,21,30,30};System.out.println("排序之前：\n"+java.util.Arrays.toString(data));mergeSort(data);System.out.println("排序之后：\n"+java.util.Arrays.toString(data));}}对象排序:
publicclassMergeSort02{publicstaticvoidmergeSort(DataWrap[]data){// 归并排序sort(data,0,data.length-1);}// 将索引从left到right范围的数组元素进行归并排序privatestaticvoidsort(DataWrap[]data,intleft,intright){if(left<right){//找出中间索引intcenter=(left+right)/2;sort(data,left,center);sort(data,center+1,right);//合并merge(data,left,center,right);}}// 将两个数组进行归并，归并前两个数组已经有序，归并后依然有序privatestaticvoidmerge(DataWrap[]data,intleft,intcenter,intright){DataWrap[]tempArr=newDataWrap[data.length];intmid=center+1;intthird=left;inttemp=left;while(left<=center&&mid<=right){if(data[left].compareTo(data[mid])<=0){tempArr[third++]=data[left++];}else{tempArr[third++]=data[mid++];}}while(mid<=right){tempArr[third++]=data[mid++];}while(left<=center){tempArr[third++]=data[left++];}while(temp<=right){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("排序之前：\n"+java.util.Arrays.toString(data));mergeSort(data);System.out.println("排序之后：\n"+java.util.Arrays.toString(data));}}归并排序稳定
- 归并排序在归并的过程中，只有arr[i]<arr[i+1]的时候才会交换位置，如果两个元素相等则不会交换位置，所以它并不会破坏稳定性，归并排序是稳定的。
时间复杂度分析：
解析:
时间复杂度为O(nlogn);
归并排序的缺点：
- 需要申请额外的数组空间，导致空间复杂度提升，是典型的以空间换时间的操作。
归并排序与希尔排序性能测试：
importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.util.ArrayList;publicclassSortCompare{//调用不同的测试方法，完成测试publicstaticvoidmain(String[]args)throwsException{//1.创建一个ArrayList集合，保存读取出来的整数ArrayList<Integer>list=newArrayList<>();//2.创建缓存读取流BufferedReader，读取数据，并存储到ArrayList中；BufferedReaderreader=newBufferedReader(newInputStreamReader(SortCompare.class.getClassLoader().getResourceAsStream("reverse_arr.txt")));Stringline=null;while((line=reader.readLine())!=null){//line是字符串，把line转换成Integer，存储到集合中inti=Integer.parseInt(line);list.add(i);}reader.close();//3.把ArrayList集合转换成数组Integer[]a=newInteger[list.size()];list.toArray(a);//4.调用测试代码完成测试// testInsertion(a);// testShell(a); //17testMerge(a);}//测试希尔排序publicstaticvoidtestShell(Integer[]a){//1.获取执行之前的时间longstart=System.currentTimeMillis();//2.执行算法代码Shell.sort(a);//3.获取执行之后的时间longend=System.currentTimeMillis();//4.算出程序执行的时间并输出System.out.println("希尔排序执行的时间为："+(end-start)+"毫秒");}//测试插入排序publicstaticvoidtestInsertion(Integer[]a){//1.获取执行之前的时间longstart=System.currentTimeMillis();//2.执行算法代码Insertion.sort(a);//3.获取执行之后的时间longend=System.currentTimeMillis();//4.算出程序执行的时间并输出System.out.println("插入排序执行的时间为："+(end-start)+"毫秒");}//测试插入排序publicstaticvoidtestMerge(Integer[]a){//1.获取执行之前的时间longstart=System.currentTimeMillis();//2.执行算法代码Merge.sort(a);//3.获取执行之后的时间longend=System.currentTimeMillis();//4.算出程序执行的时间并输出System.out.println("归并排序执行的时间为："+(end-start)+"毫秒");}}通过测试，发现希尔排序和归并排序在处理大批量数据时差别不是很大。
但归并是稳定排序,希尔是非稳定排序
小结:
- 时间复杂度：T(n) = O(nlogn)
- 稳定
