preface

This comb through the 6 sorting algorithms, from the grasp of the idea to realize it, or draw a lot of time, and through the notes comb again, just sort out, to everyone a cast a brick to attract jade effect.

The most common sorting algorithm in 6 is GIF, which is easier to help you understand the sorting idea.

The code is here on GitHub

Read the article here

The 6 sorts are as follows: 👇

  • Bubble sort
  • Count sorting
  • Quick sort
  • Merge sort
  • Insertion sort
  • Selection sort

The time complexity is shown in 👇

Complexity analysis of sorting algorithm

The following GIF is from Zhihu Shuaidi

Bubble sort

The name comes from the fact that it floats like a bubble, which you can imagine, comparing the sizes of two elements next to each other at a time, and then slowly ‘floats’. I made that up. Let’s see.

“Time complexity O(n*n)“

Train of thought

  1. Compare adjacent elements, and if the former is larger than the latter, they switch positions.
  2. Do the same for each pair of adjacent elements, starting from the first pair to the last pair, so that the last element is the largest element.
  3. Repeat the above steps for n elements, each loop excluding the last current one.
  4. Repeat steps 1 through 3 until the sorting is complete.

animation

Bubble sort

Code implementation

// The outermost loop controls the number of loops

// Each comparison is about the size relationship between two adjacent objects

let BubbleSort = function (arr, flag = 0) {

    let len = arr.length



    for (let i = 0; i < len - 1; i++) {

        for (let j = 0; j < len - 1 - i; j++) {

            if (arr[j] > arr[j + 1]) {

                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]

            }

        }

    }

    return flag ? arr.reverse() : arr

}



let arr = [2.9.6.7.4.3.1.7]

console.log(BubbleSort(arr, 1))

Copy the code

Count sorting

As the name suggests, the idea is to take the elements of an array as subscripts, and then use a temporary array to count the number of occurrences of that element.

The data in the array must be integers, and the difference between the maximum and minimum values should not be too large, for “if the data is negative, my implementation is optimized for this”.

“Time complexity: O(n+k)“

Train of thought

1. Calculate the traveling value D, the minimum value is less than 0, plus itself add

2. Create a statistics array and count the number of corresponding elements

3. The statistics array is distorted so that the following elements are equal to the sum of the preceding elements, which is the ranking array

4. Iterate over the original array, find the correct position from the statistics array, and output to the result array

animation

Count sorting

Code implementation

// Count sort

let countingSort = function(arr, flag = 0) {

    let min = arr[0].

        max = arr[0].

        len = arr.length;

    // Obtain the maximum and minimum values

    for(let i = 0; i < len; i++) {

        max = Math.max(arr[i], max)

        min = Math.min(arr[i], min)

    }

    // 1. Calculate the travel value d, the minimum value is less than 0, plus itself add



    let d =  max - min,

        add = min < 0 ? -min : 0;

    //2. Create an array and count the number of corresponding elements

    let countArray  = new Array(d+1+add).fill(0)

    for(let i = 0; i < len; i++){

        let demp = arr[i]- min + add

        countArray[ demp ] += 1 

    }

    

    //3. The statistics array is distorted so that the following elements are equal to the sum of the preceding elements, which is the ranking array

    let sum = 0;



    // We need to iterate over the length of the countArray array

    for(let i = 0; i < d+1+add; i++){

        sum += countArray[i]

        countArray[i] = sum;

    }

    let res = new Array(len)

    4. Iterate over the original array, find the correct position from the statistics array, and output to the result array

    for(let i = 0; i < len; i++){

        let demp = arr[i] -min + add

        res[ countArray[demp] - 1 ] = arr[i]

        countArray[demp] --;

    }

    return flag ? res.reverse() : res

}



let arr = [2.9.6.7.4.3.1.7.0.- 1.2 -]

console.log(countingSort(arr))

Copy the code

Quick sort

Basic idea: The records to be sorted are separated into two independent parts by one sorting. The keywords in one part of the records are smaller than those in the other part. Then the two parts of the records can be sorted separately to achieve the order of the whole sequence.

“Time complexity: O(nlogn)“

Train of thought

  1. Select the middle number of the array as the cardinality and take this cardinality from the array
  2. Prepare two array containers, go through the array, one by one with the base comparison, the smaller in the left container, the larger in the right container;
  3. Recursively process the elements of the two containers, and combine the processed data and cardinality into an array of size, and return.

animation

Quick sort

Code implementation

let quickSort = function (arr) {

    // The recursive exit is an array of length 1

    if (arr.length <= 1) return arr

    // Get the index of the intermediate value, using math.floor to round it down;

    let index = Math.floor(arr.length / 2)

    Splice = splice; splice = splice; splice = splice; splice = splice;

    // If pivot=arr[index]; There will be an infinite recursive error;

    // splice affects the original array

    let pivot = arr.splice(index, 1) [0].

        left = [],

        right = [];

    console.log(pivot)

    console.log(arr)

    for (let i = 0; i < arr.length; i++) {

        if (pivot > arr[i]) {

            left.push(arr[i])

        } else {

            right.push(arr[i])

        }

    }

    return quickSort(left).concat([pivot], quickSort(right));

}



//let arr = [2, 9, 6, 7, 4, 3, 1, 7]

// console.log(quickSort(arr))

Copy the code

Merge sort

Merging two ordered sequences into one ordered sequence is called merging.

Basic idea and process: first decompose the sequence recursively, then merge the sequence (a typical application of the idea of divide and conquer)

“Time complexity: O(nlog(n))“

Train of thought

  1. Split an array into groups A and B. The groups continue to split until each group has only one element.
  2. Follow the split process to merge the groups step by step. Since each group starts with only one element, it can be seen as an order within the group. Merging the groups can be seen as a process of merging two ordered arrays.
  3. Repeat the second step for the left and right small sequence until each interval has only one number.

animation

Merge sort

Code implementation

const merge = (left, right) = > { // Merge the array



    let result = []

    // Use the shift() method to delete the first element and return the value

    while (left.length && right.length) {

        if (left[0] <= right[0]) {

            result.push(left.shift())

        } else {

            result.push(right.shift())

        }

    }

    while (left.length) {

        result.push(left.shift())

    }



    while (right.length) {

        result.push(right.shift())

    }

    return result

}



let mergeSort = function (arr) {

    if (arr.length <= 1)

        return arr

    let mid = Math.floor(arr.length / 2)

    // Split the array

    let left = arr.slice(0, mid),

        right = arr.slice(mid);

    let mergeLeftArray = mergeSort(left),

        mergeRightArray = mergeSort(right)

    return merge(mergeLeftArray, mergeRightArray)

}



let arr = [2.9.6.7.4.3.1.7.0.- 1.2 -]

console.log(mergeSort(arr))



Copy the code

Insertion sort

As the name suggests: By building an ordered sequence, unsorted data is scanned back and forward in the sorted sequence to find the appropriate position and insert it.

“Time complexity: O(n*n)“

Train of thought

  1. Starting with the first element, the element can be considered sorted;
  2. Take the next element and scan backwards through the sequence of sorted elements;
  3. If the element (sorted) is greater than the new element, move the element to the next position;
  4. Repeat step 3 until you find the place where the sorted element is less than or equal to the new element;
  5. Repeat steps 2 to 5.

animation

Insertion sort

Code implementation

let insertionSort = function (arr) {

    let len = arr.length



    for (let i = 0; i < len; i++) {

        let preIndex = i - 1.

            cur = arr[i];

        while (preIndex >= 0 && arr[preIndex] > cur) {

            arr[preIndex + 1] = arr[preIndex]

            preIndex--;

        }

        arr[preIndex + 1] = cur

    }

    return arr

}





let arr = [2.9.6.7.4.3.1.7.0.- 1.2 -]

console.log(insertionSort(arr))

Copy the code

Selection sort

Select the largest (smallest) element from the array as the first element every time until the array is sorted

“Time complexity O(n*n)“

Train of thought

  1. I have n numbers, and I have to sort them n minus 1 times
  2. The first time you choose the minimum value, put it first
  3. The second time, select the minimum value and put it in second place
  4. … . Repeat the process
  5. Pick the minimum value in the n-1st place and put it in the n-1st place

animation

Selection sort

Code implementation

let selectSort = function (arr, flag = 0) {

    let len = arr.length,

        temp = 0;



    // We need to sort len-1 times

    for (let i = 0; i < len - 1; i++) {

        temp = i;

        for (let j = i + 1; j < len; j++) {

            if (arr[j] < arr[temp])

                temp = j;

        }

        // Ensure that bit I is the minimum value in each trip

        if(temp ! == i) {

            [arr[i], arr[temp]] = [arr[temp], arr[i]]

        }

    }



    return flag ? arr.reverse() : arr

}







let arr = [2.9.6.7.4.3.1.7.0.- 1.2 -]

console.log(selectSort(arr, 1))

Copy the code

❤️ Thank you all

If you found this helpful:

  1. Like support, let more people can also see this content.
  2. Share your thoughts with me in the comments section, and record your thought process in the comments section.
  3. If you like it, you can also read TianTian’s recent article (thanks to the encouragement and support from friends of Mine 🌹🌹🌹) :
    • 21 Handwritten JavaScript interview questions once and for all (420+👍)
    • 18 browser interview questions (680+👍)
    • 54 interview questions in JavaScript (580+👍)
    • 9 Basic Operations for the “Algorithms and Data Structures” list (160+👍)
    • Chrome DevTools debugging tips for men, efficiency 🚀🚀🚀(210+👍)
    • “How browsers work” To my Girlfriend – Rendering Process (1.1w + words) (230+👍)
    • “Array method” from detailed operation of JS array to analysis of V8 array.js(220+👍)
    • How the Browser Works the Secret to your Girlfriend – Browser composition & Network Request (1.2W words)(240+👍)