There are nine common sorting algorithms in JavaScript
- 2020-03-30 03:50:12
- OfStack
The written interview often involves a variety of algorithms, this article briefly introduces some commonly used algorithms, with JavaScript implementation.
I. insertion sort
1) algorithm introduction
The algorithm description of Insertion Sort is a simple and intuitive sorting algorithm. It works by building an ordered sequence and, for unsorted data, scanning backwards and forwards through the sorted sequence to find the appropriate location and insert. In the implementation of insertion sort, in-place sort is usually adopted (that is, the sort that only needs extra space of O(1)). Therefore, in the backward and forward scanning process, the sorted elements need to be moved backward repeatedly to provide insertion space for the latest elements.
2) algorithm description and implementation
Generally, insertion sort is implemented on an array using in-place. The specific algorithm is described as follows:
Start with the first element, which can be considered sorted;
Take the next element and scan it backwards and forwards through the 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 to be less than or equal to the new element;
After inserting the new element into this location;
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: the input array is arranged in ascending order. T (n) = O (n)
Worst case: the input array is sorted in descending order. T (n) = O (n2)
Average case: T(n) = O(n2)
Binary insertion sort
1) algorithm introduction
Binary-insert-sort is a sort algorithm that makes a small change on the direct insertion sort algorithm. The biggest difference between it and the direct insertion sort algorithm is that the method of binary search is used to find the insertion position.
2) algorithm description and implementation
Generally, insertion sort is implemented on an array using in-place. The specific algorithm is described as follows:
Start with the first element, which can be considered sorted;
Take the next element and binary search the position of the first larger number in the sorted element sequence;
After inserting the new element into this location;
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 case: T(n) = O(n2)
Selection sort
1) algorithm introduction
Selection-sort is a simple and intuitive sorting algorithm. How it works: find the smallest (large) element in the unsorted sequence, store it at the beginning of the sorted sequence, and then continue to look for the smallest (large) element from the remaining unsorted elements, and place it at the end of the sorted sequence. And so on, until all the elements are sorted.
2) algorithm description and implementation
The direct selection sort of n records can get the ordered result through n-1 direct selection sort. The specific algorithm is described as follows:
Initial state: the disordered area is R[1..n], and the ordered area is empty;
The I th sort (I =1,2,3... At the beginning of n-1), the current ordered and disordered areas are R[1.. I -1] and R(I.. N). The sequence sort selects the record R[k] with the smallest keyword from the current unordered area, and exchanges it with the first record R in the unordered area, so that R[1.. I] and R[I +1..n) become the new ordered area with the number of records increasing by 1 and the new unordered area with the number of records decreasing by 1, respectively.
At the end of the n minus 1 pass, 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 case: T(n) = O(n2)
Bubble sort
1) algorithm introduction
Bubble sort 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 task of visiting a sequence is repeated until there is no need to swap, that is, the sequence has been sorted. The algorithm got its name because smaller elements slowly "float" to the top of the list by swapping.
2) algorithm description and implementation
The specific algorithm is described as follows:
Compare adjacent elements. If the first one is bigger than the second, we swap them;
Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair, so that the last element should be the largest number;
Repeat the above steps for all but the last element.
Repeat steps 1 through 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 case: T(n) = O(n2)
quicksort
1) algorithm introduction
The basic idea of quicksort: through a single sort to separate the records to be sorted into two separate parts, in which the keywords of one part of the records are smaller than the keywords of the other part, then the records of the two parts can be continued to sort, so as to achieve the order of the whole sequence.
2) algorithm description and implementation
Quicksort USES divide-and-conquer to divide a list into two sub-lists. The specific algorithm is described as follows:
Pick an element from the sequence, called pivot;
Reorder the sequence so that all elements smaller than the base value are placed in front of the base, and all elements larger than the base value are placed after the base (the same number can go to either side). After the partition exits, the benchmark is in the middle of the sequence. This is called a partition operation;
Recursive is the recursive sorting of subseries of elements less than the base value and subseries greater than the base value.
JavaScript code implementation:
//Methods a
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 case: T(n) = O(nlogn)
Heap sort
1) algorithm introduction
Heapsort (Heapsort) is a sort algorithm designed using the heap as a data structure. Pile-up is a nearly complete binary tree structure and satisfies the property of pile-up: that is, the key value or index of the child is always less 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 region;
Swap the top element R[1] with the last element R[n], and you get a new unordered region (R1,R2... Rn-1) and a new ordered region (Rn) that satisfies R[1,2...n-1]< = R [n].
Since the new heap top R[1] after the swap may violate the properties of the heap, the current unordered area (R1,R2,... Rn-1) is adjusted to a new heap, and then R[1] is again swapped with the last element of the unordered region to obtain a new unordered region (R1,R2... Rn-2) and the new ordered region rn-1,Rn. Repeat this process until the number of elements in the ordered area is n-1, then the whole sorting process is completed.
JavaScript code implementation:
function heapSort(array) {
if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
// Building the 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!';
}
}
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, largest = 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, largest, 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 case: T(n) = O(nlogn)
Merge sort
1) algorithm introduction
Merge sort is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. Merge sort is a stable sort method. By combining the ordered subsequences, a completely ordered sequence is obtained. That is, make each subsequence ordered first, and then make the subsequence ordered between segments. 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:
The input sequence of length n is divided into two subsequences of length n/2.
Merge sort is used for the two subsequences respectively.
To combine two sorted subsequences into one final collating 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 case: T(n) = O(nlogn)
Eight, bucket sort
1) algorithm introduction
Bucket sort works by assuming that the input data is evenly distributed, dividing the data into a finite number of buckets and sorting each Bucket separately (it is possible to use another sorting algorithm or to continue sorting recursively using Bucket sort).
2) algorithm description and implementation
The specific algorithm is described as follows:
Set a quantified array to be an empty bucket;
Go through the input data and put the data one by one into the corresponding bucket.
Sort each bucket that is not empty;
The ordered data is spliced together from never an empty bucket.
JavaScript code implementation:
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, initialized
buckets[index] = [];
buckets[index].push(array[j]);
}
}
while (n < num) {
result = result.concat(buckets[n]);
n++;
}
return result;
}
3) algorithm analysis
Bucket sort is best used in linear time O(n), and the time complexity of bucket sort depends on the time complexity of sorting the data between buckets, because the time complexity of other parts is O(n). Obviously, the smaller the buckets are, the less data there is between the buckets, and the less time it takes to sort. But the corresponding space consumption will increase.
Count sort
1) algorithm introduction
Counting sort is a stable sorting algorithm. Counting sort USES an extra array C, where the ith element is the number of elements whose value in the array to be sorted is equal to I. Then the elements in A are arranged in the correct position according to the array C. 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 occurrences of each element with value I in the array, and store the ith item in the array C.
Add up all the counts (starting with the first element in C, each term and the previous term);
Backfill the target array: place each element I in the C(I) of the new array, subtracting C(I) from 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). Counting sort is not comparison sort, and sort is faster than any comparison sort 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 counting sort time and memory intensive for arrays with large data ranges.