一看就会的归并排序（java版）

思想（分治）

1.确定分界点 mid=（l+r）/2 2.递归排序 3.归并（合二为一）

详解

1.归并时，只需要开一个辅助数组 2.以mid为分界，双指针进行判断，如果arr[index1]<arr[index2],就将arr[index]的值放入辅助数组中去，然后指针后移，直至有一个指针到达边界 3.将另外没有比较完的数组全部放入辅助数组中去 4.将辅助数组克隆到原数组中

时间复杂度分析

1.每次将原数组分为一半，需要log n 2.每层的排序只需要扫一遍，需要 n 3.时间复杂度为：O(n log(n) )

模板

//二分 static void Binary(int[] arr,int low,int high){ if (low<high){ int mid=(low+high)/2; Binary(arr,low,mid); Binary(arr,mid+1,high); Merging(arr,low,mid,high); } } //归并 static void Merging(int[] arr,int low,int mid,int high){ int[] other=new int[arr.length]; //辅助数组 int index1=low; int index2=mid+1; int count=low; while (index1<=mid&&index2<=high){ if (arr[index1]<arr[index2]){ other[count++]=arr[index1++]; }else{ other[count++]=arr[index2++]; } } //将未比较的数放入辅助数组中 while (index1<=mid){ other[count++]=arr[index1++]; } while (index2<=high){ other[count++]=arr[index2++]; } //将排好序的数组放回到原来的数组中 for (int i = low; i <=high ; i++) { arr[i]=other[i]; } }

补充（递归求逆序对）

逆序对概念：

i<j arr[i]>arr[j]

模板

//归并 static void Merging(int[] arr,int low,int mid,int high){ int[] other=new int[arr.length]; //辅助数组 int index1=low; int index2=mid+1; int count=low; while (index1<=mid&&index2<=high){ if (arr[index1]<arr[index2]){ other[count++]=arr[index1++]; }else{ other[count++]=arr[index2++]; cnt += mid -index1 +1;//将逆序对的个数累加起来 } } //将未比较的数放入辅助数组中 while (index1<=mid){ other[count++]=arr[index1++]; } while (index2<=high){ other[count++]=arr[index2++]; } //将排好序的数组放回到原来的数组中 for (int i = low; i <=high ; i++) { arr[i]=other[i]; } }