One , Several common sorting algorithms are introduced ： Direct insertion sort , Simple selection sort , Bubble sort , Quick sort .

1, Direct insertion sort

describe ： In the set of numbers to sort , Suppose the front (n-1)[n>=2] The number is already in order ,
Now we're going to put the n The number is inserted into the preceding ordinal number , Make this n The number is also arranged in order .
And so on , Until it's all in order .

algorithm ： From the second number ( Current number ) start , Take it with the previous number ( Comparison number ) compare
-- If the comparison number is greater than the current number , Let the comparator move back one bit , Compare the current number with the first digit of the comparison , And so on
-- otherwise , Insert the current number at this location

code implementation ：
public static void Zhijie(int[] array) { for (int i = 1; i < array.length;
i++) { int temp = array[i]; int j = i - 1; for (; j >= 0; j--) { if (array[j] >
temp) { array[j + 1] = array[j]; } else { break; } } array[j + 1] = temp; } }
2, Simple selection sort

describe ： In the set of numbers to sort , Choose the smallest number and exchange it with the number in the first position ; Then find the smallest of the remaining numbers and exchange them with the number in the second position , So loop until the penultimate number is compared with the last .

in other words , Take the first and the second , Third , The fourth ... than , The first one is the smallest ; Then take the second and the third , The fourth , The fifth ... than , The second smallest after the match ; and so on .

code implementation ：
public static void Jiandan(int[] array) { for (int i = 0; i < array.length -
1; i++) { for (int j = i + 1; j < array.length; j++) { if (array[i] > array[j])
{ int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } }
3, Bubble sort

describe ： Compare adjacent elements . If the first is bigger than the second , Just exchange the two of them . Do the same for each pair of adjacent elements , From the first pair at the beginning to the last pair at the end . At this point , The last element should be the largest number . Repeat the above steps for all elements , Except for the last one . Continue to repeat the above steps for fewer and fewer elements at a time , Until no pair of numbers need to be compared .

code implementation ：
public static void Maopao(int[] array) { for (int i = array.length - 1; i > 0;
i--) { for (int j = 0; j < array.length - 1; j++) { if (array[j] > array[j +
1]) { int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } }
4, Quick sort

describe ： Think of the entire sequence as an array , Think of the zero position as the center axis , Compared with the last one , If it's smaller than that, exchange , It's bigger than it does nothing ; And then compare it with the smaller one , It's smaller than it doesn't exchange , More than him . This goes on and on , One pass sorting completed , The one on the left is smaller than the center axis , On the right is bigger than the center axis , Then divide and conquer ( recursion ) method , Sort the two separate arrays separately .

code implementation ：
public static void Kuaisu(int[] array) { if (array.length > 0) { _quick(array,
0, array.length - 1); } } // recursion private static void _quick(int[] array, int
low, int hight) { if (low < hight) { int mid = quick(array, low, hight);
_quick(array, 0, mid - 1); _quick(array, mid + 1, hight); } } // Find the center axle private
static int quick(int[] array, int low, int hight) { int temp = array[low];
while (low < hight) { while (low < hight && array[hight] > temp) { hight--; }
array[low] = array[hight]; while (low < hight && array[low] < temp) { low++; }
array[hight] = array[low]; } array[low] = temp; return low; }
Two , Several common search algorithms are introduced ： Search order , Binary search , Block search , hash search .

Direct code ：
/** * Average time complexity of sequential search O（n） * * @param searchKey * Value to find * @param array *
array （ Find from this array ） * @return Find results （ The subscript position of the array ） */ public static int orderSearch(int
searchKey, int[] array) { if (array == null || array.length < 1) return -1; for
(int i = 0; i < array.length; i++) { // Traversal array , Until we find it if (array[i] == searchKey)
{ return i; } } return -1; } /** * Binary search is also called binary search , It is an efficient search method .
【 Binary search requirements 】：1. The sequential storage structure must be adopted 2. Must be ordered by keyword size . * * @param array * Ordered array * * @param
searchKey * Find element * * @return searchKey Array subscript of , No return found -1 */ public static int
binarySearch(int[] array, int searchKey) { // Non recursion of binary search int low = 0; // First index
int high = array.length - 1; // Last highest order index while (low <= high) { int middle =
(low + high) / 2; // Middle position index if (searchKey == array[middle]) { //
If it is equal to the intermediate value , eureka , Direct return return middle; } else if (searchKey < array[middle]) { //
If the lookup value is less than the intermediate value high = middle - 1; // Continue binary search in the previous block } else { // If the lookup value is greater than the intermediate value low =
middle + 1; // Continue the binary search in the next block } } return -1; } public static int BinSearch(int
Array[], int low, int high, int key/* Value to find */) { // Recursion of binary search if (low <= high) {
int mid = (low + high) / 2; if (key == Array[mid]) { return mid; } else if (key
< Array[mid]) { return BinSearch(Array, low, mid - 1, key); } else if (key >
Array[mid]) { return BinSearch(Array, mid + 1, high, key); } } else { return
-1; } return -1; } /** * Block search *
1. First, the lookup table is divided into several blocks , The storage of data elements in each block is arbitrary , But blocks have to be ordered （ Suppose this sort is incremented by keyword value , That is to say, any one of the first pieces *
All data elements in the keyword are less than the data elements in the second block , The keyword of any data element in the second block is less than that of all data elements in the third block , And so on ）; *
2. Create an index table , The largest key value in each block is stored in an auxiliary array in the order of blocks , The index table is also in ascending order ; *
3. When searching, first search in the index table with the given key value , Determine which block the data elements that meet the conditions are stored in , The search method can be a binary method , It can also be a sequential search . *
4. Then search the corresponding block in order , You can get the result of the search . * * @param index * Index table , The maximum value of each block is placed * @param st * Sequence table ,
* @param key * Value to find * @param m * The length of each block in the sequence table is equal , by m * @return */ public static int
blockSearch(int[] index, int[] st, int key, int m) { //
In sequence st Array , Using block search method to find the keyword is key Record of // 1. stay index[ ] Half search , What are you looking for key In which block int i =
binarySearch(index, key); if (i >= 0) { int j = i > 0 ? i * m : i; int len = (i
+ 1) * m; // Search in the determined block with the sequential search method key for (int k = j; k < len; k++) { if (key ==
st[k]) { System.out.println(" query was successful "); return k; } } }
System.out.println(" Search failed "); return -1; } /** *
Hash table lookup is based on the key value of the record , Get the address of the node directly , It is a direct conversion method from keyword to address , No need to compare again and again . hypothesis f contain n Nodes ,Ri Is one of the nodes （1≤i≤n）,keyi Is its key value , stay keyi And Ri To establish a functional relationship between the addresses of , This function can be used to convert the key value to the address of the corresponding node , Yes ：addr(Ri)=H(keyi),addr(Ri) Is a hash function .
* There are two ways to resolve conflicts ： (1) Open address method *
If both data elements have the same hash value , In the hash table, select another table entry for the later inserted data element . When the program looks up the hash table , If the corresponding data element in the hash table is not found , The program will continue to look back , Until you find a data element that meets the search requirements , Or an empty table entry was encountered .
* (2) Chain address method Data elements with the same hash value are stored in a linked list , In the process of looking up the hash table , When the linked list is found , A linear search method must be used . Hash lookup * *
@param hash * @param hashLength * @param key * @return */ public static int
searchHash(int[] hash, int hashLength, int key) { // hash function int hashAddress = key
% hashLength; // appoint hashAdrress The corresponding value exists but is not a key value , Open addressing is used to solve the problem while (hash[hashAddress] !=