Java学习-Day22

插入排序

一、描述

插入排序像什么？没错就像斗地主或者打麻将中码牌. 每次对一个牌进行排序, 从左到右是有先后顺序的. 和这个类似的叫做冒泡排序在后面也会提及.

插入排序是简单直接的排序方式之一. 代码非常短.每次保证前 i 个数据是有序的.

先做简单的事情 (第 1 轮最多有 1 次移动), 再做麻烦的事情 (最后一轮最多有 \(n - 1\) 次移动).

下标 0 的数据为岗哨, 与顺序查询同理. 比其它排序方式多用一个空间.

tempNode 只分配了引用 (指针) 的空间, 并未 new.

二、具体代码

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
/**
 *********************
 * Insertion sort. data[0] does not store a valid data. data[0].key should be
 * smaller than any valid key.
 *********************
 */
public void insertionSort() {
	DataNode tempNode;
	int j;
	for (int i = 2; i < length; i++) {
		tempNode = data[i];

		// Find the position to insert.
		// At the same time, move other nodes.
		for (j = i - 1; data[j].key > tempNode.key; j--) {
			data[j + 1] = data[j];
		} // Of for j

		// Insert.
		data[j + 1] = tempNode;

		System.out.println("Round " + (i - 1));
		System.out.println(this);
	} // Of for i
}// Of insertionSort

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

	System.out.println(tempDataArray);

	tempDataArray.insertionSort();
	System.out.println("Result\r\n" + tempDataArray);
}// Of insertionSortTest

三、运行截图

希尔排序

一、描述

希尔排序(Shell Sort)是插入排序的一种, 它是针对直接插入排序算法的改进.

希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名.

它通过比较相距一定间隔的元素来进行, 各趟比较所用的距离随着算法的进行而减小, 直到只比较相邻元素的最后一趟排序为止. 也就是说最后一趟还是要进行一次插入排序, 但是此时数组大多有序所以就不会耗费太多时间.

二、具体代码

虽然有四层循环, 但真实的希尔排序只有三层循环, 最后一层只是为了输出数组中的数字.

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
/**
 *********************
 * Shell sort. We do not use sentries here because too many of them are needed.
 *********************
 */
public void shellSort() {
	DataNode tempNode;
	int[] tempJumpArray = { 5, 3, 1 };
	int tempJump;
	int p;
	for (int i = 0; i < tempJumpArray.length; i++) {
		tempJump = tempJumpArray[i];
		for (int j = 0; j < tempJump; j++) {
			for (int k = j + tempJump; k < length; k += tempJump) {
				tempNode = data[k];
				// Find the position to insert.
				// At the same time, move other nodes.
				for (p = k - tempJump; p >= 0; p -= tempJump) {
					if (data[p].key > tempNode.key) {
						data[p + tempJump] = data[p];
					} else {
						break;
					} // Of if
				} // Of for p

				// Insert.
				data[p + tempJump] = tempNode;
			} // Of for k
		} // Of for j
		System.out.println("Round " + i);
		System.out.println(this);
	} // Of for i
}// Of shellSort

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

	System.out.println(tempDataArray);

	tempDataArray.shellSort();
	System.out.println("Result\r\n" + tempDataArray);
}// Of shellSortTest

三、运行截图

总结

在编写希尔排序时对成组那部分有些绕, 然后就是对 tempJumpArray 的选择在我看来也可能对排序速度产生影响.

总而言之希尔排序就像是特殊的插入排序.