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 while
data[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 if
System.out.println("Not this one for " +paraKey);
tempPosition = (tempPosition + 1) % length;
} // Of while
return "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 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
/**
*********************
* 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
截图：
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）