学习来源：https://blog.csdn.net/minfanphd/article/details/116974889
顺序查找与折半查找1、顺序查找使用岗哨可以节约一半的时间. 为此, 第 0 个位置不可以放有意义的数据, 即有效数据只有 length - 1 个.
2、顺序查找时间复杂度为 O ( n ) O(n) O(n).
3、折半查找时间复杂度为 O ( log n ) O(log n) O(logn).
4、书上为简化起见, 只关注键. 这里使用键值对来表示一条完整的数据. 实际应用中可以把 content 改成任何想要的数据类型.
5、加上上一节的代码，下面的代码只是增加了hash查找相关的功能函数。大部分代码仍然是上一节的代码，不用重复写，接着上一节的写就行.
package SearchAndSort;
public class DataArray {
class DataNode{
int key;
String content;
DataNode(int paraKey, String paraContent){
key = paraKey;
content = paraContent;
}//Of the first constructor
public String toString() {
return "(" + key + " , " + content + ") ";
}//Of toString
}//of class DataNode
DataNode[] data;
int length;
public DataArray(int[] paraKeyArray, String[] paraContentArray) {
length = paraKeyArray.length;
data = new DataNode[length];
for(int i=0; i= 0 since data[0].key = paraKey.
// In this way the runtime is saved about 1/2.
// This for statement is equivalent to
//for (i = length - 1; data[i].key != paraKey; i--);
for (i = length - 1; data[i].key != paraKey; i--) {
;
}//Of for i
return data[i].content;
}// Of sequentialSearch
public static void sequentialSearchTest() {
int[] tempUnsortedKeys = {-1, 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);
System.out.println("Search result of 10 is: " + tempDataArray.sequentialSearch(10));
System.out.println("Search result of 10 is: " + tempDataArray.sequentialSearch(5));
System.out.println("Search result of 10 is: " + tempDataArray.sequentialSearch(4));
}// Of sequentialSearchTest
public String binarySearch(int paraKey) {
int tempLeft = 0;
int tempRight = length - 1;
int tempMiddle = (tempLeft + tempRight) / 2;
while(tempLeft <= tempRight) {
tempMiddle = (tempLeft + tempRight) / 2;
if(data[tempMiddle].key == paraKey) {
return data[tempMiddle].content;
}else if(data[tempMiddle].key <= paraKey) {
tempLeft = tempMiddle + 1;
}else {
tempRight = tempMiddel - 1;
}//Of if
}//Of while
//Not found.
return "null";
}//Of binarySearch
public static void binarySearchTest() {
int[] tempSortedKeys = { 1, 3, 5, 6, 7, 9, 10 };
String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
DataArray tempDataArray = new DataArray(tempSortedKeys, tempContents);
System.out.println(tempDataArray);
System.out.println("Search result of 10 is: " + tempDataArray.binarySearch(10));
System.out.println("Search result of 10 is: " + tempDataArray.binarySearch(5));
System.out.println("Search result of 10 is: " + tempDataArray.binarySearch(4));
}// Of binarySearchTest
public static void main(String[] args) {
System.out.println("rn-------sequentialSearchTest-------");
sequentialSearchTest();
System.out.println("rn-------binarySearchTest-------");
binarySearchTest();
}//Of main
}//Of class DataArray
哈希表
1、神奇、实用、粗暴的方法. 空间换时间.
2、保证空间足够.
3、在构造方法中装入数据. 自己可以写代码增加数据.
4、使用 (最简单的) 除数取余法获得数据存放地址 (下标).
5、使用 (最简单的) 顺移位置法解决冲突.
6、搜索的时间复杂度仅与冲突概率相关, 间接地就与装填因子相关. 如果空间很多, 可以看出时间复杂度为 O ( 1 ) 。
package SearchAndSort;
public class DataArray {
class DataNode{
int key;
String content;
DataNode(int paraKey, String paraContent){
key = paraKey;
content = paraContent;
}//Of the first constructor
public String toString() {
return "(" + key + " , " + content + ") ";
}//Of toString
}//of class DataNode
DataNode[] data;
int length;
public DataArray(int[] paraKeyArray, String[] paraContentArray) {
length = paraKeyArray.length;
data = new DataNode[length];
for(int i=0; i= 0 since data[0].key = paraKey.
// In this way the runtime is saved about 1/2.
// This for statement is equivalent to
//for (i = length - 1; data[i].key != paraKey; i--);
for (i = length - 1; data[i].key != paraKey; i--) {
;
}//Of for i
return data[i].content;
}// Of sequentialSearch
public static void sequentialSearchTest() {
int[] tempUnsortedKeys = {-1, 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);
System.out.println("Search result of 10 is: " + tempDataArray.sequentialSearch(10));
System.out.println("Search result of 10 is: " + tempDataArray.sequentialSearch(5));
System.out.println("Search result of 10 is: " + tempDataArray.sequentialSearch(4));
}// Of sequentialSearchTest
public String binarySearch(int paraKey) {
int tempLeft = 0;
int tempRight = length - 1;
int tempMiddle = (tempLeft + tempRight) / 2;
while(tempLeft <= tempRight) {
tempMiddle = (tempLeft + tempRight) / 2;
if(data[tempMiddle].key == paraKey) {
return data[tempMiddle].content;
}else if(data[tempMiddle].key <= paraKey) {
tempLeft = tempMiddle + 1;
}else {
tempRight = tempMiddel - 1;
}//Of if
}//Of while
//Not found.
return "null";
}//Of binarySearch
public static void binarySearchTest() {
int[] tempSortedKeys = { 1, 3, 5, 6, 7, 9, 10 };
String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" };
DataArray tempDataArray = new DataArray(tempSortedKeys, tempContents);
System.out.println(tempDataArray);
System.out.println("Search result of 10 is: " + tempDataArray.binarySearch(10));
System.out.println("Search result of 10 is: " + tempDataArray.binarySearch(5));
System.out.println("Search result of 10 is: " + tempDataArray.binarySearch(4));
}// Of binarySearchTest
public DataArray(int[] paraKeyArray, String[] paraContentArray, int paraLength) {
//Step 1. Initialize.
length = paraLength;
data = new DataNode[length];
for(int i=0; i 
