归并排序以及求数组小和的问题

用户5513909

发布于 2023-04-25 11:30:51

1860

发布于 2023-04-25 11:30:51

归并排序

首先把一个未排序的序列从中间分割成2部分，再把2部分分成4部分，依次分割下去，直到分割成一个一个的数据，再把这些数据两两归并到一起，使之有序，不停的归并，最后成为一个排好序的序列。

//递归版本
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;
		}
	} 
}

数组最小和问题

在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有的数的小和累加起来，叫数组小和，求数组小和。

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;
	} 
}

总结：遇见需要计算数组中右边的数有多少个数比左边小、一个数左边有多少数比右边大等问题

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-19，如有侵权请联系 cloudcommunity@tencent.com 删除

int