归并排序
首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。
代码语言：javascript复制//递归版本
public class MergeSort {
public static void mergeSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
public static void process(int[] arr; int L; int R) {
if (L == R) {
return;
}
int mid = L (R-L)>>1; //获得当前数组中间位置
process(arr, L, mid); //对左右两部分分别排序
process(arr, mid 1, R);
merge(arr, L, mid, R); //左右排序后合并
}
public static void merge(int[] arr, int L, int M, int R) {
//建立辅助数组，比较左右两个数组的节点大小，小的放入help中，并移到下一位
int[] help = new int[R - L 1];
int i = 0;
int p1 = L;;
int p2 = M 1;
while (p1 <= M && p2 <= R) {
help[i ] = arr[p1] <= arr[p2] ? arr[p1 ] : arr[p2 ];
}
while (p1 <=M) {
help[i ] = arr[p1 ];
}
while (p2 <=R) {
help[i ] = arr[p2 ];
}
for (i = 0; i < help.length; i ) {
arr[L i] = help[i];
}
}
//非递归版本
//每次分的组 从 1 -> 2 -> 4 -> 8 -> 16。。。。。的大小递增
public static mergeSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
int mergeSize = 1;
while (mergeSize < N) {
int L = 0;
while (L < N) {
int M = L mergeSize - 1; //获得
if (M > N){
break;
}
int R = Math.min(M mergeSize, N - 1);
merge(arr, L, M, R);
L = R 1;
}
if (mergeSize > N/2) {
break;
}
mergeSize <<= 1;
}
}
}数组最小和问题
在一个数组中，一个数左边比它小的数的总和， 叫数的小和， 所有的数的小和累加起来， 叫数组小和，求数组小和。
代码语言：javascript复制public class MergeSort {
public static void mergeSort1(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
process(arr, 0, arr.length - 1);
}
public static void process(int[] arr; int L; int R) {
if (L == R) {
return;
}
int mid = L (R-L)>>1; //获得当前数组中间位置
return
process(arr, L, mid); //对左右两部分分别排序
process(arr, mid 1, R);
merge(arr, L, mid, R); //左右排序后合并
}
public static int merge(int[] arr, int L, int M, int R) {
//建立辅助数组，比较左右两个数组的节点大小，小的放入help中，并移到下一位
int[] help = new int[R - L 1];
int i = 0;
int p1 = L;;
int p2 = M 1;
int res = 0;
while (p1 <= M && p2 <= R) {
res = arr[p1] < arr[p2] ? (R - p2 1) * arr[p1] : 0;
help[i ] = arr[p1] < arr[p2] ? arr[p1 ] : arr[p2 ];
}
while (p1 <=M) {
help[i ] = arr[p1 ];
}
while (p2 <=R) {
help[i ] = arr[p2 ];
}
for (i = 0; i < help.length; i ) {
arr[L i] = help[i];
}
return res;
}
//非递归版本
//每次分的组 从 1 -> 2 -> 4 -> 8 -> 16。。。。。的大小递增
public static int mergeSort2(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int N = arr.length;
int mergeSize = 1;
while (mergeSize < N) {
int L = 0;
while (L < N) {
int M = L mergeSize - 1; //获得
if (M > N){
break;
}
int R = Math.min(M mergeSize, N - 1);
merge(arr, L, M, R);
L = R 1;
}
if (mergeSize > N/2) {
break;
}
mergeSize <<= 1;
}
return res;
}
}总结：遇见需要计算数组中右边的数有多少个数比左边小、一个数左边有多少数比右边大等问题
