package 排序算法;
public class MergerSort {
public static void main(String[] args) {
int[] arr= {3,2,5,6};
System.out.println(mergerSort(arr));
System.out.println();
}
public static int mergerSort(int[] arr) {
if(arr==null||arr.length<2) {
return 0;
}
int res=mergerProcess(arr, 0, arr.length-1);
return res;
}
public static int mergerProcess(int[] arr, int L, int R) {
if(L==R) {
return 0;
}
int mid=(L+R)/2;
return mergerProcess(arr, L, mid)+
mergerProcess(arr, mid+1, R)+
merger(arr, L, mid, R);
}
public static int merger(int[] arr, int l, int mid, int r) {
int i=0;
int p1=l;
int p2=mid+1;
int[] help = new int[r-l+1];
int res=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(int k=0;k<help.length;k++) {
arr[l+k]=help[k];
}
return res;
}
}
2019-05-23归并排
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 今天是什么日子 起床：6点。 孩子上学，我都把常规闹铃定到5点。只是做了一夜的梦，中途还醒来。 睡前喝了两杯山楂酒...
