Written interviews often involve various algorithms. This article briefly introduces some commonly used algorithms and implements them in JavaScript.
1. Insert sorting
1) Introduction to the algorithm
The algorithm description of Insertion-Sort is a simple and intuitive sorting algorithm. It works by building an ordered sequence, for unsorted data, scan backwards and forwards in the sorted sequence, find the corresponding position and insert it. In the implementation of insertion sorting, in-place sorting is usually used (that is, the extra space of O(1) is required), so during the scanning process from back to front, the sorted elements need to be repeatedly moved backwards to provide insertion space for the latest elements.
2) Algorithm description and implementation
Generally speaking, insertion sorting is implemented on an array using in-place. The specific algorithm is described as follows:
Starting from the first element, the element can be considered to have been sorted;
Take out the next element and scan backwards and forwards in the already sorted sequence of elements;
If the element (sorted) is greater than the new element, move the element to the next position;
Repeat step 3 until the sorted element is found where the new element is less than or equal;
After inserting a new element into that position;
Repeat steps 2 to 5.
JavaScript code implementation:
function insertionSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { for (var i = 1; i < array.length; i++) { var key = array[i]; var j = i - 1; while (j >= 0 && array[j] > key) { array[j + 1] = array[j]; j--; } array[j + 1] = key; } return array; } else { return 'array is not an Array!'; }}3) Algorithm analysis
Best case: Input arrays are sorted in ascending order. T(n) = O(n)
Worst case: The input array is sorted in descending order. T(n) = O(n2)
Average: T(n) = O(n2)
Two, binary insertion sort
1) Introduction to the algorithm
Binary-insert-sort sorting is a sorting algorithm that makes minor changes to the direct insertion sorting algorithm. The biggest difference between it and the direct insertion sorting algorithm is that when looking for insertion positions, the binary search method is used, which has a certain improvement in speed.
2) Algorithm description and implementation
Generally speaking, insertion sorting is implemented on an array using in-place. The specific algorithm is described as follows:
Starting from the first element, the element can be considered to have been sorted;
Take out the next element and find the position of the first number larger than it in the already sorted sequence of elements;
After inserting a new element into that position;
Repeat the above two steps.
JavaScript code implementation:
function binaryInsertionSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { for (var i = 1; i < array.length; i++) { var key = array[i], left = 0, right = i - 1; while (left <= right) { var middle = parseInt((left + right) / 2); if (key < array[middle]) { right = middle - 1; } else { left = middle + 1; } } for (var j = i - 1; j >= left; j--) { array[j + 1] = array[j]; } array[left] = key; } return array; } else { return 'array is not an Array!'; }}3) Algorithm analysis
Best case: T(n) = O(nlogn)
Worst case: T(n) = O(n2)
Average: T(n) = O(n2)
3. Select sorting
1) Introduction to the algorithm
Selection-sort is a simple and intuitive sorting algorithm. How it works: first find the smallest (large) element in the unsorted sequence, store it at the starting position of the sorted sequence, then continue to look for the smallest (large) element from the remaining unsorted elements, and then place it at the end of the sorted sequence. And so on until all elements are sorted.
2) Algorithm description and implementation
Direct selection of n records can be obtained through n-1 passes to directly select and sort. The specific algorithm is described as follows:
Initial state: The unordered area is R[1..n], and the ordered area is empty;
When the i-th ordering (i=1,2,3...n-1) begins, the current ordered and unordered areas are R[1..i-1] and R(i..n) respectively. This order selects the record R[k] with the smallest keyword from the current unordered area, and exchanges it with the first record R of the unordered area, so that R[1..i] and R[i+1..n) become a new ordered area with one increase in the number of records and a new unordered area with one decrease in the number of records;
The n-1 trip ends and the array is ordered.
JavaScript code implementation:
function selectionSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { var len = array.length, temp; for (var i = 0; i < len - 1; i++) { var min = array[i]; for (var j = i + 1; j < len; j++) { if (array[j] < min) { temp = min; min = array[j]; array[j] = temp; } } array[i] = min; } return array; } else { return 'array is not an Array!'; }}3) Algorithm analysis
Best case: T(n) = O(n2)
Worst case: T(n) = O(n2)
Average: T(n) = O(n2)
4. Bubble sorting
1) Introduction to the algorithm
Bubble sorting is a simple sorting algorithm. It repeatedly visits the sequences to be sorted, compares two elements at a time, and swaps them if they are incorrect. The work of visiting the sequence is repeated until no exchange is needed, that is, the sequence has been sorted. The origin of this algorithm is because the smaller the element will slowly "float" to the top of the sequence via exchange.
2) Algorithm description and implementation
The specific algorithm is described as follows:
Compare adjacent elements. If the first one is larger than the second one, exchange two of them;
Do the same work for each pair of adjacent elements, from the beginning of the first pair to the end of the last pair, so that the last element should be the largest number;
Repeat the above steps for all elements except the last one;
Repeat steps 1 to 3 until the sorting is complete.
JavaScript code implementation:
function bubbleSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { var len = array.length, temp; for (var i = 0; i < len - 1; i++) { for (var j = len - 1; j >= i; j--) { if (array[j] < array[j - 1]) { temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } return array; } else { return 'array is not an Array!'; } }3) Algorithm analysis
Best case: T(n) = O(n)
Worst case: T(n) = O(n2)
Average: T(n) = O(n2)
5. Quick sort
1) Introduction to the algorithm
The basic idea of quick sorting: divide the records to be sorted into two independent parts through one order, and the keywords of some records are smaller than those of the other part. Then the two records can be continued to sort them separately to achieve the order of the entire sequence.
2) Algorithm description and implementation
Quick sorting uses the dividing method to divide a string into two sub-lists. The specific algorithm is described as follows:
Picking an element from the sequence is called "principle" (pivot);
Reorder the sequence, all elements with smaller than the reference value are placed in front of the reference, and all elements with larger than the reference value are placed behind the reference (the same number can be placed on either side). After this partition exits, the reference is in the middle of the sequence. This is called a partition operation;
Recursively sort the sub-sequences smaller than the reference element and the sub-sequences larger than the reference element.
JavaScript code implementation:
//Method one function quickSort(array, left, right) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') { if (left < right) { var x = array[right], i = left - 1, temp; for (var j = left; j <= right; j++) { if (array[j] <= x) { i++; temp = array[i]; array[i] = array[j]; array[j] = temp; } } quickSort(array, left, i - 1); quickSort(array, i + 1, right); }; } else { return 'array is not an Array or left or right is not a number!'; } } var aaa = [3, 5, 2, 9, 1]; quickSort(aaa, 0, aaa.length - 1); console.log(aaa); //Method 2 var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right)); };3) Algorithm analysis
Best case: T(n) = O(nlogn)
Worst case: T(n) = O(n2)
Average: T(n) = O(nlogn)
6. Heap sorting
1) Introduction to the algorithm
Heap sorting refers to a sorting algorithm designed using the heap data structure. Stacking is a structure that is approximately completely binary tree and satisfies the properties of stacking: that is, the key value or index of a child node is always smaller than (or greater than) its parent node.
2) Algorithm description and implementation
The specific algorithm is described as follows:
The initial sequence of keywords to be sorted (R1, R2...Rn) is constructed into a large top heap, which is the initial unordered area;
Exchange the heap top element R[1] with the last element R[n], and at this time, a new unordered region (R1, R2,...Rn-1) and a new ordered region (Rn) are obtained, and R[1,2...n-1]<=R[n] is satisfied;
Since the new heap top R[1] after exchange may violate the properties of the heap, it is necessary to adjust the current unordered area (R1, R2,...Rn-1) to the new heap, and then exchange R[1] with the last element of the unordered area again to obtain a new unordered area (R1, R2...Rn-2) and a new ordered area (Rn-1,Rn). Repeat this process until the number of elements in the ordered area is n-1, and the entire sorting process is completed.
JavaScript code implementation:
/*Method description: heap sort @param array Array to be sorted*/ function heapSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { //Build heap var heapSize = array.length, temp; for (var i = Math.floor(heapSize / 2); i >= 0; i--) { heapify(array, i, heapSize); } //Heap sort for (var j = heapSize - 1; j >= 1; j--) { temp = array[0]; array[0] = array[j]; array[j] = temp; heapify(array, 0, --heapSize); } } else { return 'array is not an Array!'; }}/* Method description: Maintain the properties of the heap @param arr Array @param x Array Subscript @param len Heap size*/function heapify(arr, x, len) { if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') { var l = 2 * x, r = 2 * x + 1, largeest = x, temp; if (l < len && arr[l] > arr[largest]) { largest = l; } if (r < len && arr[r] > arr[largest]) { largest = r; } if (largest != x) { temp = arr[x]; arr[x] = arr[largest]; arr[largest] = temp; heapify(arr, large, len); } } else { return 'arr is not an Array or x is not a number!'; }}3) Algorithm analysis
Best case: T(n) = O(nlogn)
Worst case: T(n) = O(nlogn)
Average: T(n) = O(nlogn)
7. Ordering
1) Introduction to the algorithm
Merge sorting is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. Merge sorting is a stable sorting method. Merge the ordered subsequences to obtain a completely ordered sequence; that is, make each subsequence first order, and then make the subsequence segments order. If two ordered tables are merged into one ordered table, it is called 2-way merge.
2) Algorithm description and implementation
The specific algorithm is described as follows:
Divide the input sequence of length n into two subsequences of length n/2;
These two subsequences are sorted together separately;
Merge the two sorted subsequences into a final sorted sequence.
JavaScript code implementation:
function mergeSort(array, p, r) { if (p < r) { var q = Math.floor((p + r) / 2); mergeSort(array, p, q); mergeSort(array, q + 1, r); merge(array, p, q, r); } } function merge(array, p, q, r) { var n1 = q - p + 1, n2 = r - q, left = [], right = [], m = n = 0; for (var i = 0; i < n1; i++) { left[i] = array[p + i]; } for (var j = 0; j < n2; j++) { right[j] = array[q + 1 + j]; } left[n1] = right[n2] = Number.MAX_VALUE; for (var k = p; k <= r; k++) { if (left[m] <= right[n]) { array[k] = left[m]; m++; } else { array[k] = right[n]; n++; } }}3) Algorithm analysis
Best case: T(n) = O(n)
Worst case: T(n) = O(nlogn)
Average: T(n) = O(nlogn)
8. Bucket sorting
1) Introduction to the algorithm
The principle of bucket sorting: Assuming that the input data is uniformly distributed, the data is divided into a limited number of buckets, and each bucket is sorted separately (it is possible to use other sorting algorithms or continue to use bucket sorting in a recursive manner).
2) Algorithm description and implementation
The specific algorithm is described as follows:
Set a quantitative array as an empty bucket;
Iterate through the input data and put the data into the corresponding bucket one by one;
Sort each bucket that is not empty;
Splice the sorted data from an empty bucket.
JavaScript code implementation:
/*Method description: bucket sort @param array array @param num Number of buckets*/ function bucketSort(array, num) { if (array.length <= 1) { return array; } var len = array.length, buckets = [], result = [], min = max = array[0], regex = '/^[1-9]+[0-9]*$/', space, n = 0; num = num || ((num > 1 && regex.test(num)) ? num : 10); for (var i = 1; i < len; i++) { min = min <= array[i] ? min : array[i]; max = max >= array[i] ? max : array[i]; } space = (max - min + 1) / num; for (var j = 0; j < len; j++) { var index = Math.floor((array[j] - min) / space); if (buckets[index]) { // Non-empty bucket, insert sort var k = buckets[index].length - 1; while (k >= 0 && buckets[index][k] > array[j]) { buckets[index][k + 1] = buckets[index][k]; k--; } buckets[index][k + 1] = array[j]; } else { //Empty bucket, initialize buckets[index] = []; buckets[index].push(array[j]); } } while (n < num) { result = result.concat(buckets[n]); n++; } return result; }3) Algorithm analysis
In the best case of bucket sorting, linear time O(n), the time complexity of bucket sorting depends on the time complexity of sorting data between buckets, because the time complexity of other parts is O(n). Obviously, the smaller the bucket is divided, the less data the bucket is, the less time it takes to sort it. But the corresponding space consumption will increase.
9. Counting sorting
1) Introduction to the algorithm
Counting sort is a stable sorting algorithm. Count sorting uses an additional array C, where the i-th element is the number of elements with a value equal to i in the array A to be sorted. Then, according to array C, the elements in A are arranged to the correct position. It can only sort integers.
2) Algorithm description and implementation
The specific algorithm is described as follows:
Find the largest and smallest elements in the array to be sorted;
Count the number of times each element with a value of i in the array appears and store it into the i-th item of array C;
Accumulate all counts (starting from the first element in C, each item and the previous item are added);
Reverse fill target array: Place each element i in the C(i)th item of the new array, and subtract C(i) by 1 for each element.
JavaScript code implementation:
function countingSort(array) { var len = array.length, B = [], C = [], min = max = array[0]; for (var i = 0; i < len; i++) { min = min <= array[i] ? min : array[i]; max = max >= array[i] ? max : array[i]; C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1; } for (var j = min; j < max; j++) { C[j + 1] = (C[j + 1] || 0) + (C[j] || 0); } for (var k = len - 1; k >=0; k--) { B[C[array[k]] - 1] = array[k]; C[array[k]]--; } return B; }3) Algorithm analysis
When the input element is n integers between 0 and k, its running time is O(n + k). Count sorting is not a comparison sorting, and the sorting speed is faster than any comparison sorting algorithm. Since the length of the array C used to count depends on the range of data in the array to be sorted (equal to the difference between the maximum and minimum values of the array to be sorted plus 1), this makes count sorting requires a lot of time and memory for arrays with a large data range.