Selection sort

Select sort: find the minimum subscript 0-n-1, the minimum subscript and 0 position swap. The loop determines the values of subscripts 1 and 2.

function selectSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i
    for (let j = i + 1; j < arr.length; j++) {
      minIndex = arr[minIndex] > arr[j] ? j : minIndex
    }
    let temp = arr[i]
    arr[i] = arr[minIndex]
    arr[minIndex] = temp
  }
  return arr
}
Copy the code

Bubble sort

Compare them in pairs, big ones in the back, small ones in the front. You pick the last one at a time.

 function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
      }
    }
  }
  return arr
}
Copy the code

Insertion sort

The first cycle is ordered in 0-1; In the second loop, the order in 0-2…

function insertSort(arr) {
  if (arr.length < 2) return
  for (let i = 1; i < arr.length; i++) {
    for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
      // let temp = arr[j]
      // arr[j] = arr[j + 1]
      // arr[j + 1] = temp
      swap(arr, j, j + 1)}}return arr
}
Xor operations can only be swapped between two memory regions in different locations, otherwise the swap between itself and itself becomes 0
function swap(arr, i, j) {
  arr[i] = arr[i] ^ arr[j]
  arr[j] = arr[i] ^ arr[j]
  arr[i] = arr[i] ^ arr[j]
}
Copy the code

Merge sort

Order an array l-mid and an array mid–r, and merge the two.

Core method: define an auxiliary array with two Pointers, starting from the left array and the right array respectively. Compare, put the smallest in the auxiliary array.

function mergeSort1(arr) {
  if (arr === null || arr.length < 2) return arr
  process(arr, 0, arr.length - 1)
  return arr
}
function process(arr, l, r) {
  if (l === r) return
  let mid = l + Math.floor((r - l) >> 1)
  process(arr, l, mid)
  process(arr, mid + 1, r)
  merge(arr, l, mid, r)
}
function merge(arr, l, mid, r) {
  let p1 = l,
    p2 = mid + 1
  let h = [],
    index = 0
  while (p1 <= mid && p2 <= r) {
    h[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]
  }
  while (p1 <= mid) {
    h[index++] = arr[p1++]
  }
  while (p2 <= r) {
    h[index++] = arr[p2++]
  }
  for (let i = 0; i < h.length; i++) {
    arr[l + i] = h[i]
  }
}
Copy the code

Quick sort

The idea of quicksort is to put whatever is less than a certain number on the left, whatever is larger on the right, and whatever is equal in the middle.

Here, random quicksort is introduced. Take a random number from the array, use it as the base, swap it with the last one, and put the base number at the end. The partition is smaller than or larger than a region.

  • Anything larger than this will be swapped, and the larger region will be moved forward, and the comparison will continue with the current index
  • The next step is equal,
  • If the value is smaller than, go to the next step
function quickSort3(arr) {
  if (arr.length < 2 || arr === null) return arr
  return randomProcess(arr, 0, arr.length - 1)}function randomProcess(arr, l, r) {
  if (l >= r) return
  let m = netherlandsFlag2(arr, l, r)
  randomProcess(arr, l, m.l - 1)
  randomProcess(arr, m.r + 1, r)
  return arr
}
function netherlandsFlag2(arr, l, r) {
  if (l > r) return { l: -1.r: -1 }
  if (l === r) return { l, r }
  let less = l - 1,
    more = r,
    index = l
  let random = Math.floor(Math.random() * (r - l + 1) + l)
  let m = arr[random]
  swap3(arr, random, r)
  while (index < more) {
    if (arr[index] > m) {
      swap3(arr, index, --more)
    } else if (arr[index] < m) {
      swap3(arr, ++less, index++)
    } else {
      index++
    }
  }
  swap3(arr, more, r)
  // console.log(m, arr, less, more)
  return { l: less + 1.r: more }
}
function swap3(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}
Copy the code

Heap sort

An array becomes a large root heap. Swap the top of the heap with the last value, reduce the size of the heap, and then form a large root heap, repeating the process until the heap is zero.

You can use either heapInsert or Heapify during the loop. However, the heapify method is in a loop and the event complexity is O (nlogn).

Ascending: Swap the node to be inserted when the child node is larger than the parent node, run the subscript to the parent node, and then compare it with its parent node. Up to the top of the heap.

Sinking: the parent node is compared with the child node, the child node takes the largest, the largest child node is compared with the parent node, the parent node breaks greatly, and the child node switches greatly. Place the maximum value node on the parent node and run the subscript to the maximum value node. Continue comparing until left exceeds the heap length.

function heapSort(arr) {
  if (arr === null || arr.length < 2) return arr
  for (let i = arr.length - 1; i >= 0; i--) {
    heapify(arr, i, arr.length)
  }
  let heapSize = arr.length
  swap(arr, 0, --heapSize)
  while (heapSize > 0) {
    heapify(arr, 0, heapSize)
    swap(arr, 0, --heapSize)
  }
  return arr
}
/ / up
function heapInsert(arr, index) {
  while (arr[index] > arr[Math.floor((index - 1) > >1)]) {
    swap(arr, index, Math.floor((index - 1) > >1))
    index = Math.floor((index - 1) > >1)}}/ / sink
function heapify(arr, index, heapSize) {
  let left = (index << 1) + 1
  while (left < heapSize) {
    let largest =
      left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left
    largest = arr[index] > arr[largest] ? index : largest
    if (largest === index) break
    swap(arr, index, largest)
    index = largest
    left = (index << 1) + 1}}function swap(arr, i, j) {
  let temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}
Copy the code

Stability compared with time and extra space complexity

Stability: Equal numbers remain in the same relative order after sorting

  • Time complexity O(n^2)
    • Selection sort, unstable extra space complexity O(1)
    • Bubble Sort, stable extra space complexity O(1)
    • Insert sort, stable extra space complexity O(1)
  • Time complexity O(nlogn)
    • Merge sort, (copy left stable first if equal) extra space complexity O(nlogn)
    • Quick Sort, unstable (partition small and large) Extra space complexity O(nlogn)
    • Heap Sort, unstable extra space complexity O(nlogn)
    • Hill sort, unstable

Three sort, merge more stable, fast row speed, less heap sort space

Counting sort O(n) O(M) Cardinal sort O(n)

conclusion

  • Not based on comparison sorting, strict requirements on sample data, not easy to rewrite
  • Comparison sort can be reused as long as you specify how to compare the size of two samples, right
  • The time complexity limit for comparison sorting is O(nlogn).
  • The time complexity O(nlogn), the extra space complexity is less than O(N), and stable comparison based sorting does not exist
  • Merge more stable, fast sorting speed, less heap sort space