Quick sort

  • Quicksort is recognized as one of the fastest algorithms.

  • Quicksort basic idea:

    1. Determine a pivot, usually the middle value of the array
    2. Place all values less than the fulcrum on the left (in ascending order, and vice versa) and all values greater than the fulcrum on the right
    3. Repeat the process until all sorts are complete

  • Specific practices (ascending order as an example) :

    1. Pivot: Divide the length of the array by 2 and round down to get the median value, get the index of the pivot, and get the value of the pivot through the index.
    2. Prepare an empty array for elements smaller than and larger than the fulcrum, such as left and right
    3. Get the array without the fulcrum and create a pointer to the first element of the new array
    4. The current value of the pointer is compared to the fulcrum, less than the fulcrum is placed in left, greater than the fulcrum is placed in right, and the pointer points to the next current value
    5. Repeat for left and right
    6. Concatenate three arrays (left, fulcrum, right) and return

  • JS implementation (recursive implementation) :

        let quickSort = array= > {
        if(array.length < 2) {
            return array
        } else {
            let left = []
            let right = []
            let index = Math.floor(array.length / 2)
            /* the return value of the splice function is the intercepted value. The return value of a function is always an array. 3. Execution of the function affects the original array */
            let pivot = array.splice(index, 1) [0]
            for (let i = 0; i < array.length; i++) {
                array[i] < pivot ? left.push(array[i]) : right.push(array[i])
            }
            return quickSort(left).concat([pivot], quickSort(right))
        }
    }
Copy the code

    Selection sort

  • The basic idea of selection sort:

    • (ascending) Find the smallest value in the array and place it at the top of the array

  • Specific practices (ascending order) :

    1. Defines the function that gets the minimum index
    2. The minimum and minimum index numbers are obtained by the minimum index function, and arrays that do not contain minimum values are intercepted by the index numbers
    3. Repeat above to get all min arrays ([min] + [other])
    4. Concat all arrays in sequence, sorting done

  • JS implementation (recursive implementation)

    let minIndex = array= > {
        let index = 0;
        if (array.length < 2) { return index }
        for (let i = 0; i < array.length; i++) {
            index = array[index] < array[i] ? index : i
        }
        return index
    }
    let chooseSort = array= > {
        if (array.length < 2) { return array }
        let index = minIndex(array)
        let min = array[index]
        // Notice the return value of splice
        array.splice(index, 1)
        return [min].concat(chooseSort(array))
    }
Copy the code

Merge sort

  • Also called merge sort, high efficiency, is a widely used sorting algorithm

  • Basic idea:

    • Pairwise merging two sorted arrays is faster than sorting from scratch. Split the array into n arrays with only one element, and keep merging them in pairs until you’ve sorted everything.

  • Specific practices (ascending order) :

    1. Slice the array from start to middle on the left and from middle to end on the right, repeating until each array has only one value
    2. Sets a pointer to the first current value at both ends.
    3. Compare the two ends of the pointer in pairs, take out the value that meets the condition, put it in front, and repeat
    4. Merge the compared arrays

  • JS implementation (recursive implementation)

    let merge = (left, right) = > {
        if (left.length === 0) { return right }
        if (right.length === 0) { return left }
        return left[0] < right[0]? [left[0]].concat(merge(left.slice(1), right)) : [right[0]].concat(merge(left, right.slice(1)))}let mergeSort = array= > {
        if (array.length < 2) { return array }
        let left = array.splice(0, array.length / 2)
        let right = array.splice(array.lengt / 2)
        return merge(mergeSort(left), mergeSort(right))
    }
Copy the code

Count sorting

  • Basic idea:

    • Using a hash table, treat each array element with a key: Key is an array element, and value is the number of occurrences. The hash table is traversed with Max as the maximum number of occurrences. During traversing, the value of Max that appears in the hash table is placed into the array to complete sorting. Counting sort is faster than all of the above because it only iterates through the array once. But you need to use an extra hash table, which is a classic trade of space for time.

  • Specific practices:

    1. Define the hash table hash, Max Max with an initial value of 0, and an empty array for sorting.
    2. Iterate through the list of numbers, place each element as a key and the number of occurrences of that element as a value into the hash table, and find the maximum value Max
    3. If the current value of Max is equal to the key of the hash table, put the current value of Max into the array value times
    4. Completes sorting, returns the sorted array

  • JS implementation

    let countSort = array= > {
        let hash = {}
        let max = 0
        let result = []
        for (let i = 0; i < array.length; i++) {
            if(! hash[array[i]]) { hash[array[i]] =1
            } else {
                hash[array[i]]++
            }
            max = max > array[i] ? max : array[i]
        }
        // The value of Max is available in the loop
        for (let i = 0; i <= max; i++) {
            if (i in hash) {
                for (let j = 0; j < hash[i]; j++) {
                // The value of I in the loop is the hash key
                    result.push(i)
                }
            }
        }
        return result
    }

Copy the code