1. Bubble sort

Like bubbles in water, small bubbles at the bottom rise to the top and become large bubbles. Bubble sort is a loop that puts the largest number to the right each time

function BubbleSort(array) {
            for (let i = 0; i < array.length - 1; i++) { // How many times did it loop
                for (j = 0; j < array.length - i - 1; j++) { // How many times does each loop compare
                    if (array[j] > array[j + 1]) {
                        [array[j], array[j + 1]] = [array[j + 1], array[j]]
                    }
                }
            }
            return array;
        }
Copy the code

More times (N – 1) + (N – 2) +… + 3 + 2 + 1 = N * (N – 1) / 2

Comparison times time complexity: O(N^2)

Every time you make a comparison, you swap it out. It’s not very efficient, but the concept is easy to understand

2. Select sort

Every time you sort, you pick the smallest one and put it on the left

function selectionSort(array) {
            for (let i = 0; i < array.length - 1; i++) { // How many times does the loop compare to the penultimate
                let min = i
                for (let j = i + 1; j < array.length; j++) { // How many times does each loop compare
                    if (array[min] > array[j]) {
                        min = j
                    }
                }
                [array[min], array[i]] = [array[i], array[min]]
            }
            return array
        }
Copy the code

More times (N – 1) + (N – 2) +… + 3 + 2 + 1 = N * (N – 1) / 2

Comparison times time complexity: O(N^2)

Number of switches: N-1

Switching times Time complexity: O(N)

Fewer switching times, the execution efficiency is higher than bubble sort

3. Insert sort

The principle is local order, starting at the second position, each cycle compares with the number on the left, and inserts into the appropriate position

function insertSort(array) {
            for (let i = 1; i < array.length; i++) {
                let temp = array[i] // Temp is the data to be compared
                let j = i
                while (temp < array[j - 1] && j > 0) { // Because the left side is partially ordered, compare with the left one digit first, less than the left to continue the comparison
                    array[j] = array[j - 1]
                    j--
                }
                array[j] = temp //j has already been replaced by j
            }
            return array
        }
Copy the code

Most compare number: 1 + 2 + 3 +… + (N – 2) + (N – 1) = N * (N – 1) / 2

Average number of comparisons :(N * n-1)/4

Then the average number of replications is (N * n-1)/4

Comparison times time complexity: O(N^2)

4. Quicksort

The idea of quicksort is to divide and conquer. Select a data as a hub, move the numbers smaller than the hub to the left, and move the numbers larger than the hub to the right. The left and right regions continue to do the same operation, so as to achieve sorting

function quiceSort(arr) {
            if (arr.length <= 1) {
                return arr
            };
            let pivotIndex = Math.floor(arr.length / 2) // Base position
            let pivot = arr.splice(pivotIndex, 1) [0] / / reference number
            let left = []
            let right = []
            for (var i = 0; i < arr.length; i++) {
                if (arr[i] < pivot) {
                    left.push(arr[i])
                } else {
                    right.push(arr[i])
                }
            }
            return quiceSort(left).concat([pivot], quiceSort(right))
        }
Copy the code

Comparison times Time complexity: O(N*logN)