Bubble sort

Train of thought

You need to traverse Length-1

Each traversal is compared from the back to the front, with adjacent pairs comparing the size and the small ones floating forward O(n^2^).

function bubbleSort(target) { let temp = null for(let i = 0; i < target.length - 1; i++) { for(let j = target.length - 1; j > i; j--) { if (target[j] < target[j - 1]) { temp = target[j] target[j] = target[j - 1] target[j - 1] = temp } } Console. log(' first ${I + 1} sort ')} return target} console.log(bubbleSort([23, 32, 5, 72, 12, 1]))Copy the code

Disadvantages:

When the target object is already sorted data

You also need to iterate multiple times

console.log(bubbleSort([1, 2, 3, 4, 5, 6]))
Copy the code

To optimize the

Define a Boolean value

At the end of each iteration, the Boolean value is changed if there is a position switch. At the end of each iteration, the Boolean value is determined if it has changed and the next iteration continues. If it has not changed, the next iteration exits

function bubbleSort(target) { let temp = null for(let i = 0; i < target.length - 1; i++) { let flag = false for(let j = target.length - 1; j > i; j--) { if (target[j] < target[j - 1]) { temp = target[j] target[j] = target[j - 1] target[j - 1] = temp flag = true } } Console. log(' order ${I + 1} ') if (! flag) break } return target } console.log(bubbleSort([1, 2, 3, 4, 5, 6]))Copy the code

Selection sort

Traverse Length – 1 times

Start from left to right, and swap the minimum with the first element of the current iteration O(n^2^).

function selctionSort(target) {
    for (let i = 0; i < target.length - 1; i++) {
        let min = target[i]
        let minIndex = i

        for (let j = i + 1; j < target.length; j++) {
            if (target[j] < min) {
                min = target[j]
                minIndex = j
            }
        }

        console.log(`第${i + 1}次循环`, target)
        if (minIndex === i) continue
        target[minIndex] = target[i]
        target[i] = min
    }

    return target
}

console.log(selctionSort([23, 32, 5, 72, 12, 1]))
console.log(selctionSort([1, 2, 3, 4, 5, 6])) 
Copy the code

Insertion sort

Traverse Length – 1 times

I’m going to start with I plus one, and I’m going to go two by two, O of n2.

function insertionSort(target) { let temp for (let i = 0; i < target.length - 1; i++) { for (let j = i + 1; j > 0; j--) { if (target[j] < target[j - 1]) { temp = target[j - 1] target[j - 1] = target[j] target[j] = temp } else { // If not less than the sorted maximum value // exit each iteration, Log (' ${I + 1} loop ', target)} return target} console.log(insertionSort([23, 32, 5, 72, 12, 1]))Copy the code

Quick sort

/** Target Target array to sort l Start item to sort r end item to sort */ function quickSort(target, l, r) {if (l >= r) return let I = l; let j = r; let key = target[l]; While (I < j) {while (I < j && target[j] >= key); if (i < j) { target[i] = target[j]; i++; } while (I < j && target[I] < key)// find the first value greater than key I ++; if (i < j) { target[j] = target[i]; j--; } } //i == j target[i] = key; quickSort(target, l, i - 1); // Recursively call quickSort(target, I + 1, r); Return target} console.log(quickSort([23, 32, 5, 72, 12, 1, 2], 0, 5)) console.log(quickSort([23, 32, 5, 72, 12, 1, 4, 5))Copy the code

Post to recommend

  • Encapsulate a simple WebSocket library
  • Note: Vue often meet questions summary and analysis
  • Proxy is an alternative to Object. DefineProperty in Vue3.0
  • Vue 3.0 – First experience 1
  • Figure out a prototype, a prototype object, a prototype chain
  • Promise Principles = Build a Promise from 0 to 1

[Notes are not easy, if it is helpful to you, please like, thank you]