• figure
  • The tree
  • Dictionaries, hash tables
  • A collection of
  • The list
  • The queue
  • The stack

Bubble sort, select sort, insert sort, merge sort, quick sort, heap sort, order search, binary search algorithm

Sorting algorithm

  • An array is created to represent the data structure to be sorted and searched
function ArrayList(){ var array = []; This. insert = function(item){// Insert method adds element array.push(item) to data structure; }; This.tostring = function(){// To concatenate all elements of an array into a single string return array.join(); }; The join method concatenates array elements to a string and returns the stringCopy the code

Bubble sort

  • Bubble sort is the worst in terms of runtime.

Principle:

Bubble sort compares any two adjacent items and swaps them if the first is larger than the second. Items move up to the correct order, like bubbles rising to the surface, hence the name bubble sort.

Implement bubble sort:

this.bubbleSort = function(){ var length = array.length; For (var I =0; i<length; For (var j=0; var j=0; var j=0; var j=0; var j=0; j<length-1; If (array[j] > array[j+1]){swap(array, j, j+1); swap(array, j, j+1); swap(array, j, j+1); //{5}}}}}; Var swap = function(array, index1, index2){var aux = array[index1]; array[index1] = array[index2]; array[index2] = aux; }; // We use an intermediate value to store the value of a certain swapCopy the code

ES6 writing:

[array[index1], array[index2]] = [array[index2], array[index1]];
Copy the code

Subtract the number of rounds that have been run in the outer loop from the inner loop

Advanced bubble sort:

this.modifiedBubbleSort = function(){ var length = array.length; for (var i=0; i<length; i++){ for (var j=0; j<length-1-i; J++) {/ / avoid all unnecessary in the inner loop is the if (array [j] > array [j + 1]) {swap (j, j + 1); }}}};Copy the code

Selection sort (an address-comparison sort algorithm)

How it works: Find the smallest value in the data structure and place it first, then find the second-smallest value and place it second, and so on

Example:

this.selectionSort = function(){ var length = array.length, indexMin; for (var i=0; i<length-1; i++){ indexMin = i; for (var j=i; j<length; j++){ if(array[indexMin]>array[j]){ indexMin = j; } } if (i ! == indexMin){ swap(i, indexMin); }}};Copy the code

Insertion sort

Insert sort builds the final sorted array, one item at a time

Example:

this.insertionSort = function(){ var length = array.length, j, temp; for (var i=1; i<length; i++){ j = i; temp = array[i]; while (j>0 && array[j-1] > temp){ array[j] = array[j-1]; j--; } array[j] = temp; }};Copy the code

Merge sort

Merge sort is the first practical sorting algorithm

Principle:

Divide the original array into smaller arrays until each of the smaller arrays has only one position, and then merge the smaller arrays into larger arrays until there is only one sorted large array.

  • Merge sort is a divide-and-conquer algorithm
  • Merge sort is also recursive
this.mergeSort = function(){ 
 array = mergeSortRec(array); 
};
Copy the code

Recursive function

Var mergeSortRec = function(array){var length = array.length; If (length === 1) {return array; } var mid = math.floor (length / 2), // If the array length is larger than 1, Right = array.slice(mid, length); right = array.slice(mid, length); Merge (mergeSortRec(left), mergeSortRec(right)); merge(mergeSortRec(right)); // Divide the array into two small arrays};Copy the code

Example:

Var merge = function(left, right){var result = [], // Merge a new array il = 0, ir = 0; While (il < left.length && ir < right.length) {// Iterate over two arrays // Compare whether the items from left array are smaller than the items from right array if(left[il] < right[ir]) { result.push(left[il++]); } else{result.push(right[ir++]);} else{result.push(right[ir++]); }} while (il < left.length){// {11} result.push(left[il++]); } while (ir < right.length){ // {12} result.push(right[ir++]); } return result; / / {13}};Copy the code

Quick sort

  • Selects the middle item from the array as the primary
  • Create two Pointers, one on the left pointing to the first item and one on the right pointing to the last item of the array
  • Move the left pointer until we find an element larger than the pivot
  • Move the right pointer until you find an element smaller than the pivot

Example:

this.quickSort = function(){ 
 quick(array, 0, array.length - 1); 
};
Copy the code

Example:

var quick = function(array, left, right){ var index; If (array.length > 1) {// Because only one element of the array must be sorted index = partition(array, left, right); / /. Quick (array, left, index-1); quick(array, left, index-1); quick(array, left, index-1); Quick (array, index, right); quick(array, index, right); quick(array, index, right); // Repeat the process for the array}}};Copy the code
  • Divide the process

1. Select the primary element

Division process:

Var partition = function(array, left, right) {var pivot = array[math.floor ((right + left) / 2)], // initialize two Pointers to the first element of the array j = right; While (array[I] < pivot) {// Move the left pointer until an element larger than the pivot element is found i++; } while (array[j] > pivot) {// Move the right pointer until we find an element j smaller than the pivot --; } if (I <= j) {// If (I <= j) {// If (I <= j) {// If (I <= j) {// If (I <= j) {// If (I <= j) {// If (I <= j); // swap them, then move two Pointers i++; j--; } } return i; };Copy the code

Display:

  • The diagram below shows partitioning operations performed on subarrays with smaller values

  • Continue creating subarrays, as shown in the figure below

  • Let’s go ahead and divide

  • Let’s go ahead and divide

Heap sort

  • It’s a very efficient algorithm
  • So named for sorting arrays like binary trees

1. Index 0 is the root node of the tree.

2. Except the root node, the parent of any node N is N/2.

3. The left child node of node L is 2*L;

4. The right child of R is 2*R+1

The array [3, 5, 1, 6, 4, 7, 2] is imagined as the tree below

Example:

this.heapSort = function() { var heapSize = array.length; buildHeap(array); While (heapSize > 1) {heapSize--; swap(array, 0, heapSize); // Swap the position of the first and last element in the heap heapify(array, heapSize, 0); // Find the root node of the current heap (smaller value) and place it at the bottom of the tree}};Copy the code

The buildHeap function is implemented as follows

var buildHeap = function(array){ var heapSize = array.length; for (var i = Math.floor(array.length / 2); i >= 0; i--) { heapify(array, heapSize, i); }};Copy the code

The heap is built as follows :(call buildHeap function)

Array [3, 5, 1, 6, 4, 7, 2]

var heapify = function(array, heapSize, i){ 

 var left = i * 2 + 1, 
 right = i * 2 + 2, 
 largest = i; 
 
 if (left < heapSize && array[left] > array[largest]) { 
     largest = left; 
 } 
 
 if (right < heapSize && array[right] > array[largest]) { 
     largest = right; 
 } 
 
 if (largest !== i) { 
     swap(array, i, largest); 
     heapify(array, heapSize, largest); 
 } 
 
};
Copy the code

Sort (distributed sort)

1. Count sort

2. Bucket sort

3. Radix sort

The best known distributed algorithms are counting sort, bucket sort and radix sort

Search algorithm – sequential search

  • Sequential or linear search is the most basic search algorithm
  • Compare each element in the data structure to the element we’re looking for

Example:

this.sequentialSearch = function(item){ for (var i=0; i<array.length; If (item === array[I]) // Compare each array element with the search item return I; // Search success // return value can be the search item itself, true, or the search item index}} return -1; // If the item is not found, return -1 to indicate that the index does not exist};Copy the code

Search algorithm – binary search

Game example: a number game from 1 to 100. Every time we respond to a number, the person will say whether the number is high, low, or right.

Example:

this.binarySearch = function(item){ this.quickSort(); Var low = 0, high = array.length - 1, mid, element; While (low <= high){mid = math.floor ((low + high) / 2); element = array[mid]; If (element < item) {low = mid + 1; } else if (element > item) { high = mid - 1; } else { return mid; } } return -1; // If low is higher than high, it means that the value to be searched does not exist and returns -1};Copy the code

Steps performed:

Bubble, select, insert, merge, fast and heapsort algorithms, sequential search and binary search

Algorithm model

  • recursive
  • Dynamic programming
  • Greedy algorithm

Example:

function recursiveFunction(someParam){ 
 recursiveFunction(someParam); 
};
Copy the code
function recursiveFunction1(someParam){ 
 recursiveFunction2(someParam); 
}; 
function recursiveFunction2(someParam){ 
 recursiveFunction1(someParam); 
};
Copy the code
  • It keeps executing (stack overflow error). (Requires a condition that no longer calls recursively)

Limits on the size of the JavaScript call stack

Example:

var i = 0; function recursiveFn () { i++; recursiveFn(); } try { recursiveFn(); } catch (ex) { alert('i = ' + i + ' error: ' + ex); // Internal error: too many recursions}Copy the code
  • Es6 tail-call optimization

Fibonacci numbers

  • The Fibonacci numbers of 1 and 2 are 1
  • The Fibonacci number of n (n >2) is Fibonacci number of (n1) plus Fibonacci number of (n2)

Example:

/ / boundary condition is known, and 1 and 2 of the Fibonacci number is 1 function Fibonacci (num) {if (num = = = 1 | | num = = = 2) {/ / {1} return 1; }}Copy the code
function fibonacci(num){ if (num === 1 || num === 2){ return 1; } return fibonacci(num - 1) + fibonacci(num - 2); } // Fibonacci(n) = Fibonacci(n-1)+Fibonacci(n-2)Copy the code

Non-recursive Fibonacci functions:

function fib(num){ 
 var n1 = 1, 
 n2 = 1, 
 n = 1; 
 
 for (var i = 3; i<=num; i++){ 
     n = n1 + n2; 
     n1 = n2; 
     n2 = n; 
 } 
 
 return n; 
}
Copy the code

Dynamic programming

Some famous questions are as follows:

  • Knapsack problem
  • Longest common subsequence
  • Matrix chain multiplication
  • Coin change
  • The full source shortest path of the graph

Introduction to functional programming

Functional programming takes advantage of ES6’s capabilities, and JavaScript is also capable of functional programming

With imperative programming, we declare the following functions:

var printArray = function(array) { for (var i = 0; i < array.length; i++) { console.log(array[i]); }}; printArray([1, 2, 3, 4, 5]);Copy the code

Functional programming :(focus on what needs to be described, not how)

var forEach = function(array, action) { for (var i = 0; i < array.length; i++) { action(array[i]); }}; var logItem = function (item) { console.log(item); }; forEach([1, 2, 3, 4, 5], logItem);Copy the code

1. The goal is to describe the data and the transformations to be applied to the data

2. The order in which a program is executed is of low importance, whereas in imperative programming steps and sequences are very important

3. Functions and data sets are at the heart of functional programming

4. In functional programming, we can use and abuse functions and recursion, while in imperative programming, we use loops, assignments, conditions, and functions

map

To convert or map one data set to another

filter

Use the filter function to filter the values of a collection

reduce

To reduce a set to a specific value

Algorithm complexity

  • The famous big O notation
  • And NP complete theory

Big O notation

  • When we talk about big O notation, we generally think about CPU usage

O(1)

Function increment(num){return increment(num); }Copy the code

O(n)

Function sequentialSearch(array, item){for (var I =0; i<array.length; i++){ if (item === array[i]){ //{1} return i; } } return -1; }Copy the code

Time complexity comparison

Time complexity of common data structures:

Time complexity of the graph:

Time complexity of sorting algorithm:

Time complexity of search algorithm:

NP complete theory

  • NP (Nondeterministic polynomial)algorithm
  • For a given problem, if there is a polynomial algorithm, thenP (polynomial)
  • If a problem can verify the correct solution in polynomial time, thenNP
  • NPThe hardest part of the problem isNPProblem completely

1. It is NP problem, that is, the solution can be verified in polynomial time, but the polynomial algorithm has not been found

2. All NP problems can be reduced to it in polynomial time

P, NP, NP complete and NP hard problem diagrams:

Recommendation: An introduction to THE THEORY of NP completeness

❤️ follow + like + favorites + comments + forward ❤️, original is not easy, encourage the author to create better articles

Likes, favorites and comments

I’m Jeskson, thanks for your talent: likes, favorites and comments, and we’ll see you next time! ☞ Thank you for learning with me.

See you next time!

This article is constantly updated. You can search “Programmer Doraemon” on wechat to read it for the first time, and reply [information] there are materials of first-line big factories prepared by me, which have been included in this article www.dadaqianduan.cn/#/

Star: github.com/webVueBlog/…