学习来源：日撸 Java 三百行（41-50天，查找与排序）_闵帆的博客-CSDN博客

42 哈希表

42.1 使用 (最简单的) 除数取余法获得数据存放地址 (下标)。

42.2 使用 (最简单的) 顺移位置法解决冲突。

代码：

/********************** The second constructor. For Hash code only. It is assumed that* paraKeyArray.length <= paraLength.* * @param paraKeyArray     The array of the keys.* @param paraContenArray  The array of contents.* @param paraLength       The space for the Hash table.********************/public DataArray(int[] paraKeyArray, String[] paraContentArray, int paraLength) {// Step 1. Initialize.length = paraLength;data = new DataNode[length];for (int i = 0; i < length; i++) {data[i] = null;} // Of for i// Step 2. Fill the data.int tempPosition;for (int i = 0; i < paraKeyArray.length; i++) {// Hash.tempPosition = paraKeyArray[i] % paraLength;// Find an empty position.while (data[tempPosition] != null) {tempPosition = (tempPosition + 1) % paraLength;System.out.println("Collision, move forward for key " + paraKeyArray[i]);} // Of whiledata[tempPosition] = new DataNode(paraKeyArray[i], paraContentArray[i]);} // Of for i} // Of the second constructor/********************** Hash search.* * @param paraKey The given key.* @return The content of the key.********************/public String hashSearch(int paraKey) {int tempPosition = paraKey % length;while (data[tempPosition] != null) {if (data[tempPosition].key == paraKey) {return data[tempPosition].content;} // Of ifSystem.out.println("Not this one for " +paraKey);tempPosition = (tempPosition + 1) % length;} // Of whilereturn "null";} // Of hashSearch/********************** Test the method.********************/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/************************ The entrance of the program.* * @param args*            Not used now.**********************/public static void main(String[] args) {System.out.println("\r\n-------------sequentialSearchTest-------------");sequentialSearchTest();System.out.println("\r\n-------------binarySearchTest-------------");binarySearchTest();System.out.println("\r\n-------------hashSearchTest-------------");hashSearchTest();} // Of main

截图：

43 插入排序

43.1 插入排序是简单直接的排序方式之一。

43.2 每次保证前 i 个数据是有序的。

43.3 下标 0 的数据为岗哨。

代码：

	/********************** 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 inset.// 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/************************ The entrance of the program.* * @param args*            Not used now.**********************/public static void main(String[] args) {System.out.println("\r\n-------------sequentialSearchTest-------------");sequentialSearchTest();System.out.println("\r\n-------------binarySearchTest-------------");binarySearchTest();System.out.println("\r\n-------------hashSearchTest-------------");hashSearchTest();System.out.println("\r\n-------------insertionSort-------------");insertionSortTest();} // Of main} // Of class DataArray

截图：

44 希尔排序

44.1 达 4 重循环, 但时间复杂度只有O(n^2)。

44.2 岗哨的个数与最初的步长相关。

代码：

	/********************** Shell sort. We do not use sentries here because too many of them are neded.********************/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 tiome, 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 jSystem.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/************************ The entrance of the program.* * @param args*            Not used now.**********************/public static void main(String[] args) {System.out.println("\r\n-------------sequentialSearchTest-------------");sequentialSearchTest();System.out.println("\r\n-------------binarySearchTest-------------");binarySearchTest();System.out.println("\r\n-------------hashSearchTest-------------");hashSearchTest();System.out.println("\r\n-------------insertionSort-------------");insertionSortTest();System.out.println("\r\n-------------shellSort-------------");shellSortTest();} // Of main

截图：