排序算法之---归并排序

不多废话,直接上代码:
递归版本:

public static void mergeSort(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) {
	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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

然后迭代版归并:

public static void mergeSort(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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度: O(N * logN)

归并可解问题:

1. 小和问题: (依次找出所有左边比自己小的数相加的和)
   要求时间复杂度: O(N*logN)

   public static int smallSum(int[] arr) {
   	if(arr == null || arr.length < 2) {
   		return 0;
   	}
   	return process(arr, 0, arr.length - 1);
   }
   
   public static int process(int[] arr, int l, int r) {
   	if(l == r) {
   		return 0;
   	}
   	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) {
   	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
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36

2. 逆序对问题…