黑马程序员技术交流社区
标题:
归并排序与逆序数
[打印本页]
作者:
syd957594556
时间:
2016-6-7 22:38
标题:
归并排序与逆序数
[java]
view plain
copy
package MyGuiBing;
public class GuiBingPaiXu {
static int count;//新增
/*
* 归并排序+逆序数
*
* 与归并排序比较 增加了两行核心代码
*
*
* 如果i<j而且 a
>a[j] 成为逆序数
*
* */
public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] a = { 26,5,77,1,61,11,59,15,48,19 };
//int[] a={4,3,6,5,1,2};
int[] a={2,4,3,1};
sop(a);
Guibing(a, 0, a.length - 1);
sop(a);
System.out.println(count);
}
public static void sop(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr
+ "\t");
}
System.out.println();
}
public static void Guibing(int[] n, int first, int last) {
if (first < last) {
int mid = (first + last) / 2;
//左边
Guibing(n, first, mid);
//右边
Guibing(n, mid + 1, last);
//左右归并
Mes(n, first, mid, last);
}
}
public static void Mes(int[] a, int first, int mid, int last) {
int[] temp = new int[a.length];
int i = first;
int j = mid + 1;
int m = mid, n = last;
int k = 0;
//把较小的数先移到新数组中
while (i <= m && j <= n) {
if (a
<= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
count +=mid-i+1;// 逆序数 核心代码
}
}
//把左边剩余的数先移到新数组中
while (i <= m) {
temp[k++] = a[i++];
}
//把右边剩余的数移到新数组中
while (j <= m) {
temp[k++] = a[j++];
}
//把新数组中的元素 覆盖到 a数组中
for (int p = 0; p < k; p++) {
a[first + p] = temp[p];
}
}
}
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2
