“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

preface

The front-end algorithm series is a record of my algorithm learning, which mainly analyzes the learning algorithm knowledge from common algorithms, data structure, algorithm thinking and common skills. It realizes deliberate practice through LeetCode platform, and practices Feynman learning method through digging gold and the output of STATION B. I will update the quality content and synchronously update it to Nuggets, B station and Github in the future, so as to record the complete process of learning algorithm. Welcome to communicate, like and collect more, let us make progress together, daydayUp 👊

Directory address: directory section

Code address: Github

Bilibili – 100 days algorithm series

I. Classification of algorithms

• Comparison class: through the comparison of elements to achieve, time complexity can not break O(nlogn)
• Non-comparison classes: There is no need to compare the size of elements

Second, algorithm complexity

Related knowledge supplement

• Time complexity: A functional relationship between the time it takes to execute code and the amount of data
• Spatial complexity: The functional relationship between the amount of space required to execute code and the amount of data
• Stability: Whether two equal data are sorted in the same order

Three, ten sorting algorithm details

Online sorting algorithm demonstration

Introduction: the implementation of the code may be slightly different, but the main idea remains the same, in order to make the code more concise out of part of the functional code

Bubble Sort

describe

Compare the two elements in turn, moving the smaller value to the front, while the larger element bubbles to the end

The illustration

code

function bubbleSort(nums) {
    let len = nums.length
    for(let i=len; i>0; i--) {
        for(let j=0; j<i-1; j++) {
            if (nums[j] > nums[j+1]) temp(nums, j, j + 1)}}}// Switch the position of the data deconstruction version
function temp(nums, i, j) {
    [nums[i], nums[j]] = [nums[j], nums[i]]
}
Copy the code

3.1 Quick Sort (Quick Sort)

describe

Pick a pivot, place greater than or equal to the pivot to the right, and less than the pivot to the left, and recurse

The illustration

code

// This function bases on the first element of the array
function quickSort(nums) {
    if (nums.length < 2) return nums
    let left = [], right = []
    while(nums.length > 1) {
        let num = nums.pop()
        if (num >= nums[0]) {
            right.push(num)
        } else {
            left.push(num)
        }
    }
    return [...quickSort(left), nums[0], ...quickSort(right)]
}
Copy the code

3.2 Selection Sort

describe

Pick the smallest element in the array at a time

The illustration

code

function selectionSort(nums) {
    let i = 0, 
        len = nums.length
    while(i < len) {
        let min = getMinIdx(nums, i)
        temp(nums, i, min)
        i++
    }
    return nums
}

// Get the smallest array
function getMinIdx(nums, i) {
    let min = 0
    for(let j=i; j < nums.length; j++) {
        if (nums[j] < nums[min]) min = j
    }
    return min
}
Copy the code

3.3 Heap Sort

describe

Heapsort refers to a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node.

The illustration

code

// TODO
var len;    // Since multiple declared functions require data length, len is set as a global variable
 
function buildMaxHeap(arr) {   // Create a big top heap
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) { heapify(arr, i); }}function heapify(arr, i) {     / / heap of adjustment
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;
 
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
 
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
 
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}
 
function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
 
function heapSort(arr) {
    buildMaxHeap(arr);
 
    for (var i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}
Copy the code

3.4 Insertion Sort

describe

Insert an unsorted array into an unsorted array, analogous to the process of playing poker

The illustration

code

/* function insertionSort(nums) { for(let i=1; i
      
        0 && num < nums[j]) j-- nums.splice(i, 1) nums.splice(j + 1, 0, num) } return nums } */
      ;>
for(let i=1; i<nums.length; i++) {
    let j = i - 1
    let num = nums[i]
    while(j >= 0 && num < nums[j]) j--
    nums.splice(i, 1)
    nums.splice(j + 1.0, num)
}
return nums
Copy the code

3.5 Shell Sort

1959 Shell invention, the first breakthrough O(N2) sorting algorithm, is an improved version of simple insertion sort. It differs from insertion sort in that it compares distant elements first. Hill sort is also called reduced increment sort.

describe

Insert an upgraded version of sort, first comparing data sets with n/2 intervals, then comparing data sets with N /2/2 intervals, and finally comparing entire arrays

The illustration

code

function shellSort(nums) {
    let len = nums.length, gap = len
    while(gap = getGap(gap)) {
        for(let i=0; i<nums.length; i++) {
            let k = i, num = nums[i]
            while(k - gap >= 0 && num < nums[k - gap]) {
                nums[k] = nums[k - gap] // *
                k = k - gap
            }
            nums[k] = num
        }
    }
}

// Get the increment
function getGap(len) {
    return Math.floor(len/2)}Copy the code

3.6 Merge Sort

describe

Classical divide-and-conquer algorithm, first divided into two heaps, sorted separately, and then combined

The illustration

code

function mergeSort(nums) {
    if (nums.length < 2) return nums
    let i = Math.floor(nums.length / 2)
    return merge(
        mergeSort(nums.slice(0, i)),
        mergeSort(nums.slice(i))
    )
}

// Merge two arrays
function merge(l, r) {
    let res = []
    while(l.length || r.length) {
        if(! l.length || l[0] > r[0]) {
            res.push(r.shift())
        } else if(! r.length || l[0] <= r[0]) {
            res.push(l.shift())
        } else {
            //}}return res
}
Copy the code

3.7 Counting Sort (Counting Sort)

describe

Storing the values of the data as subscripts in a new array and counting them, and then retrieving them, counting sort requires that the input data be integers with a defined range

The illustration

code

function countingSort(nums, max) {
    let ans = []
    let res = new Array(max + 1)
    for(let i=0; i<nums.length; i++) {
        let k = nums[i]
        res[k] = res[k] ? (res[k] + 1) : 1 
    }
    for(let i=0; i<res.length; i++) {
        while (res[i]) {
            ans.push(i)
            res[i] -= 1}}return ans
}
Copy the code

3.8 Bucket Sort

describe

Bucket sort is an updated version of counting sort. It makes use of the mapping relation of functions, and the key of efficiency lies in the determination of the mapping function. Bucket sort works by dividing the data into a finite number of buckets, assuming that the input data is evenly distributed, and sorting each Bucket separately (it is possible to use another sorting algorithm or to continue sorting using Bucket sort recursively).

The illustration

code

function bucketSort(nums) {
    const size = 10
    const [buckets, getHashMap] = HashMap(nums, size)

    for(let i=0; i<nums.length; i++) {
        let idx = getHashMap(nums[i])
        buckets[idx].push(nums[i])
    }

    nums.length = 0
    for(let i=0; i<buckets.length; i++) {
        if (buckets[i].length === 0) continue

        // Insert sort into buckets
        insertionSort(buckets[i])

        for(let j=0; j<buckets[i].length; j++) {
            nums.push(buckets[i][j])
        }
    }

    return nums
}

// Create buckets and mapping functions
function HashMap(nums, size) {
    let max = nums[0]
    let min = nums[0]
    let buckets = new Array(size)

    for(let i=1; i<nums.length; i++) {
        max = max > nums[i] ? max : nums[i]
        min = min < nums[i] ? min : nums[i]
    }
    
    for(let i=0; i<buckets.length; i++) {
        buckets[i] = []
    }

    let pivot = Math.floor((max - min) / size) + 1

    return [buckets, function(num) {
        return Math.floor(num / pivot)
    }]
}

// Insert sort
function insertionSort(nums) {
    for(let i=1; i<nums.length; i++) {
        let j = i - 1
        let num = nums[i]
        while(j > 0 && num < nums[j]) j--
        nums.splice(i, 1)
        nums.splice(j + 1.0, num)
    }
    return nums
}
Copy the code

3.9 Radix Sort

describe

Compare the ones place first, divide and regroup from 0 to 9, then compare the tens place, and then compare

Reference: Radix sort is sorted by low order and then collected; And then sort it in order, and then collect it; And so on, all the way to the highest place. Sometimes some attributes are prioritized, first by low priority, then by high priority. The final order is that the higher-priority ones come first, and the lower-priority ones come first.

The illustration

code

function radixSort(nums) {
    let digit = getMax(nums)
    for(let i=0; i<digit; i++) {
        let newNums = []
        let res = new Array(10).fill(1).map(() = > [])
        for(let j=0; j<nums.length; j++) {
            let level = getNum(nums[j], i)
            res[level].push(nums[j])
        }
        for(let k=0; k<10; k++) {
            while(res[k].length) {
                newNums.push(res[k].shift())
            }
        }
        nums = newNums
    }
    return nums
}

// Get the value of the current bit
function getNum(val, i) {
    return (val % Math.pow(10, i + 1)) / Math.pow(10, i)
}

// Get the maximum number and its bits
function getMax(nums) {
    let max = 0, digit = 0
    for(let i=1; i<nums.length; i++) {
        if (nums[i] > nums[max]) max = i
    }
    max = nums[max]
    digit = (max + ' ').length
    return digit
}
Copy the code

Fourth, front-end TOY version sorting method expansion

function setTimeOutSort(nums) {
    let res = []
    for(num of nums) {
        setTimeOut(() = > res.push(num), num)
    }
    return res
}
Copy the code

Personal notes

1. Why is the best time complexity of select sort and bubble sort different

2. Not proficient in heap sort (TODO), Hill sort and quick sort

3. The analysis of each algorithm is not written