记java归并排序

(Updated: )
java 
1
2
3
4
5
6
7
8
9
10
11
static int[] sort(int[] A, int low, int high) {

		if (low < high) {
			int mid = (low + high) / 2;
			sort(A, low, mid);
			sort(A, mid + 1, high);
			merge(A, low, mid, high);
		}

		return A;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void merge(int[] A, int low, int mid, int high) {
	int n1 = mid - low + 1, n2 = high - mid, i, j, k;
	int[] L = new int[high - low + 1], R = new int[high - low + 1];

	for (i = 0; i < n1; i++)
		L[i] = A[low + i];

	for (j = 0; j < n2; j++)
		R[j] = A[mid + j + 1];

	L[n1] = Integer.MAX_VALUE;
	R[n2] = Integer.MAX_VALUE;
	i = j = 0;

	for (k = low; k < high + 1; k++) {
		if (L[i] < R[j]) {
			A[k] = L[i];
			i++;
		} else {
			A[k] = R[j];
			j++;
		}
	}
}
1
2
3
4
5
6
int[] arr = { 8, 3, 6, 4, 2 };

		System.out.println(Arrays.toString(arr));
		// System.err.println(Arrays.toString(sort(arr, 0, arr.length - 1)));
		// System.err.println(Arrays.toString(sort(arr, 0, arr.length - 1)));
		System.err.println(Arrays.toString(s(arr)));

使用分治法分而治之，时间复杂度O(nlogn)，空间复杂度O(n)