Ten sorting details

  Bubble sort (n2)

The first layer circulates through the outer layer length -1 The item , To the front length-1 Number sorting

The inner loop traverses to length - i -1, To the front length - i -1 Number bubbling

function bubbleSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            const temp = arr[j + 1]
            arr[j + 1] = arr[j]
            arr[j] = temp
        }
    }
}

Selection sort （n2）

Select the minimum joining sequence area from the disordered sequence area

The outer loop ： Expand the disordered area to length-1

Inner circulation ： Select the minimum subscript in the disordered area

function selectSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let minIndex = i
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        const tmp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tmp;
    }
}

Insertion sort （n2）

Choose any one from the disordered areas , Find its position in the disordered area

The outer loop  ： Expand ordered areas , To length-1

Inner circulation ： Find the insertion position in the ordered area

use pre and current Assist in finding location

function insertionSort(arr) {
    for (let i = i; i < arr.length - 1; i++) {
        let preIndex = i - 1
        let current = arr[i]
        while (preIndex > 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex]
            preIndex--
        }
    }
    arr[preIndex + 1] = current
}

Shell Sort （nlogn~nlog2n）

use gap Split the array , Insert and sort each small array

Outer circulation ：gap Half off each time , until gap by 0

function shellSort(arr) {
    for (let gap = Math.floor(arr.length); gap > 0; gap = Math.floor(arr / 2)) {
        for (let i = gap; gap < arr.length; i++) {
            const curr = arr[i]
            let j = i
            while (j - gap > 0 && arr[j-gap] >curr) {
                arr[j]=arr[j-gap]
                j=j-gap
            }
            arr[j]=curr
        }
    }
}

Merge sort （nlogn）

Standard divide and conquer , Divided into two arrays , Recursive solution .

function mergeSort(arr) {
    function sort(arr, left, right) {
        if (left < right) {
            const mid = (left + right) / 2
            leftArr = sort(arr, left, mid)
            rightArr = sort(arr, mid + 1, right)
            return merge(leftArr, rightArr)
        }
        return left > 0 ? [arr[left]] : []
    }
    function merge(leftArr, leftArr) {
        const res = []
        const leftPtr = 0
        const rightPtr = 0
        while (leftPtr < leftArr.length && rightPtr < rightArr.length) {
            if (leftArr[leftPtr] < leftArr[rightPtr]) {
                res.push(leftArr[leftPtr++])
            } else {
                res.push(rightArr[rightPtr++])
            }
        }
        while (leftPtr < leftArr.length) {
            res.push(leftArr[leftPtr++])
        }
        while (rightPtr < rightArr.length) {
            res.push(rightArr[rightPtr++])
        }
        return res
    }
}

Quick sort （nlogn-n2）

Divide and conquer method , Select the first element , Divide the array into a group larger than the element and a group smaller than the element . Recursive solution

It mainly includes four steps

Back and forth , Find a comparison x Small

In exchange for

After going , Find a comparison x Big

In exchange for

function quickSort(arr) {
    function sort(arr, low, high) {
        let i = low
        let j = high
        const x = arr[low]
        while (i < j) {
            while (i < j && arr[j] > x) {
                j--
            }
            if (i < j) {
                arr[i] = arr[j]
                i++
            }
            while (i < j && arr[i] < x) {
                i++
            }
            if (i < j) {
                arr[j] = arr[i]
                j--
            }
        }
        arr[i] = x
        sort(arr, low, i - 1)
        sort(arr, i + 1, high)
    }

}

Count sorting （n+k）

Determine the array range , Open up a continuous space , One time storage , Read in spatial order

It's like a hash table , Store the subscript as a value

//  Count sorting 
function countingSort(arr) {
    let maxValue = Number.MIN_VALUE
    let minValue = Number.MAX_VALUE
    const res = []
    //  Determine the space 
    arr.forEach(num => {
        maxValue = num > maxValue ? num : maxValue
        minValue = num > minValue ? minValue : num
    })
    if (minValue < 0) {
        offset = -minValue
    }
    const bucket=new Array(maxValue+offset+1).fill(0)
    //  Deposit the corresponding subscript 
    arr.forEach(num=>{
        bucket[num+offset]++
    })
    bucket.forEach((store,index)=>{
        while(store--){
            res.push(index-offset)
        }
    })
    return result
}

Radix sorting

Put each one in a different bucket

Heap sort

  Big pile top ： The root node is larger than children

1、 Pre function , Maintain the nature of the big top pile

Swap the root node with the maximum

Recursively maintain the properties of the exchanged node

 2、 Build the big top heap

Start with the parent of the first leaf node ：n - 2 / 2 = n / 2 - 1

Traverse every node , Conduct property maintenance

3、 Sort

Swap the head and tail

Then disconnect the tail connection

Maintain the large top pile

At this time, the tail is the largest