The following is a summary of some of the sorting algorithms I have encountered. In fact, we all know there is a sort method in JS. This article is for those who are interested in sorting algorithms. To facilitate implementation, let’s first define a few general functions

const Compare = {
    LESS_THAN: -1.BIGGER_THAN: 1.EQUAL: 0,}function defaultCompare(a, b) {
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

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

ES6 can also be used for swap

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

Bubble sort

const test_arr0 = [2.1.78.45.62.90.55.36.45.28]  // The array to test
function bubbleSort(array, compareFn = defaultCompare) {
    const { length } = array;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1 - i; j++) {
            if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
                swap(array, j, j + 1); }}}return array;
}

const bubble_res = bubbleSort(test_arr0);
console.log('Bubble sort:', bubble_res);
Copy the code

Selection sort

const test_arr1 = [2.1.78.45.62.90.55.36.45.28]  // The array to test
function selectionSort(array, compareFn = defaultCompare) {
    const { length } = array;
    let indexMin;  // Define the smallest value of index
    for (let i = 0; i < length - 1; i++) {  // Since we want to compare, we only need one less poll
        indexMin = i; // The smallest is the current I
        // Find the minimum value
        for (let j = i; j < length; j++) {
            if (compareFn(array[indexMin], array[j]) === Compare.BIGGER_THAN) {
                indexMin = j; // If the current minimum indexMin is not the smallest, then we set the minimum indexMin to j}}// If the current value is not the minimum, we switch places
        if (i !== indexMin) {
            swap(array, i, indexMin);
        }
    }
    return array;
}

const selection_res = selectionSort(test_arr1);
console.log('Selection sort:', selection_res);
Copy the code

Insertion sort

const test_arr2 = [2.1.78.45.62.90.55.36.45.28]  // The array to test
function insertionSort(array, compareFn = defaultCompare) {
    const { length } = array;
    let temp; // Store the element to be inserted
    // Start with the second
    for (let i = 1; i < length; i++) {
        let j = i; // We store I
        temp = array[i]; // The current value
        // The boundary conditions are j>0 and our current value is smaller than its predecessor
        while (j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) {
            array[j] = array[j - 1]; // Move the preceding value to the right to the current value. That is, the current value is equal to the previous value
            j--; // The position changes to the previous position of the current position
        }
        array[j] = temp; // Insert to current position
    }
    return array;
}

const insertion_res = insertionSort(test_arr2);
console.log('Insert sort:', insertion_res);
Copy the code

Merge sort

const test_arr3 = [2.1.78.45.62.90.55.36.45.28];  // The array to test
function mergeSort(array, compareFn = defaultCompare) {
    if (array.length > 1) { // If the array length is greater than 1
        const { length } = array;
        const middle = Math.floor(length / 2); // Let's round this down
        const left = mergeSort(array.slice(0, middle), compareFn);
        const right = mergeSort(array.slice(middle, length), compareFn);
        array = merge(left, right, compareFn);
    }
    return array;
}

function merge(left, right, compareFn) {
    let i = 0;
    let j = 0;
    const result = [];
    while (i < left.length && j < right.length) {
        result.push(
            compareFn(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]
        )
    }
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

const merge_res = mergeSort(test_arr3);
console.log('Merge sort:', merge_res);
Copy the code

Quick sort

The worst case for quicksort is O(n ^ 2), for example, quicksort. But its amortized expected time is O(n log n), and the constant factor implied in the O(n log n) notation is very small, much smaller than the stable O(n log n) merge sort. Therefore, for most random sequences with weak order, quicksort is always better than merge sort.

const test_arr4 = [2.1.78.45.62.90.55.36.45.28]  // The array to test

function quickSort(array, left, right, compareFn = defaultCompare) {
    var { length } = array; // Get the array length
    var partitionIndex; // Get the index of the current operation
    var left = typeofleft ! ="number" ? 0 : left; / / the left
    var right = typeofright ! ="number" ? length - 1 : right; / / most the right side

    // Compare the far left with the far right
    if (compareFn(left, right) === Compare.LESS_THAN) {
        partitionIndex = partition(array, left, right);
        quickSort(array, left, partitionIndex - 1); // Compare the left part of the base value
        quickSort(array, partitionIndex + 1, right); // Compare the right part of the base value
    }
    return array;
}

function partition(array, left, right, compareFn = defaultCompare) { // Partition operations
    var pivot = left; // Set the leftmost value to be the pivot point.
    var index = left + 1; // Start from the first value on the right
    // Start the loop, starting from the first value on the right and continuing to the rightmost
    for (var i = index; i <= right; i++) {
        // If the current value is smaller than the base value, then we place these values to the right of the base value
        if (compareFn(array[i], array[pivot]) === Compare.LESS_THAN) {
            swap(array, i, index); // The starting position is swapped with the current I
            index++; // }}// At the moment, since the values to the right of the base value are all smaller than it, we swap the base value with the rightmost value of the current sequence of values that are smaller than it
    swap(array, pivot, index - 1);
    return index - 1; // The value returned is the rightmost item of the array smaller than the current reference value
}
const quick_res = quickSort(test_arr4);
console.log('Quicksort:', quick_res);

Copy the code

Hill sorting

function shellSort(array, compareFn = defaultCompare) { let { length } = array; let temp; let gap = 1; While (gap < length / 3) {// Dynamically define interval sequence gap = gap * 3 + 1; } for (gap; gap > 0; gap = Math.floor(gap / 3)) { for (var i = gap; i < length; i++) { temp = array[i]; for (var j = i - gap; j >= 0 && array[j] > temp; j -= gap) { array[j + gap] = array[j]; } array[j + gap] = temp; } } return array; } const test_arr5 = [2, 1, 78, 45, 62, 90, 55, 36, 45, 28] Console. log(' Hill sort: ', shell_res);Copy the code

Counting sort (note that this is only for integer sort)

function countingSort(array) {
    if (array.length < 2) {
        return array;
    }
    const maxValue = findMaxValue(array);

    const counts = new Array(maxValue + 1); // Create an array whose length is the maximum in the current array

    array.forEach(element= > {
        // console.log(typeof counts); // object
        if(! counts[element]) { counts[element] =0;
        }
        counts[element]++;
    });
    // console.log(' counts after the first step ', counts); // Counts [1:1,2:1,28:1....] ; It's actually an object

    let sortedIndex = 0;
    counts.forEach((count, i) = > {
        // console.log(count, i); // 1 1 1 2 1 28 1 36 2 45...
        while (count > 0) { array[sortedIndex++] = i; count--; }})return array;
}

const test_arr6 = [2.1.78.45.62.90.55.36.45.28];
const counting_res = countingSort(test_arr6);
console.log('Count sort:', counting_res);

function findMaxValue(array) {
    let max = array[0];
    for (let i = 1; i < array.length; i++) {
        if(array[i] > max) { max = array[i]; }}return max;
}
Copy the code