归并排序及其衍生问题
1. 解题思路
归并排序的核心思想是先让序列的左半部分有序、再让序列的右半部分有序，最后从两个子序列（左右两半）从头开始逐次比较，往辅助序列中填较小的数。
以序列{2,1,4,3}为例，归并排序的过程大致如下
示意图
代码
package mySort;
public class mergeSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr={1,4,2,3,5};
printArray(arr);
mergeSort(arr,0,arr.length-1);
printArray(arr);
}
public static void mergeSort(int arr[],int l,int r){
if(l==r){
return ;
}
int mid=(l+r)/2;
mergeSort(arr,l,mid);
mergeSort(arr,mid+1,r);
merge(arr,l,mid,r);
}
private static void merge(int[] arr, int l, int mid, int r) {
int[] help=new int[r-l+1];
int p1=l;
int p2=mid+1;
int i=0;
while(p1<=mid&&p2<=r){
if(arr[p1]<arr[p2]){
help[i]=arr[p1];
i++;
p1++;
}else{
help[i]=arr[p2];
p2++;
i++;
}
}
while(p1<=mid){
help[i]=arr[p1];
p1++;
i++;
}
while(p2<=r){
help[i]=arr[p2];
i++;
p2++;
}
for(i=0;i<help.length;i++){
arr[l+i]=help[i];
}
}
public static void printArray(int arr[]){
if(arr==null || arr.length<2){
return ;
}
int i=0;
while(i<arr.length){
System.out.print(arr[i]+" ");
i++;
}
System.out.println();
}
}
小和问题
在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和。例如：
[1,3,4,2,5]
1左边比1小的数，没有；
3左边比4小的数，1；
4左边比4小的数，1、3；
2左边比2小的数，1；
5左边比5小的数，1、3、4、2；
所以小和为1+1+3+1+1+3+4+2 = 16
简单的做法就是遍历一遍数组，将当前遍历的数与该数之前数比较并记录小于该数的数。易知其时间复杂度为O(n^2)（0+1+2+……+n-1）。
更优化的做法是利用归并排序的并入逻辑
在归并的过程中比较，找出右边元素有多少比左边的元素大的。如上面的数组，1右边有4个比1大的，那么1会出现4次。
package mySort;
public class SmallSum {
public static int SmallSum(int arr[]){
if(arr==null||arr.length<2){
return 0;
}
return mergeSort(arr,0,arr.length-1);
}
private static int mergeSort(int[] arr, int l, int r) {
if(l==r){
return 0;
}
int mid=l+(r-l)/2;//防止int溢出
return mergeSort(arr,l,mid)+mergeSort(arr,mid+1,r)+merge(arr,l,mid,r);
}
private static int merge(int[] arr, int l, int mid, int r) {
int help[]=new int[r-l+1];
int p1=l;
int p2=mid+1;
int res=0;
int i=0;
while(p1<=mid&&p2<=r){
res+=arr[p1]<arr[p2]?arr[p1]*(r-p2+1):0;
help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=mid){
help[i++]=arr[p1++];
}
while(p2<=r){
help[i++]=arr[p2++];
}
for(i=0;i<help.length-1;i++){
arr[i]=help[i];
}
// TODO Auto-generated method stub
return res;
}
public static void printArray(int arr[]){
if(arr==null ||arr.length<2){
}
for(int i=0;i<arr.length-1;i++){
System.out.print(arr[i]+" ");
}
System.out.println(" ");
}
public static void main(String[] test){
int arr[]={1,3,4,2,5};
printArray(arr);
System.out.println(SmallSum(arr));
}
}
该算法在归并排序的基础上做了略微改动，即merge中添加了变量res记录每次并入操作应该累加的小和、mergeSort则将每次并入应该累加的小和汇总。此种做法的复杂度与归并排序的相同，优于遍历的做法。可以理解，依次求每个数的小和过程中有很多比较是重复的，而利用归并排序求小和时利用了并入的两个序列分别有序的特性省去了不必要的比较，如134并入25时，2>1直接推出2后面的数都>1，因此直接arr[p1]*(r-p2+1)即可。这在样本量不大的情况下看不出来优化的效果，试想一下如果样本量为2^32，那么依照前者求小和O(n^2)可知时间复杂度为O(21亿的平方)，而归并排序求小和则只需O(21亿*32)，足以见得O(n^2)和O(nlogn)的优劣。
逆序对问题
在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有的逆序对。
主要思想：
在归并的过程中比较，找出左边有多少数比右边的数大，有则产生逆序对，打印。
代码
package mySort;
public class SmallSum {
public static int SmallSum(int arr[]){
if(arr==null||arr.length<2){
return 0;
}
return mergeSort(arr,0,arr.length-1);
}
private static int mergeSort(int[] arr, int l, int r) {
if(l==r){
return 0;
}
int mid=(l+r)/2;
return mergeSort(arr,l,mid)+mergeSort(arr,mid+1,r)+merge(arr,l,mid,r);
}
private static int merge(int[] arr, int l, int mid, int r) {
int help[]=new int[r-l+1];
int p1=l;
int p2=mid+1;
int res=0;
int i=0;
while(p1<=mid&&p2<=r){
if(arr[p1]>arr[p2]){
res+=mid-p1+1;
int temp=p1;
while(p1<=mid){
System.out.print(arr[p1++]+""+arr[p2]+" ");
}
p1=temp;
System.out.println();
}
help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
}
while(p1<=mid){
help[i++]=arr[p1++];
}
while(p2<=r){
help[i++]=arr[p2++];
}
for(i=0;i<help.length-1;i++){
arr[i]=help[i];
}
// TODO Auto-generated method stub
return res;
}
public static void printArray(int arr[]){
if(arr==null ||arr.length<2){
}
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.println(" ");
}
public static void main(String[] test){
int arr[]={3,2,1};
printArray(arr);
System.out.println(SmallSum(arr));
}
}
