学习来源：日撸 Java 三百行（41-50天，查找与排序）
第 42 天: 哈希表使用 (最简单的) 除数取余法获得数据存放地址 (下标)。
使用 (最简单的) 顺移位置法解决冲突。
搜索的时间复杂度仅与冲突概率相关， 间接地就与装填因子相关。如果空间很多，可以看出时间复杂度为 O(1)。
输入：输入整型数组tempUnsortedKeys和字符数组tempContents构造数据数组tempDataArray
输出：通过哈希表查找指定key的元素中的内容content
优化目标：无
public DataArray(int[] paraKeyArray, String[] paraContentArray, int paraLength) {
length = paraLength;
data = new DataNode[length];
for (int i = 0; i < length; i++) {
data[i] = null;
} // Of for i
int tempPosition;
for (int i = 0; i < paraKeyArray.length; i++) {
tempPosition = paraKeyArray[i] % paraLength;
while (data[tempPosition] != null) {
tempPosition = (tempPosition + 1) % paraLength;
System.out.println("Collision, move forward for key " + paraKeyArray[i]);
} // Of while
data[tempPosition] = new DataNode(paraKeyArray[i], paraContentArray[i]);
} // Of for i
}// Of the second constructor
public String hashSearch(int paraKey) {
int tempPosition = paraKey % length;
while (data[tempPosition] != null) {
if (data[tempPosition].key == paraKey) {
return data[tempPosition].content;
} // Of if
System.out.println("Not this one for " + paraKey);
tempPosition = (tempPosition + 1) % length;
} // Of while
return "null";
}// Of hashSearch
public static void hashSearchTest() {
int[] tempUnsortedKeys = { 16, 33, 38, 69, 57, 95, 86 };
String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents, 19);
System.out.println(tempDataArray);
System.out.println("Search result of 95 is: " + tempDataArray.hashSearch(95));
System.out.println("Search result of 38 is: " + tempDataArray.hashSearch(38));
System.out.println("Search result of 57 is: " + tempDataArray.hashSearch(57));
System.out.println("Search result of 4 is: " + tempDataArray.hashSearch(4));
}// Of hashSearchTest
public static void main(String args[]) {
System.out.println("rn-------sequentialSearchTest-------");
sequentialSearchTest();
System.out.println("rn-------binarySearchTest-------");
binarySearchTest();
System.out.println("rn-------hashSearchTest-------");
hashSearchTest();
}// Of main
运行截图：
插入排序是简单直接的排序方式之一，每次保证前 i 个数据是有序的。
先做简单的事情 (第 1 轮最多有 1 次移动)，再做麻烦的事情 (最后一轮最多有n−1 次移动)。下标 0 的数据为岗哨， 与 41 天内容同理， 比其它排序方式多用一个空间。
输入：输入整型数组tempUnsortedKeys和字符数组tempContents构造数据数组tempDataArray
输出：输出对tempDataArray 进行插入排序的排序过程以及排序后的升序序列
优化目标：无
public void insertionSort() {
DataNode tempNode;
int j;
for (int i = 2; i < length; i++) {
tempNode = data[i];
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
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("Resultrn" + tempDataArray);
}// Of insertionSortTest
public static void main(String args[]) {
System.out.println("rn-------sequentialSearchTest-------");
sequentialSearchTest();
System.out.println("rn-------binarySearchTest-------");
binarySearchTest();
System.out.println("rn-------hashSearchTest-------");
hashSearchTest();
System.out.println("rn-------insertionSortTest-------");
insertionSortTest();
}// Of main
运行截图：
输入：输入整型数组tempUnsortedKeys和字符数组tempContents构造数据数组tempDataArray
输出：输出对tempDataArray 进行希尔排序的排序过程以及排序后的升序序列
优化目标：无
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];
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
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("Resultrn" + tempDataArray);
}// Of shellSortTes
public static void main(String args[]) {
System.out.println("rn-------sequentialSearchTest-------");
sequentialSearchTest();
System.out.println("rn-------binarySearchTest-------");
binarySearchTest();
System.out.println("rn-------hashSearchTest-------");
hashSearchTest();
System.out.println("rn-------insertionSortTest-------");
insertionSortTest();
System.out.println("rn-------shellSortTest-------");
shellSortTest();
}// Of main
运行截图：
