preface

Master a variety of commonly used algorithms can enhance our own internal forces, exercise our logical thinking.

Exchange function

function swap(array, a, b) {
    [array[a], array[b]] = [array[b], array[a]];
}
Copy the code

Bubble sort

// Bubble sort
function bubbleSort(array) {
    const { length } = array;
    for (let i = 0; i < length; i++) {
        // The purpose of -i is that as the number of runs increases, there is no need to compare the last sorted element
        for (let j = 0; j < length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
            	swap(array, j, j + 1); }}}return array;
}
Copy the code

Selection sort

In situ sorting algorithm. The general idea of selection sort is to 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

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

Insertion sort

Insert sort builds the final sorted array, one item at a time. Let’s say the first term is sorted.

Next, it is compared with the second item: should the second item stay in place or be inserted before the first? This way, the first two items are sorted correctly, then compared to the third item (should it be inserted first, second, or third), and so on.

When sorting small arrays, this algorithm performs better than selective sort and bubble sort.

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

Hill sorting

Hill sort is the first algorithm to break through O(n ^ 2), which is based on insertion sort, and is generally better than O(n ^ 2).

function shellSort(array) {
    const length = array.length;
    / / interval
    let gap = (length / 2) | 0;
    while (gap >= 1) {
    	// Group by gap, then insert sort;
    	for (let i = gap; i < length; i++) {
            let temp = array[i];
            let j = i;
            while (j > gap - 1 && array[j - gap] > temp) {
            	array[j] = array[j - gap];
            	j -= gap;
            }
            array[j] = temp;
    	}
    	gap = Math.floor(gap / 2); }}Copy the code

Merge sort

Merge sort is the first algorithm that you can actually use and merge sort is good, order nlog of n.

For example, Mozilla Firefox uses merge sort as an implementation of array.prototype.sort

Merge sort is divide-and-conquer, recursive, so we’re going to split the algorithm into two functions, and the first function is going to split the large array into smaller arrays and call the sorting helper function

function mergeSort(array) {
	// Merge sort converts a large array into several smaller arrays until there is only one item. Since the algorithm is recursive, we need a stop condition, in this case to determine whether the length of the array is 1
	if (array.length > 1) {
            const { length } = array;
            const middle = Math.floor(length / 2);
            const left = mergeSort(array.slice(0, middle));
            const right = mergeSort(array.slice(middle, length));
            array = merge(left, right);
	}
	return array;
}
function merge(left, right) {
	let i = 0;
	let j = 0;
	const result = [];
	while (i < left.length && j < right.length) {
            result.push(left[i] > right[j] ? left[i++] : right[j++]);
	}
	return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}
Copy the code

Binary search

The algorithm requires that the data structure to be searched is sorted and the process is:

1. Select the middle value of the array

2. If the selected value is the value to be searched, the algorithm is returned

3. If the value to be searched is smaller than the selected value, return the step to look for (smaller) in the subarray to the left of the selected value.

4. If the value to be searched is larger than the selected value, return step to search for (larger) in the subarray to the right of the selected value.

function binarySearch(array, target) {
	let low = 0;
	let high = array.length - 1;
	while (low <= high) {
            const mid = Math.floor((low + high) / 2);
            const middleValue = array[mid];
            if (middleValue > target) {
            	high = mid - 1;
            } else if (middleValue < target) {
            	low = mid + 1;
            } else {
            	returnmid; }}return - 1;
}

Copy the code

conclusion

So that’s the usual sort method