- 2020-07-13 05:43
*views 6*- Algorithm and data structure
- Java

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] !=

0 && hash[hashAddress] != key) { hashAddress = (++hashAddress) % hashLength; }

// Open unit found , Indicates that the search failed if (hash[hashAddress] == 0) return -1; return hashAddress; }

/** * Data insertion Hash surface * * @param hash * Hashtable * @param hashLength * @param data */

public static void insertHash(int[] hash, int hashLength, int data) { // hash function

int hashAddress = data % hashLength; // If key existence , It means it has been occupied by someone else , The conflict must be resolved at this point while

(hash[hashAddress] != 0) { // Find by open addressing hashAddress = (++hashAddress) %

hashLength; } // take data Put it in the dictionary hash[hashAddress] = data; }

Technology

Daily Recommendation

views 5

views 4

views 3

©2019-2020 Toolsou All rights reserved,

（ Super detail ）Eclipse Using tutorials —— use Eclipse Create first HelloWorld! Database operation 5 code implementation mysql Addition, deletion, modification and query of database What can MCU do , Do you have any interesting works made by MCU or open source hardware Go to the interview after reading this , Steady over ~~ Single linked list of primary data structure （C Language implementation ）SQL Comprehensive questions Employee unit comprehensive questions Python Implementation of Hanoi Tower code VHDL——JK trigger It's over , Starting salary 30k