Hi, I’m Koba.
For programming, only to master the algorithm is to understand the soul of programming, algorithm for beginners, it is really a little difficult, but in the future to have better development, get better progression, systematic learning of the algorithm is the most important.
For Java programmers, this back-end language is just our external work, we are more to learn its syntax, framework and some tools to use. The algorithm is our real internal work, it is more concerned with how to design the system, how to write high-performance code, and constantly cultivate our thinking ability, so as to improve our work efficiency.
Koha today is to introduce some classical algorithms we need to understand in Java, I hope you can taste the beauty and strangeness of algorithms from these classical algorithms, have interest in her, better for our career development power forward. Okay, let’s move on to our text:
Binary search
Introduction to the
Basic idea: also called semicolon search, requires the order of the sequence to be searched, is a fast search algorithm, the time complexity is O(logn), requires that the data set is an ordered data set.
use
Application scenario: It is used to search for array elements, and the array must be sorted (usually in ascending order) before searching.
Steps:
1. Compare the value of the middle position with the keyword to be searched. If the value of the middle position is larger than the keyword to be searched, the search process is repeated in the first half.
2. If the value in the middle is smaller than the keyword to be searched, the search process is repeated in the second half.
3. There is no keyword in the sequence until it is found.
Code examples:
public static int biSearch(int []array,int a){
int lo=0;
int hi=array.length-1;
int mid;
while(lo<=hi){
mid=(lo+hi)/2;// Middle position
if(array[mid]==a){
return mid;
}else if(array[mid]<a){ // Go to the right
lo=mid+1;
}else{ // look left
hi=mid-1; }}return -1;
}
Copy the codeBubble sort algorithm
Introduction to the
Basic idea: compare two adjacent data, if the previous data is larger than the next data, the two data exchange. After traversing the array from 0 to n-1, the largest data “sinks” to the n-1 position. N= n-1, if N is not 0 repeat the previous two steps, otherwise the sorting is complete.
use
Application scenario: The data volume is small, the stability is required, and the data is basically orderly.
Steps:
1. Compare all the elements in the sequence in pairs, placing the largest element at the end.
2. Compare all elements in the remaining sequence in pairs, placing the largest element at the end.
3. Repeat step 2 until only one number remains.
Code examples:
public static void bubbleSort1(int [] a, int n){
int i, j;
for(i=0; i<n; i++){// indicates n sorting processes.
for(j=1; j<n-i; j++){
if(a[j-1] > a[j]){// If the preceding number is greater than the following number, swap
// Switch a[j-1] and a[j]
int temp;
temp = a[j-1];
a[j-1] = a[j]; a[j]=temp; }}}}Copy the codeInsertion sort algorithm
Introduction to the
Basic idea: By constructing ordered sequence, for unordered data, scan from back to front in sorted sequence, find corresponding position and insert.
use
Application scenario: The amount of data is small, the stability of the algorithm is required, and the data is in partial or overall order.
Steps:
1. The first element of the first to be sorted sequence is regarded as an ordered sequence, and the second element to the last element is regarded as an unsorted sequence.
2. Scan the unordered sequence from beginning to end, inserting each scanned element into the appropriate place of the ordered sequence. (If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.)
Code examples:
public class InsertSort implements IArraySort {
@Override
public int[] sort(int[] sourceArray) throws Exception {
// Copy the arR without changing the parameters
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
// Select the appropriate place to insert from the element with subscript 1, since there is only one element with subscript 0 and the default is ordered
for (int i = 1; i < arr.length; i++) {
// Record the data to be inserted
int tmp = arr[i];
// Start from the rightmost of the sorted sequence and find the number less than it
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
// There is a smaller number, insert
if (j != i) {
arr[j] = tmp;
}
}
returnarr; }}Copy the codeQuicksort algorithm
Introduction to the
Basic idea: Select a key value as a reference value. Anything less than the base value is in the left-hand sequence (generally unordered), and anything larger than the base value is in the right-hand sequence (generally unordered). The first element of the sequence is generally selected.
use
Application scenario: When the value range is large, the probability of the same value is small, and the data volume is large and the stability is not considered, the power is greater when the value is much larger than the data volume.
Steps:
1, a cycle, from the back to the front, compared with the base value and the last value, if the exchange position is smaller than the base value, if there is no continue to compare the next, until the first value is found smaller than the base value before exchange.
2, after finding the value, and start to compare from front to back, if there is a greater than the base value, switch positions, if there is no continue to compare the next, until find the first value greater than the base value before switching.
3, until the front to back comparison index > from back to front comparison index, end the first cycle, at this point, for the reference value, the left and right sides are ordered.
Code examples:
public void sort(int[] a,int low,int high){
int start = low;
int end = high;
int key = a[low];
while(end>start){
// Compare from back to front
while(end>start&&a[end]>=key)
// If there is none less than the key value, compare the next one until there is a swap position less than the key value, and then compare back to back again
end--;
if(a[end]<=key){
int temp = a[end];
a[end] = a[start];
a[start] = temp;
}
// From the front to the back
while(end>start&&a[start]<=key)
// If none is greater than the key value, compare the next one until there is a swap position greater than the key value
start++;
if(a[start]>=key){
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
// At this point, the first loop comparison is completed, and the key value position has been determined. The values on the left are both smaller than the key value, and the values on the right are both larger than the key value, but the order may be different. Make the following recursive call
}
/ / recursion
if(start>low) sort(a,low,start-1);// The left sequence. The first index location goes to the key value index -1
if(end<high) sort(a,end+1,high);// Right side sequence. Index from key value +1 to last}}Copy the codeHill sorting algorithm
Introduction to the
Basic idea: firstly, divide the whole sequence of records to be sorted into several sub-sequences for direct insertion sort respectively. When the records in the whole sequence are “basically ordered”, then direct insertion sort is carried out for all records successively.
use
Application scenario: A large amount of data does not require stability.
Steps:
1, select a delta sequence T1, T2… , where Ti >tj, tk=1;
2. Sort the sequence k times according to the number of incremental sequences K;
3. In each sort, according to the corresponding increment TI, the sequence to be sorted is divided into several sub-sequences with length m, and each sub-table is directly inserted and sorted. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.
Code examples:
private void shellSort(int[] a) {
int dk = a.length/2;
while( dk >= 1 ){
ShellInsertSort(a, dk);
dk = dk/2; }}private void ShellInsertSort(int[] a, int dk) {
// Similar to insert sort, except insert sort increment is 1, in this case increment is dk, replace 1 with dk
for(inti=dk; i<a.length; i++){if(a[i]<a[i-dk]){
int j;
int x=a[i];//x is the element to be inserted
a[i]=a[i-dk];
for(j=i-dk; j>=0&& x<a[j]; j=j-dk){// Move through the loop one by one to find the position to insert.
a[j+dk]=a[j];
}
a[j+dk]=x;/ / insert}}}Copy the codeMerge sort algorithm
Introduction to the
Merge sorting is the merging of two (or more) ordered tables into a new ordered table, that is, the sequence to be sorted into several subsequences, each subsequence is ordered. Then the ordered subsequence is combined into a whole ordered sequence.
Scenario USES
Application scenario: This parameter is used when the memory is small and parallel computing is available.
Steps:
1. Select two adjacent numbers to form an ordered sequence.
2. Select two adjacent ordered sequences to form an ordered sequence.
3. Repeat step 2 until you have an ordered sequence.
Code examples:
public class MergeSortTest {
public static void main(String[] args) {
int[] data = new int[] { 5.3.6.2.1.9.4.8.7 };
print(data);
mergeSort(data);
System.out.println("Sorted array:");
print(data);
}
public static void mergeSort(int[] data) {
sort(data, 0, data.length - 1);
}
public static void sort(int[] data, int left, int right) {
if (left >= right)
return;
// Find the intermediate index
int center = (left + right) / 2;
// Recurse to the left array
sort(data, left, center);
// Recurse the array on the right
sort(data, center + 1, right);
/ / merge
merge(data, left, center, right);
print(data);
}
/** * merge two arrays, the first two arrays are ordered, after the merge is still ordered *@paramData * Array object *@paramLeft * The index of the first element of the left array@paramCenter * is the index of the last element in the left array, and Center +1 is the index of the first element in the right array@paramRight * Index of the last element of the right array */
public static void merge(int[] data, int left, int center, int right) {
// Temporary array
int[] tmpArr = new int[data.length];
// Index of the first element in the right array
int mid = center + 1;
// third Records the index of the temporary array
int third = left;
// Cache the index of the first element of the left array
int tmp = left;
while (left <= center && mid <= right) {
// Put the smallest of the two arrays into the temporary array
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else{ tmpArr[third++] = data[mid++]; }}// The rest is placed in a temporary array (actually only one of the two whiles executes)
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
// Copy the contents of the temporary array back into the original array
// (the contents of the original left-right range are copied back to the original array)
while(tmp <= right) { data[tmp] = tmpArr[tmp++]; }}public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t"); } System.out.println(); }}Copy the codeBucket sorting algorithm
Introduction to the
Basic idea: Divide array ARR into N sub-intervals (buckets) of the same size, sort each sub-interval separately, and merge at last. Counting sort is a special case of bucket sort, and you can think of counting sort as a case where there is only one element per bucket.
use
Application scenario: It is very practical when the amount of data is very large and the space is relatively abundant, which can greatly reduce the operation order of the algorithm.
Steps:
1. Find the maximum value Max and minimum value min in the array to be sorted
2. We use ArrayList as a bucket, and ArrayList is used to store the elements in the bucket. The number of buckets is (maxmin)/arr.length+1
3. Iterate over the arR of the number group and calculate the bucket placed by each element ARR [I]
4. Sort each bucket individually
Code examples:
public static void bucketSort(int[] arr){
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
/ / create a bucket
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
// Put each element into the bucket
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
// Sort each bucket
for(int i = 0; i < bucketArr.size(); i++){ Collections.sort(bucketArr.get(i)); }}Copy the codeRadix sort algorithm
Introduction to the
Basic idea: unify all the values to be compared (positive integer) into the same digit length, and fill zeros in front of the shorter digit. Then, sort the order one by one, starting with the lowest order. So from the lowest order to the highest order, the sequence becomes an ordered sequence.
use
Application scenario: Sort a large number of long numbers.
Steps:
1. Take out the units digit of all the numbers and sort them according to the units digit to form a sequence.
2. Take out the ten digits of all the newly formed numbers and sort them according to the ten digits to form a sequence.
Code examples:
public class radixSort {
inta[]={49.38.65.97.76.13.27.49.78.34.12.64.5.4.62.99.98.54.101.56.17.18.23.34.15.35.25.53.51};
public radixSort(a){
sort(a);
for(inti=0; i<a.length; i++){ System.out.println(a[i]); }}public void sort(int[] array){
// First determine the number of sorts;
int max=array[0];
for(inti=1; i<array.length; i++){if(array[i]>max){ max=array[i]; }}int time=0;
// Determine the number of digits;
while(max>0){
max/=10;
time++;
}
// Create 10 queues;
List<ArrayList> queue=newArrayList<ArrayList>();
for(int i=0; i<10; i++){ ArrayList<Integer>queue1=new ArrayList<Integer>();
queue.add(queue1);
}
// Perform time allocation and collection;
for(int i=0; i<time; i++){// Allocate an array element;
for(intj=0; j<array.length; j++){// Get the time of the number +1 digit;
int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);
ArrayList<Integer>queue2=queue.get(x);
queue2.add(array[j]);
queue.set(x, queue2);
}
int count=0;// Element counter;
// Collect queue elements;
for(int k=0; k<10; k++){while(queue.get(k).size()>0){
ArrayList<Integer>queue3=queue.get(k);
array[count]=queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}
}
Copy the codePruning algorithm
Introduction to the
Basic idea: In the optimization of search algorithm, pruning is to avoid some unnecessary traversal process through some judgment. Figuratively speaking, it is to cut some “branches” in the search tree, so it is called pruning. The core problem of pruning optimization is to design pruning judgment method, that is, to determine which branches should be discarded and which branches should be kept.
use
Application scenario: It is used in DFS and BFS search algorithms to search for filtering conditions and reduce unnecessary search paths in advance.
Steps:
1. Generate a decision tree based on the training data set, and the generated decision tree should be as large as possible;
2. Pruning is carried out with the most generated tree of the validation data set and the optimal subtree is selected. In this case, the minimum loss function is taken as the criterion of pruning
Code examples:
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
LinkedList<Integer> track = new LinkedList<>();
combinationSum(candidates, 0, target, track);
return result;
}
private List<List<Integer>> result = new ArrayList<>();
private void combinationSum(int[] candidates, int start, int target, LinkedList<Integer> track) {
if (target < 0) {
return;
} else if (target == 0) {
result.add(new LinkedList<>(track));
return;
}
for (int i = start; i < candidates.length; i++) {
if (target < candidates[i]) {
break; } track.add(candidates[i]); combinationSum(candidates, i, target - candidates[i], track); track.removeLast(); }}}Copy the codeBacktracking algorithm
Introduction to the
Basic idea: Backtracking algorithm is actually a search attempt process similar to enumeration, which is mainly to find the solution of the problem in the search attempt process. When it is found that the solution condition is not met, it will “backtrack” back and try another path.
use
Application scenario: Set up a recursive function, the parameters of the function will carry some information about the current possible solution, according to these parameters to get the possible solution or impossible and backtrack, usually see N queen, sudoku, set and so on.
Steps:
1. Define a solution space that contains the solution of the problem;
2. Organize the solution space with a method suitable for searching;
3. Use depth-first method to search solution space;
4. Use bounding functions to avoid moving to subspaces where solutions are impossible.
Code examples:
function backtrack(n, used) {
// Determine whether the input or status is illegal
if (input/state is invalid) {
return;
}
// Determine if the recursion should end, and return the result if the end condition is satisfied
if (match condition) {
return some value;
}
// Run through all possible current scenarios and try each one
for (all possible cases) {
// If the previous attempt affects the next attempt, write the status
used.push(case)
// Recursively make the next attempt to search the subtree
result = backtrack(n + 1, used)
// In this case the attempt is complete, reset the state for the following backtrace attempt
used.pop(case)}}Copy the codeShortest path algorithm
Introduction to the
Basic idea: Starting from a vertex and reaching another vertex along the edge of the graph, the path with the minimum sum of the weights of each edge is called the shortest path. To solve the shortest problem, there are the following algorithms, such as Dijkstra algorithm, Bellman-Ford algorithm, Floyd algorithm and SPFA algorithm.
use
Application scenarios: Computer network routing algorithm, robot pathfinding, traffic route navigation, artificial intelligence, game design, etc.
Steps :(example of Dijkstra algorithm)
1. Visit the nearest starting point in the road network that has not been checked, and place this point in the OPEN group for inspection.
Select the closest point from the OPEN table, find all the children of this point, and place this point in the CLOSE table.
3. Traverse the child nodes of this point. Find the distance between these children and the starting point and place the children in the OPEN table.
4. Repeat steps 2,3. Until the OPEN table is empty or the target point is found.
Code examples:
/ / Dijkstra algorithm
static int[] pathSrc = new int[9];
static int[] shortPath = new int[9];
static void shortestPath_DijkStra(MGraph m, int v0) {
// finalPath[w] = 1 indicates that the shortest path between vertices V0 and Vw has been obtained
int[] finalPath = new int[9];
for (int i = 0; i < m.numVertexes; i++) {
finalPath[i] = 0;
shortPath[i] = m.arc[v0][i];
pathSrc[i] = 0;
}
// The path from v0 to v0 is 0
shortPath[v0] = 0;
// vo to v0 does not require a path
finalPath[v0] = 1;
for (int i = 1; i < m.numVertexes; i++) {
// The closest known distance to V0
int min = INFINITY;
int k = 0;
for (int w = 0; w < m.numVertexes; w++) {
if(shortPath[w] < min && finalPath[w] == 0) {
min = shortPath [w];
k = w;
}
}
finalPath[k] = 1; // Change the value of finalPath to indicate that the shortest path has been found
for (int w = 0; w < m.numVertexes; w++) {
// If the path through V is shorter than the original path (not through V)
if(finalPath[w] == 0 && (min + m.arc[k][w]) < shortPath[w]) {
// A shorter path is found
shortPath[w] = min + m.arc[k][w]; // Change the path length
pathSrc[w] = k; // Modify the precursors of the vertex subscript W}}}}Copy the codeMaximum subarray algorithm
Introduction to the
Basic idea: Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum.
use
Application scenario: life can be used to view the growth of the stock within a week, need to get the most appropriate time to buy and sell.
Steps:
Discard substrings with negative sums and keep only positive sums.
2. If there are positive numbers in NUMS, iterate over numS from left to right, recording the sum of each step with the variable cur until positive numbers increase and negative numbers decrease.
3. When cur>=0, each summation may be the largest summation. Therefore, another variable Max can be used to track and record the maximum value of cur in the whole process.
Code examples:
class Solution {
public:
/* * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */
int maxSubArray(vector<int> nums) {
if(nums.size()<=0) {return 0;
}
int max=INT_MIN,cur=0;/ / c + + minimum value
for(int i=0; i<nums.size(); i++)
{
if(cur < 0)
cur = nums[i];// If the preceding sum is less than 0, discard the preceding one
else
cur+=nums[i];
if(cur > max)
max = cur;
}
returnmax; }};Copy the codeLongest common suborder algorithm
Introduction to the
Basic idea: The longest common subsequence is a problem used to find the oldest sequence of all sequences in a set of sequences. This differs from the problem of finding the longest common substring in that the subsequence does not need to occupy contiguous positions in the original sequence.
use
Application scenario: The longest common subsequence problem is a classic computer science problem that underlies data comparison programs, such as Diff tools, and bioinformatics applications. It is also widely used in version control, such as Git to mediate changes between files.
Steps:
1, can use recursion to solve, need to go through all possible, very slow;
2. General LCS problems are NP problems;
3. When the number of sequences is certain, dynamic programming can be used to solve the problem.
Code examples:
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int length1 = text1.length();
int length2 = text2.length();
int[][] a = new int[length1 + 1][length2 + 1];//0 rows and 0 columns are reserved
for(int i = 1; i <= length1; i++){
for(int j = 1; j <= length2; j++){
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
a[i][j] = a[i - 1][j - 1] + 1;
} else {
if (a[i][j - 1] > a[i-1][j]) {
a[i][j] = a[i][j - 1];
} else {
a[i][j] = a[i - 1][j]; }}}}returna[length1][length2]; }}Copy the codeMinimum spanning tree algorithm
Introduction to the
Basic idea: If n-1 edges are selected from a weighted undirected connected graph with n vertices to form a minimal connected subgraph, and the sum of weights of n-1 edges in the connected subgraph is minimized, it is called the minimum spanning tree of a connected network (not necessarily unique).
In general, two algorithms are used to solve the minimum spanning tree problem: Prim algorithm and Kruskal algorithm.
use
Application Scenario: Generally used to calculate cost minimization.
Steps :(example Prim algorithm)
1. Start at a point and find all edges accessible to the current point;
2. Find the smallest edge among the edges that have been found. This edge must have a point that has not been visited, add the point that has not been visited to our set, and record the added edge;
3. Find all edges accessible to the current set and repeat the process of 2 until no new points can be added;
4. At this point, the tree composed of all edges is the minimum spanning tree.
Code examples:
/** Prim algorithm *@paramFirst Constitutes the identity * of the starting point of the minimum spanning tree@returnReturns the smallest spanning tree edge */
public List<Edge> generateMinTreePrim(T first){
// Store the smallest spanning tree edge
List<Edge> result=new LinkedList<>();
// Create a map with key vertex and value edge
HashMap<Vertex<T>, Edge> map=new HashMap<>();
Iterator<Vertex<T>> vertexIterator=getVertexIterator();
Vertex<T> vertex;
Edge edge;
while(vertexIterator.hasNext()){
// At the beginning, both ends of value edge are themselves, weight=maxDouble
vertex=vertexIterator.next();
edge=new Edge(vertex, vertex, Double.MAX_VALUE);
map.put(vertex, edge);
}
// First is the identifier that forms the starting point of the minimum spanning tree
vertex=vertexMap.get(first);
if(vertex==null){
System.out.println("No node:"+first);
return result;
}
// All nodes that are not in the spanning tree are map keys. If the map is empty, all nodes are in the tree
while(! map.isEmpty()){// This loop will add vertex to the spanning tree and edge to the vertex.
edge=map.get(vertex);
// Every time A node j is added to tree A, it is first removed from the map
map.remove(vertex);
result.add(edge);
System.out.println(Spanning tree adds edges, vertices:+vertex.getLabel()+
", the end of the edge is:"+edge.getEndVertex().getLabel()+", the edge weight is:"+edge.getWeight());;
// If it is the first node and the corresponding edge is to itself, delete it
if(vertex.getLabel().equals(first)){
result.remove(edge);
}
// Then look at the distance between the remaining nodes in the map and node j. If this edge is less than the previous edge, replace the edge with this edge to node j
// The shortest edge minEdge is also found in the substitution traversal
Edge minEdge=new Edge(vertex, vertex, Double.MAX_VALUE);
for(Vertex<T> now:map.keySet()){
edge=map.get(now);
//newEdge is the edge between now and node j
Edge newEdge=now.hasNeighbourVertex(vertex);
if(newEdge! =null&&newEdge.getWeight()<edge.getWeight()){
// If this edge is less than the previous edge, replace the edge with this edge to the node j
edge=newEdge;
map.put(now, edge);
}
if(edge.getWeight()<minEdge.getWeight()){
/ / update the minEdgeminEdge=edge; }}// Set the direction of the edge from v not on the tree to u on the tree
// The starting point of this edge is not in the tree. It is the next node added to the spanning tree
vertex=minEdge.getBeginVertex();
}
return result;
}
Copy the codeThe last
Algorithms are essential for both learning and work. If we master the logic behind these algorithms, it will promote our study and work very well.
Secondly, the algorithm for the interview, especially into some large factories BAT and other companies are a stepping stone, large companies will evaluate your overall technical level through the algorithm, if you have a good algorithm foundation, I believe it will be of great help to your future career path.
In the later stage of career development, good algorithm skills can help us complete coding faster and more efficiently, and develop towards the direction of architect. If you have the corresponding algorithm knowledge for the same position, you can get a better salary than others.
Of course, the algorithm is far more than these listed, there are many complex algorithms to continue to learn, together with cheer ~