Implement visualizations through algorithms: visualgo.net/zh/sorting to deepen understanding.

  • Basic sorting algorithm:

    • Bubble sort
    • Insertion sort
    • Selection sort

  • Advanced sorting algorithm

    • Merge sort
    • Quick sort

Bubble sort

Ideas:

Bubble sort is the process of repeatedly comparing two adjacent items, starting with the first element. If the first item is larger than the second, the two items are swapped. Vice versa. Each round of operation places the largest element of that round at the end of the array. If the length of the array is n, then by the time we do n rounds, the entire array will be in order.

implementation

function bubbleSort(arr) {
  // Cache array length
	let len = arr.length
  // The outer loop takes one value from the beginning to the end of each round and compares it with all the values in the inner loop
  for(let i = 0; i < len; i++) {
  	for(let j = 0; j < len-1; j++) {
      // If the current value is greater than the latter value, the position is switched
    	if(arr[j]> arr[j+1]) {
      	[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
      }
    }
  }
  return arr
}
Copy the code

Optimization for the first time

As the outer loop progresses, the elements at the end of the array get sorted — by the time we finish the first loop, the largest elements are at the end of the array; At the end of the second cycle, the second largest element is ranked second from the bottom of the array; By the end of the third loop, the third largest element is placed at…… By the end of the NTH loop, the last n elements of the array are already sorted

function betterBubbleSort(arr) {
    const len = arr.length  
    for(let i=0; i<len; i++) {// Notice the difference in this line, where we limit the scope of the inner loop
        for(let j=0; j<len-1-i; j++) {if(arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
            }
        }
    }
    return arr
}
Copy the code

Optimize the second time

function betterBubbleSort(arr) {
    const len = arr.length  
    
    for(let i=0; i<len; i++) {// The difference here is that we add a flag bit
        let flag = false
        for(let j=0; j<len-1-i; j++) {if(arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
                // When a swap occurs, the flag bit is modified
                flag = true}}// If no swap occurs, the array is in order
        if(flag == false)  return arr;
    }
    return arr
}
Copy the code

Selection sort

Ideas:

The keyword of selection sort is “minimum” : loop through the array of numbers, find the minimum value in the current range each time, put it in the head of the current range; Then narrow down the sorting range and repeat until the array is completely sorted

implementation

function selectSort(arr)  {
  // Cache array length
  const len = arr.length 
  // define minIndex, the index of the minimum value of the current interval
  let minIndex  
  // I is the start of the current sort interval
  for(let i = 0; i < len - 1; i++) { 
    // Initialize minIndex as the first element of the current range
    minIndex = i  
    // I and j define the upper and lower bounds of the current interval respectively. I is the left boundary and j is the right boundary
    for(let j = i; j < len; j++) {  
      // If the item at j is smaller than the current minimum, update the minimum index to j
      if(arr[j] < arr[minIndex]) {  
        minIndex = j
      }
    }
    // If the corresponding minIndex element is not the current header element, the two are swapped
    if(minIndex ! == i) { [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]] } }return arr
}
Copy the code

Insertion sort

Train of thought

The core idea of insertion sort is to “find the correct position of the element in the sequence that precedes it.” In particular, all operations of insert sort are based on the premise that the sequence before the current element is ordered. Based on this premise, work backwards to find the correct position of the current element in the previous sequence.

implementation

function insertSort(arr) {
  // Cache array length
  const len = arr.length
  // Temp is used to store the current element to be inserted
  let temp  
  // I is used to identify the index of the element being inserted each time
  for(let i = 1; i < len; i++) {// j is used to help Temp find its rightful position
    let j = i
    temp = arr[i]  
    // Determine whether the element before j is larger than temp
    while(j > 0 && arr[j-1] > temp) {
      // If so, move the element before j back one bit to make room for temp
      arr[j] = arr[j-1]   
      j--
    }
    // The final j is the correct index of temp
    arr[j] = temp
  }
  return arr
}
Copy the code

Merge sort

Train of thought

Divide and rule — divide and rule

  • Split the subproblem: Split the sorted array in half, then split each subarray in half, and repeat until each subarray has only one element.
  • Solve each subproblem: Start with the smallest subarray and merge in pairs, making sure the array is sorted each time. (By “subproblem” I mean sorting each subarray.)
  • Merge the solutions of the subproblems to get the solution of the big problem: when the array is merged to its original size, the result is a fully sorted array
function mergeSort(arr) {
    const len = arr.length
    // Handle boundary cases
    if(len <= 1) {
        return arr
    }   
    // Calculate the split point
    const mid = Math.floor(len / 2)    
    // Divide the left subarray recursively and merge it into an ordered array
    const leftArr = mergeSort(arr.slice(0, mid)) 
    // Divide the right subarray recursively and merge it into an ordered array
    const rightArr = mergeSort(arr.slice(mid,len))  
    // Merge left and right ordered arrays
    arr = mergeArr(leftArr, rightArr)  
    // Return the merged result
    return arr
}
  
function mergeArr(arr1, arr2) {  
    // Initialize two Pointers to arr1 and arr2
    let i = 0, j = 0   
    // Initialize the result array
    const res = []    
    // Cache the length of arr1
    const len1 = arr1.length  
    // Cache the length of arR2
    const len2 = arr2.length  
    // Merge two subarrays
    while(i < len1 && j < len2) {
        if(arr1[i] < arr2[j]) {
            res.push(arr1[i])
            i++
        } else {
            res.push(arr2[j])
            j++
        }
    }
    // If one of the subarrays is merged completely first, the rest of the other subarray is directly merged
    if(i<len1) {
        return res.concat(arr1.slice(i))
    } else {
        return res.concat(arr2.slice(j))
    }
}
Copy the code

Time complexity: O(nlogn)

Quick sort

Train of thought

Quicksort is basically the same as merge sort, except that it does not split up the real array and merge it into a new array. Instead, it sorts directly inside the original array.

Quicksort filters the original array into smaller and larger subarrays, and then sorts the two subarrays recursively.

Implement a

function quickSort(arr) {
  const len = arr.length
  if(len < 1) return arr
  // Select the reference point
  const lineIndex = Math.floor(len / 2)
  const lineValue = arr[lineIndex]
	const left = []
  const right = []
  
  for(let i = 0; i < len; i++) {
  	if(i ! == lineIndex) {const n = arr[i]
      if(n < lineIndex) {
      	left.push(n)
      } else {
      	right.push(n)
      }
    }
  }
  return quickSort(left).concat(
  	[lineValue],
    quickSort(right)
  )
}
Copy the code

Time complexity: O(nlogn)

Space complexity: O(n)

Realize the

// Quicksort entry
function quickSort(arr, left = 0, right = arr.length - 1) {
  // Define recursive bounds. If the array has only one element, there is no sorting necessary
  if(arr.length > 1) {
      // lineIndex indicates the index bit of the next subarray partition
      const lineIndex = partition(arr, left, right)
      // If the length of the left subarray is not less than 1, the subarray is recursively fast-sorted
      if(left < lineIndex-1) {
        // The left subarray is bounded by lineIndex-1
        quickSort(arr, left, lineIndex-1)}// If the length of the right subarray is not less than 1, the subarray is recursively fast-sorted
      if(lineIndex<right) {
        // The right subarray is bounded by lineIndex
        quickSort(arr, lineIndex, right)
      }
  }
  return arr
}
// The process of dividing left and right subarrays with reference values as the axis
function partition(arr, left, right) {
  // The base value defaults to the middle element
  let pivotValue = arr[Math.floor(left + (right-left)/2)]
  // Initialize the left and right Pointers
  let i = left
  let j = right
  // When the left and right Pointers do not exceed the bounds, the loop executes the following logic
  while(i<=j) {
      // If the left pointer points to an element less than the base value, the left pointer moves to the right
      while(arr[i] < pivotValue) {
          i++
      }
      // If the right pointer points to an element greater than the reference value, the right pointer moves to the left
      while(arr[j] > pivotValue) {
          j--
      }

      // If I <=j, it means that there is a larger element to the left or a smaller element to the right of the base value
      if(i<=j) {
          swap(arr, i, j)
          i++
          j--
      }

  }
  // Return the left pointer index as the basis for the next subarray partition
  return i
}
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]]
}
Copy the code

Time complexity: O(nlogn)

Space complexity: O(1)