Java学习-Day25

归并排序

一、描述

归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法, 该算法是采用分治法(Divide and Conquer）的一个非常典型的应用. 将已有序的子序列合并, 得到完全有序的序列

即先使每个子序列有序, 再使子序列段间有序. 若将两个有序表合并成一个有序表, 称为二路归并.

\(\log n\)轮, 每轮 \(O(n)\) 次拷贝. 因此时间复杂度为 \(O(n\log n)\)

空间复杂度为 \(O(n)\). 只需要一行辅助空间.

归并排序适用于数据量大, 并且对稳定性有要求的场景.

二、具体代码

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/**
 *********************
 * Merge sort. Results are stored in the member variable data.
 *********************
 */
public void mergeSort() {
	// Step 1. Allocate space.

	int tempRow; // The current row
	int tempGroups; // Number of groups
	int tempActualRow; // Only 0 or 1
	int tempNextRow = 0;
	int tempGroupNumber;
	int tempFirstStart, tempSecondStart, tempSecondEnd;
	int tempFirstIndex, tempSecondIndex;
	int tempNumCopied;
	for (int i = 0; i < length; i++) {
		System.out.print(data[i]);
	} // Of for i
	System.out.println();

	DataNode[][] tempMatrix = new DataNode[2][length];

	// Step 2. Copy data.
	for (int i = 0; i < length; i++) {
		tempMatrix[0][i] = data[i];
	} // Of for i

	// Step 3. Merge. log n rounds
	tempRow = -1;
	for (int tempSize = 1; tempSize <= length; tempSize *= 2) {
		// Reuse the space of the two rows.
		tempRow++;
		System.out.println("Current row = " + tempRow);
		tempActualRow = tempRow % 2;
		tempNextRow = (tempRow + 1) % 2;

		tempGroups = length / (tempSize * 2);
		if (length % (tempSize * 2) != 0) {
			tempGroups++;
		} // Of if
		System.out.println("tempSize = " + tempSize + ", numGroups = " + tempGroups);

		for (tempGroupNumber = 0; tempGroupNumber < tempGroups; tempGroupNumber++) {
			tempFirstStart = tempGroupNumber * tempSize * 2;
			tempSecondStart = tempGroupNumber * tempSize * 2 + tempSize;
			if (tempSecondStart > length - 1) {
				// Copy the first part.
				for (int i = tempFirstStart; i < length; i++) {
					tempMatrix[tempNextRow][i] = tempMatrix[tempActualRow][i];
				} // Of for i
				continue;
			} // Of if
			tempSecondEnd = tempGroupNumber * tempSize * 2 + tempSize * 2 - 1;
			if (tempSecondEnd > length - 1) {
				tempSecondEnd = length - 1;
			} // Of if

			System.out.println("Trying to merge [" + tempFirstStart + ", " + (tempSecondStart - 1) + "] with ["
					+ tempSecondStart + ", " + tempSecondEnd + "]");

			tempFirstIndex = tempFirstStart;
			tempSecondIndex = tempSecondStart;
			tempNumCopied = 0;
			while ((tempFirstIndex <= tempSecondStart - 1) && (tempSecondIndex <= tempSecondEnd)) {
				if (tempMatrix[tempActualRow][tempFirstIndex].key <= tempMatrix[tempActualRow][tempSecondIndex].key) {

					tempMatrix[tempNextRow][tempFirstStart
							+ tempNumCopied] = tempMatrix[tempActualRow][tempFirstIndex];
					tempFirstIndex++;
					System.out.println("copying " + tempMatrix[tempActualRow][tempFirstIndex]);
				} else {
					tempMatrix[tempNextRow][tempFirstStart
							+ tempNumCopied] = tempMatrix[tempActualRow][tempSecondIndex];
					System.out.println("copying " + tempMatrix[tempActualRow][tempSecondIndex]);
					tempSecondIndex++;
				} // Of if
				tempNumCopied++;
			} // Of while

			while (tempFirstIndex <= tempSecondStart - 1) {
				tempMatrix[tempNextRow][tempFirstStart + tempNumCopied] = tempMatrix[tempActualRow][tempFirstIndex];
				tempFirstIndex++;
				tempNumCopied++;
			} // Of while

			while (tempSecondIndex <= tempSecondEnd) {
				tempMatrix[tempNextRow][tempFirstStart
						+ tempNumCopied] = tempMatrix[tempActualRow][tempSecondIndex];
				tempSecondIndex++;
				tempNumCopied++;
			} // Of while
		} // Of for groupNumber

		System.out.println("Round " + tempRow);
		for (int i = 0; i < length; i++) {
			System.out.print(tempMatrix[tempNextRow][i] + " ");
		} // Of for j
		System.out.println();
	} // Of for tempStepSize

	data = tempMatrix[tempNextRow];
}// Of mergeSort

/**
 *********************
 * Test the method.
 *********************
 */
public static void mergeSortTest() {
	int[] tempUnsortedKeys = { 5, 3, 6, 10, 7, 1, 9 };
	String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
	DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents);

	System.out.println(tempDataArray);

	tempDataArray.mergeSort();
	System.out.println(tempDataArray);
}// Of mergeSortTest

三、运行截图

四、总结

相比起通过循环来实现归并排序, 使用递归的形式仿佛更容易实现.

小结

一、各大查找算法对比

查找算法 复杂度
顺序查找 \(O(n)\)
二分查找 \(O(n\log n)\)
哈希查找 \(O(1)\) (无冲突的情况下)

二、设计一个自己的 Hash 函数和一个冲突解决机制.

1. Hash 函数

找一个素数用于取模.

2. 冲突解决机制

采用链地址法, 当发生冲突时将冲突元素组织成为一个链表.

三、各大排序算法对比

排序算法 平均时间复杂度 空间复杂度 稳定性
插入排序 \(O(n)\) \(O(1)\) 稳定
希尔排序 \(O(n\log n)\) \(O(1)\) 不稳定
冒泡排序 \(O(n^2)\) \(O(1)\) 稳定
快速排序 \(O(n\log n)\) \(O(\log n)\) 不稳定
选择排序 \(O(n^2)\) \(O(1)\) 不稳定
堆排序 \(O(n\log n)\) \(O(1)\) 不稳定
归并排序 \(O(n\log n)\) \(O(n)\) 稳定

四、描述各种排序算法的特点和基本思想.

插入排序是每趟排序把元素插入到已排好序的数组中. 特点是稳定, 第 k 次排序后, 前 k 个元素已经是从小到大排好序的.

希尔排序是基于插入排序的一种排序算法, 思想是对长度为 n 的数组 s , 每趟排序基于间隔 h 分成几组, 对每组数据使用插入排序方法进行排序, 然后减小 h 的值, 这样刚开始时候虽然分组比较多, 但每组数据很少, h 减小后每组数据多但基本有序, 而插入排序对已经基本有序的数组排序效率较高.

冒泡排序思想很简单, 就是对每个下标 i, 取 j 从 0 到 n-1-i (n是数组长度)进行遍历. 如果两个相邻的元素 s[j] > s[j+1], 就交换, 这样每次最大的元素已经移动到了后面正确的位置.

快速排序是内排序中平均性能较好的排序, 思想是每趟排序时选取一个数据（通常用数组的第一个数）作为关键数据, 然后将所有比它小的数都放到它的左边, 所有比它大的数都放到它的右边. 特点是不稳定, 递归还容易栈溢出.

选择排序思想是对每个下标 i, 从 i 后面的元素中选择最小的那个和 s[i] 交换. 选择排序的特点: 不稳定, 每趟排序后前面的元素肯定是已经排好序的了, 每次排序后可以确定一个元素会在其最终位置上.

堆排序是基于选择排序的一种排序算法, 堆是一个近似完全二叉树的结构, 且满足子结点的键值或索引总是小于（或者大于）它的父节点. 代码中采用最大堆方式: 位于堆顶的元素总是整棵树的最大值, 每个子节点的值都比父节点小, 堆要时刻保持这样的结构, 所以一旦堆里面的数据发生变化, 要对堆重新进行一次构建.

归并排序的思想是将两个有序表合并成一个新的有序表, 即把待排序序列分为若干个子序列, 每个子序列是有序的. 然后再把有序子序列合并为整体有序序列. 即先划分为两个部分, 最后进行合并. 特点是稳定, 可以用在顺序存储和链式存储的结构.