Why Learn Data Structures and Algorithms

Data Structures and Algorithms For many front-end engineers, they have always felt dispensable, but in fact, personally, the front-end engineers are actually The person who needs the most attention to the data structure and algorithm, because what the front end does is what the user sees at the first sight of the website, especially after the arrival of the mobile wave, the user experience is getting higher and higher, and the front end is higher. Requirements, in the face of increasingly complex products, requires a solid data structure and algorithm basis to control. If you haven't studied computer science programmers, when we are dealing with some problems, the familiar data structure is an array, and arrays are undoubtedly a good choice. But many times, for many complex problems, arrays are too simplistic. After learning the data structure and algorithm, for many programming problems, when thinking about a suitable data structure, design and implement the algorithm to solve these problems. Hand to come.

related knowledge points - data structure, sorting algorithm and search algorithm

related explanation subdivision: Data structures: lists, stacks, queues, linked lists, dictionaries, hashes, graphs, and binary search trees Sorting algorithm: fake sort, select sort, insert sort, hill sort, merge sort, and quick sort Search algorithm: sequential search and binary search

列表

In daily life, people often use the list: to-do list, shopping list, best ten list and so on. The computer program is also using the list. Under the following conditions, the selection list is particularly useful as a data structure:

  • The data structure is relatively simple
  • does not need to find elements in a long sequence, or Sorting

, if the data structure is very complex, the list is not as big.

Stack is a special list, the elements in the stack can only be accessed through one end of the list, this end is called the top of the stack. Imagine that the plate we usually see in the restaurant is an example of a stack that is common in the real world. It can only be taken from the top, and after the dish is washed, it can only be placed on the top. The stack is called a last-in, first-out data structure. It is an efficient data structure, because data can only be added or deleted at the top of the stack, so this operation is very fast. Conditions of use:

  • As long as the data is saved to meet , the principle of first-in first-out or advanced-out, the priority is to use the stack

images

Queue

queue is also a list, The difference is that the queue can only insert elements at the end of the queue and delete elements at the beginning of the queue. Imagine that we are lined up at the bank, the first person to do business first, and the people coming back can only be behind the team until the turn of them. Conditions of use:

  • As long as the data is saved to meet 先先先出,后后后出出, the principle is preferred to use the queue

Common application scenario:

  • Queue mainly used In time-related places, especially in operating systems, queues are an important mechanism for implementing multitasking.
  • Message mechanism can be implemented through queues, and process scheduling is also implemented using queues

images

链表

链表It's also a list of why it's necessary to have a linked list, the main problem with arrays in JavaScript, when they are implemented as objects, as opposed to arrays in other languages ​​(like C++ and Java), which is inefficient. If you find that the array is slow in actual use, consider using a linked list instead. Conditions of use:

  • 链表 can be used in almost any case where 一维Array can be used. Arrays are still a better choice if random access is required.

images

字典

字典 is a data structure for storing data by running 键-value, the Object class in JavaScript is designed in the form of a dictionary. JavaScript can implement the dictionary class to make this dictionary type object easier to use. The dictionary can realize the common functions owned by the object, and expand the functions that you want. The objects can be seen everywhere in JavaScript writing, so the role of the dictionary It is also very obvious.

散列

Hash (also known as hash table) is a commonly used array storage technology, and the hashed array can be quickly inserted or accessed. The data structure used by the hash is called a hash table. Insert, delete, and fetch data on the hash table are very fast, but inefficient for lookup operations, such as finding the maximum and minimum values ​​in a set of arrays. These operations need to be applied to other data structures, such as the binary search tree described below.

散列表 can be designed in the base array in JavaScript. The length of the array is pre-set, and all elements are stored in a specific position of the array according to the key corresponding to the element, where the key and the key of the object are the concept of the type. When you use a hash table to store an array, the key is mapped to a number by a hash function that ranges from 0 to the length of the hash table.

Even with an efficient hash function, there is still the possibility of mapping two keys to the same value. This phenomenon is called collision. The common collision treatment methods are: 开链法 and linear detection method(The specific concept is interested in online confidence)

使用条件:

  • Can be used for data insertion, deletion and retrieval, not for finding data

images

A graph consists of a collection of edges and a collection of vertices. Maps are a very common reality scene around us. For example, every two towns are connected by some kind of road. Each town above can be seen as a apex, and the road connecting the towns is the side. The edges are defined by vertex pairs (v1, v2), and v1 and v2 are the two vertices in the graph, respectively. Vertices also have weight and become a cost. If the vertex pairs of a graph are ordered, they are called directed graphs (such as common flowcharts), and vice versa, called unordered graphs. Use the scene (using the map to model the real system):

  • 交通系统, you can use the vertices to represent the intersection of the street, and the side can represent the street. The weighted edges can represent the speed limit or the number of lanes. This system can be used to determine the best route and the street most likely to be stuck.
  • Any transportation system can be modeled using diagrams. For example, airlines can use graphs to model their flight systems. Think of each airport as a vertex and treat each route through the two vertices as an edge. Weighted edges can represent the cost of a flight from one airport to another, or the distance between two airports, depending on what the model is. There are two main algorithms for

search: depth-first search and breadth-first search.

二叉树和二叉找树

树 is a data structure often used in computer science. A tree is a non-linear data structure that stores data in a hierarchical manner. The binary tree does not allow more than two children per node. The two child nodes of a parent node are called the left node and the right node respectively. By limiting the number of child nodes to 2, it is possible to write an efficient program to insert, find, and delete data . The binary search tree (BST) is a special binary tree. Relatively small values ​​are stored in the left node, and larger values ​​are stored in the right node. This feature makes 。 二叉查找树(BST)是一种特殊的二叉树,相对较小的值保存在左节点中,较大的值保存在右节点中。这一特性使得 lookups very efficient, for both numeric and non-numeric data, such as words and strings. Binary search tree implementation method

in the tree
function Node(data, left, right) { // 创建节点
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show
}

function show () { // 显示树的数据
  return this.data
}

function BST () { // 二叉查找树类
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder; // inOrder是遍历BST的方式
}

function insert (data) { // 向树中插入数据
  var n = new Node(data, null, null)
  if (this.root == null) {
    this.root = n;
  } else {
    var current = this.root;
    var parent;
    while (true) {
	  parent = current
	  if (data < current.data) {
		current = current.left;
		if (current == null) {
		  parent.left = n;
		  break;
		}
	  } else {
		current = current.right;
		if (current == null) {
		  parent.right = n;
		  break;
		}
	  }
    }
  }
}

images 遍历BST的方式有三种:中序遍历(以升序访问树中所有节点,先访问左节点,再访问根节点,最后访问右节点)、先序遍历(先访问根节点,再以同样的方式访问左节点和右节点)、后序遍历(先访问叶子节点,从左子树到右子树,再到根节点)

sort algorithm

basic sorting algorithm

basic sorting algorithm, the core idea is to rearrange a group of arrays in a certain order. The technique used when rearranging is a set of nested for loops. The outer loop traverses each item of the array, and the inner loop is used to compare the elements.

bubble sorting

bubble sorting is a simple sorting algorithm. It repeatedly visits the sequence to be sorted, compares two elements at a time, and swaps them if they are in the wrong order. The work of visiting the series is repeated until no more exchanges are needed, which means that the sequence has been sorted. The name of this algorithm comes from the fact that the smaller the element will slowly "float" to the top of the series via the exchange.

function bubbleSort (arr) {
	var i = arr.length;
	while (i > 0) {
		var pos = 0
		for (var j = 0; j < i; j++) {
			if (arr[j] > arr[j+1]){
				pos = j
				var temp = arr[j]
				arr[j] = arr[j+1]
				arr[j+1] = temp
			}
		}
		i = pos
	}
	return arr
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

images

选择选

Selection-sort is a simple and intuitive sorting algorithm. It works by first finding the smallest (large) element in the unsorted sequence, storing it at the beginning of the sorting sequence, then continuing to find the smallest (large) element from the remaining unsorted elements, and then placing it in the sorted sequence. At the end. And so on, until all the elements are sorted.

function selectionSort (arr) {
	var len = arr.length;
	var minIndex, temp;
	for (var i = 0; i < len-1; i++) {
		minIndex = i;
		for (var j = i+1; j < len; j++) {
			if (arr[j] < arr[minIndex]) {
				minIndex = j
			}
		}
		temp = arr[minIndex]
		arr[minIndex] = arr[i]
		arr[i] = temp
	}
	return arr
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

images

Insert Sort

Insert Sort (Insertion-Sort) algorithm description is a simple and intuitive sorting algorithm. It works by constructing an ordered sequence, for unsorted data, scanning backwards and forwards in the sorted sequence, finding the corresponding position and inserting it. Insert sorting is implemented in in-place sorting (that is, only the extra space of O(1) is used), so in the process of scanning backwards and forwards, it is necessary to repeatedly shift the sorted elements backwards. Provides insertion space for the latest elements.

function insertSort (arr) {
	var len = arr.length
	for (i = 1; i < len; i++) {
		var key = arr[i]
		var j = i - 1
		while (j >= 0 && arr[j] > key) {
			arr[j+1] = arr[j]
			j--;
		}
		arr[j+1] = key
	}
	return arr
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(insertSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

images

Advanced Sorting Algorithm

Advanced Data Sorting Algorithm, the most efficient sorting algorithm commonly used to process large data sets, they can process millions of elements, not just a few hundred or Thousands, we will introduce Hill sorting, merge sorting, and quick sorting.

希尔序

1959 Shell invented, the first breakthrough O(n^2) sorting algorithm; is an improved version of simple insert sorting; it differs from insert sorting in that it will Priority is given to comparing elements that are farther away. Hill sorting is also called narrowing incremental sorting. The core of the Hill sorting is the setting of the interval sequence. The interval sequence can be set in advance or the interval sequence can be dynamically defined.

function shellSort (arr) {
	var len = arr.length;
	var temp, gap = 1;
	while (gap < len /3 ) {
		gap = gap * 3 + 1
	}
	while (gap >= 1) {
		for (var i = gap; i < len; i++) {
			temp = arr[i]
			for (var j = i - gap; j >= 0 && arr[j] > temp; j-=gap) {
				arr[j+gap] = arr[j]
			}
			arr[j+gap] = temp
		}
		gap = (gap - 1) / 3
	}
	return arr
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

5555

merge sorting

merge sorting is an efficient sorting algorithm based on merge operations. This algorithm is a very typical application using Divide and Conquer. Merging and sorting is a stable sorting method. The existing subsequences are combined to obtain a completely ordered sequence; that is, each subsequence is first ordered, and then the subsequences are ordered. If you combine two ordered tables into one ordered list, it is called 2-way merge.

function mergeSort (arr) {
	var len = arr.length
	if (len < 2) {
		return arr
	}
	var middle = Math.floor(len / 2)
	var left = arr.slice(0, middle)
	var right = arr.slice(middle)
	return merge (mergeSort(left), mergeSort(right));
}
function merge (left, right) {
	var result = []
	while (left.length && right.length) {
		if (left[0] < right[0]) {
			result.push(left.shift())
		} else {
			result.push(right.shift())
		}
	}
	while (left.length) {
		result.push(left.shift())
	}
	while (right.length) {
		result.push(right.shift())
	}
	return result
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));

images

快序

快序 is one of the fastest sorting algorithms for large data sets. It is a divide-and-conquer algorithm that recursively decomposes data into different subsequences containing smaller elements and larger elements. The algorithm repeats this step to know that all data is ordered. This algorithm first selects an element in the list as the reference value. Data sorting is done around the baseline value, moving elements in the list that are smaller than the baseline value to the bottom of the array, and moving elements larger than the baseline value to the top of the array.

function qSort (arr) {
	if (arr.length == 0) {
		return []
	}
	var left = []
	var right = []
	var pivot = arr[0]
	for (var i = 1; i < arr.length; i++) {
		if (arr[i] < pivot) {
			left.push(arr[i])
		} else {
			right.push(arr[i])
		}
	}
	return qSort(left).concat(pivot, qSort(right))
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(qSort(arr));

images

Search Algorithm

There are two ways to find data in a list: sequential lookup and binary lookup. A sequential lookup applies to a list of randomly arranged elements; a binary search applies to a list of ordered elements. Binary search is more efficient, but extra time must be spent sorting the elements in the list before looking up.

序找

The easiest way to find data is to judge the list elements one by one from the first element of the list until the desired result is found, or until the end of the list is not found. This method is called sequential lookup and is sometimes called linear lookup.

function seqSearch (arr, data) {
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] == data) {
      return i;
    }
  }
  return -1;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(seqSearch(arr, 15))

二分找

二分法找, also known as binary search, is a search algorithm for finding specific elements in an ordered array. The search process can be divided into the following steps:

  • First, the search starts from the middle element of the ordered array. If the element happens to be the target element (ie the element to be looked up), the search process ends, otherwise the next step is taken.
  • If the target element is larger or smaller than the middle element, look for the half of the array where the array is larger or smaller than the middle element, and then repeat the first step.
  • If a step array is empty, the target element is not found.
function binSearch (arr, data) {
	var low = 0;
	var high = arr.length - 1
	while (low <= high) {
		var middle = Math.floor((low + high) / 2)
		if (arr[middle] < data) {
			low = middle + 1
		} else if (arr[middle] > data) {
			high = middle - 1
		} else {
			return middle
		}
	}
	return -1
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(binSearch(arr, 15))

Continuous update. . . . . .