Front knowledge

In real life, we’ve all played poker (for ourselves and our families, stay away from gambling and drugs). We pick up a card from the table one by one and insert it, in sequence, into the cards we already have, forming the result we want: bomb, straight, etc.

Insertion sort

Insert sort: In the unsorted data, scan from back to front in the sorted sequence to find the corresponding position to insert.

Data structure: array

Steps:

  1. Starting with the first element, the element is assumed to have been sorted
  2. Takes the next element and scans back to front in the sorted element sequence
  3. If the sorted element is larger than the element, the sorted element is moved backward
  4. Scan forward and repeat step 3 until you find sorted elements less than or equal to that element
  5. Inserts the element into a new location
  6. Next, repeat steps 2-5 until the sorting is complete

Time complexity

Average time complexity O(n2)O(n^{2})O(n2)

Worst time complexity O(n2)O(n^{2})O(n2)

Optimal time complexity O(n)O(n)O(n) (ascending)

graphic

For example, have an unordered array: [6, 5, 3, 1, 8, 7, 2, 4]

  • Step 1: The first element 6 is sorted by default
  • Step 2: take out the second element 5 and scan forward. If 6 > 5 is found, 6 moves back one bit. At this time, it is found that the previous scan has been finished, so 5 is put in the current position[5, 6, 3, 1, 8, 7, 2, 4]
  • Step 3: take out the third element 3 and scan forward. If 6 > 3 is found, move 6 back one bit. Continue to compare, if 5 > 3, move 5 back one bit[3, 5, 6, 1, 8, 7, 2, 4]
  • Step 4: Take out the fourth element 1 and scan forward. If 6 is > 1, move 6 back one bit and continue the comparison. If 5 is > 1, move 5 back one bit and continue the comparison. So put 6 in the current position[1, 3, 5, 6, 8, 7, 2, 4]
  • Step 5: Take out the fifth element 8, and scan forward to find that 8 > 6, the end of the scan, so the position of 8 is not moved[1, 3, 5, 6, 8, 7, 2, 4]
  • And so on until it’s all over[1, 2, 3, 4, 5, 6, 7, 8]‘

Code implementation (Typescript)

Auxiliary tools – generate random numbers

function getRandomInteger(count: number = 1, min: number = 0, max: number = 1000) :Array<number> {
  const res: Array<number> = []
  for (let i = 0; i < count; i ++ ){
    const random = Math.floor(Math.random() * (max - min) + min)
    res.push(random)
  }
  return res
}
Copy the code

One: exchange data in a timely manner

function insertSort(arr:Array<number>) :Array<number> {
  if (arr.length <= 1) return arr
  for (let i = 1; i < arr.length; i++) {
    const curValue: number = arr[i]
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] > curValue) {
        arr[j + 1] = arr[j]
        arr[j] = curValue
      }
    }
  }
  return arr
}
Copy the code

Second: record the index and update the data centrally after traversing

function insertSort(arr:Array<number>) :Array<number> {
  if (arr.length <= 1) return arr
  for (let i = 1; i < arr.length; i++) {
    const curValue: number = arr[i]
    let currentIndex: number = i // Record index
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] > curValue) {
        currentIndex = j // Update the current index position}}for (let k = i; k > currentIndex; k--) {
      arr[k] = arr[k-1]
    }
    arr[currentIndex] = curValue
  }
  return arr
}
Copy the code

test

const randoms: Array<number> = getRandomInteger(10)
console.log("Before sorting :"  + randoms) / / before ordering: 119997628740104,81,588,632,877,402
console.log("After sorting :" + insertSort(randoms)) / / sorted: 81104119402588628632740877997
Copy the code