Preface: When doing the leetcode scheduling problem with there is a very simple, but the official to the degree of difficulty is moderate, is not to say that the problem is how hard to do, but what would it be possible for me to have extended to the problem is, so I think this problem is valuable, to take this opportunity to summarize the commonly used sorting algorithms, hoping to bring some help for oneself, It will also help anyone reading this article

Sorting algorithm

Sorting algorithms can be roughly divided into two categories: comparison based sorting algorithms (bubble, select, insert, merge, fast) and non-comparison based sorting algorithms (count, cardinality)

Bubble sort

Basic idea: the outer loop is pairwise compared each time, and the largest element of the unscheduled portion of each round is placed at the end of the array, time complexity O(N^2).

Array.prototype.BubSort = (arr) => {
    for (let i = 0; i < arr.length - 1; i++) {
        let flag = true;
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                flag = false; }}if (flag) returnarr; // If we do not swap at all through the inner loop, which means the array is sorted, we can stop bubbling sort at this point. }return arr
}

Copy the code

Selection sort

Each round selects the smallest part of the unscheduled part and swaps it to the beginning of the unscheduled part. After several steps, the entire array is arranged.

Array.prototype.SelectSort = (arr) => {
    for (var i = 0; i < arr.length-1; i++) {
        var flag = i
        for (var j = i + 1; j < arr.length; j++) {
            if (arr[flag] > arr[j]) {
                flag = j
            }
        }
        var temp = arr[flag]
        arr[flag] = arr[i]
        arr[i] = temp
    }
    return arr
}
Copy the code

Insertion sort

Insert a number one at a time into an ordered array, making it a longer ordered array, and after a finite number of operations, the array will be ordered.

Array.prototype.InsSort = (arr) => {
    for (let i = 1; i < arr.length; i++) {
        let temp = arr[i];
        let j = i;
        while (j > 0 && arr[j - 1] > temp) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
    return arr
} 
Copy the code

Merge sort

With extra space, merge two ordered arrays to get a longer ordered array.

Algorithm idea: divide and conquer

Array.prototype.MerSort = (nums) => {
    let sort = (left, right) => {
        if (left >= right) return;
        let mid = parseInt((right + left) / 2)
        sort(left, mid);
        sort(mid + 1, right);
        merge(left, mid, right);
        return nums;
    }
    let merge = (left, mid, right) => {
        let arr = [];
        let index = 0;
        let i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            arr[index++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
        }
        while (i <= mid) arr[index++] = nums[i++];
        while (j <= right) arr[index++] = nums[j++];
        for (lett = 0; t < index; t++) { nums[left + t] = arr[t]; }}return sort(0, nums.length - 1);
}
Copy the code

Quick sort

Each time you order an element (the element stays where it should eventually be), you recursively order the element to the left and the element to the right, and so on until the array is sorted.

Algorithm idea: divide and conquer

const QuiSort = (array) => {
    const sort = (arr, left = 0, right = arr.length - 1) => {
        if(left >= right) {// If the left index is greater than or equal to the right index, the collation is completereturn
        }
        let i = left
        letJ = right const baseVal = arr[jwhile(I < j) {// Place all numbers smaller than the base value on the left and large numbers on the rightwhile(I < j && arr[I] <= baseVal) {// Find a number larger than the base value and swap I ++} arr[j] = arr[I] // Assign the value to yourself (I = j).while(j > I &&arr [j] >= baseVal) {// Find a number less than the base value and swap j--} arr[I] = arr[j] // assign a value less than the base value to yourself (I = j)} Sort (arr, left, j-1) sort(arr, j + 1, arr, j + 1) Const newArr = array.concat() // To make sure this function is pure copy array sort(newArr) oncereturn newArr
}
 
Copy the code

Count sorting

Take the value of the array element as the key, the number of occurrences of the value into a temporary array, and finally iterate over the temporary array to restore the original array. Because JavaScript array subscripts are stored as strings, count sort can be used to arrange negative numbers, but not decimals.

Array.prototype.CouSort = (arr) => {
    var temp = [];
    arr.map((item)=>{
        temp[item] = ++temp[item] || 1
    })
    arr = []
    temp.map((item , index)=>{
        while(item--){
            arr.push(index)
        }
    })
    return arr
}
Copy the code

Radix sort

Using ten buckets 0-9, place each number from lowest to highest in the corresponding bucket according to the number of digits, and loop the maximum number of digits. But you can only arrange positive integers, because you can’t compare a negative sign with a decimal point.

Array.prototype.CouSort = (nums) => {// Compute the number of bitslet getDigits = (n) => {
        let sum = 0;
        while (n) {
            sum++;
            n = parseInt(n / 10);
        }
        return sum;
    }
    let arr = Array.from(Array(10)).map(() => Array());
    letmax = Math.max(... nums);let maxDigits = getDigits(max);
    for (leti = 0, len = nums.length; i < len; Nums [I] = (nums[I] +) {// Use 0 to fill each number with the same number of digits' ').padStart(maxDigits, 0); // Put each number in the bucket according to the units digitlettemp = nums[i][nums[i].length - 1]; arr[temp].push(nums[i]); } // Loop through each digitfor (leti = maxDigits - 2; i >= 0; I --) {// Loop through each bucketfor (let j = 0; j <= 9; j++) {
            let temp = arr[j]
            letlen = temp.length; // Put the number in the bucket into the corresponding bucket according to the current digit Iwhile (len--) {
                letstr = temp[0]; temp.shift(); arr[str[i]].push(str); }}} // Change back to the original arraylet res = [].concat.apply([], arr);
    nums.forEach((val, index) => {
        nums[index] = +res[index];
    })
    return nums
}
Copy the code