当前位置：网站首页>Ten sorting details

Ten sorting details

2022-07-26 19:50:00 【Jiangjiangchun】

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
}