Three basic sorting algorithms

1. Bubble sort

The outer loop determines the final point: end decreases from arr. Length-1 to 1

The inner loop traverses from 0 to end-1, with the larger ones switched back

Each inner loop determines a final position

• Time complexity: O(n²)
• Space complexity: O(1)
• stable

function bubbleSort(arr) {
  if(! arr || arr.length <2) {
    return
  }
  for (let end = arr.length - 1; end > 0; end--) {
    for (let i = 0; i < end; i++) {
      if (arr[i] > arr[i + 1]) {
        exchange(arr, i, i + 1)}}}}Copy the code

2. Selection sort

The outer loop specifies the end point, from 0 to arr. Length-2

The inner layer loops from the outer pointer to arr. Length-1, finding the smallest element’s subscript and swapping with the outer pointer’s anchor

Each inner loop determines a final position

• Time complexity: O(n²)
• Space complexity: O(1)
• stable

function selectSort(arr) {
  if(! arr || arr.length <2) {
    return
  }
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i
    for (let j = i + 1; j < arr.length; j++) {
      minIndex = arr[j] < arr[minIndex] ? j : minIndex
    }
    if(minIndex ! == i) { exchange(arr, i, minIndex) } } }Copy the code

3. Insert sort

The outer loop is sorted before the subscript

The inner loop traverses forward from the outer index. If it is small, it switches forward. Otherwise, it jumps out of the inner loop

If the array is basically ordered, the time can be order n.

• Time complexity: O(n²)
• Space complexity: O(1)
• stable

function insertSort(arr) {
  if(! arr || arr.length <2) {
    return
  }
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0; j--) {
      if (arr[j] < arr[j - 1]) {
        exchange(arr, j, j - 1)}else {
        // There is no need to compare since the previous order is already in order
        break}}}}Copy the code

Two, two advanced sort

1. Merge sort

Recursive time complexity analysis: T(n) = aT(n/b) + O(n^d)

• log(b,a) > d ==> O(nlog(b,a))
• log(b,a) = d ==> O(n^dlgn)
• log(b,a) < d ==> O(n^d)

Use recursion, similar to the sequential traversal process of binary tree (recursion, divide and conquer: the process of dividing the original problem into smaller scale merge)

Divide the array from the middle into two parts, first sort the two parts recursively, then merge the two ordered arrays (auxiliary arrays are required, but due to the particularity of javascript arrays, auxiliary arrays can not be used)

T(n) = 2T(n/2) + O(n) : A = b = 2, d = log(b,a) = 1

• Time complexity: O(NLGN)
• Space complexity: O(n)
• stable

function sort(arr) {
  if(! arr || arr.length <2) {
    return
  }
  / / recursion
  mergeSort(arr, 0, arr.length - 1)}function mergeSort(arr, left, right) {
  // If there is only one number in the interval, no sorting is required
  if (left === right) {
    return
  }
  let mid = left + Math.floor((right - left) / 2)
  // Recurse to the left
  mergeSort(arr, left, mid)
  // Recursive row to the right
  mergeSort(arr, mid + 1, right)
  / / merge
  merge(arr, left, mid, right)
}

// Merge two ordered arrays to make use of extra space
function merge(arr, left, mid, right) {
  const helper = []
  let i = 0
  let p1 = left
  let p2 = mid + 1
  while (p1 <= mid && p2 <= right) {
    helper[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]
  }
  // Only one of the two must be out of bounds, and only one of the two while will be executed
  while (p1 <= mid) {
    helper[i++] = arr[p1++]
  }
  while (p2 <= right) {
    helper[i++] = arr[p2++]
  }
  for (i = 0; i < helper.length; i++) {
    arr[left + i] = helper[i]
  }
}
Copy the code

2. Quicksort

Classical fast sorting: only determine the final position of one number at a time. Affected by the array situation, it may lead to the degradation of time complexity to O(n²) and space complexity to O(n).

Random quicksort: Use probability to get time complexity O(NLGN), space complexity O(LGN)

Recursion is used, similar to the sequential traversal process of binary tree

• Partition (time complexity O(n), space complexity O(1))
• Then fast-sort the left and right recursions (time complexity O(NLGN), space complexity O(LGN))

Compared to merge, it’s order NLGN, but the constant term is smaller, so it’s faster

• Time complexity: O(NLGN)
• Space complexity: O(LGN) : Each partition should record the middle position of the partition
• unstable

function sort(arr) {
  if(! arr || arr.length <2) {
    return
  }
  quickSort(arr, 0, arr.length - 1)}function quickSort(arr, left, right) {
  if (left < right) {
    // Random quicksort: select a number at random and swap with right
    exchange(arr, left + Math.floor(Math.random() * (right - left + 1)), right)
    const p = partition(arr, left, right)
    quickSort(arr, left, p[0])
    quickSort(arr, p[1], right)
  }
}

function partition(arr, left, right) {
  let less = left - 1
  let more = right + 1
  let cur = left
  while (cur < more) { // cur = more
    if (arr[cur] < arr[right]) {
      exchange(arr, ++less, cur++)
    } else if (arr[cur] > arr[right]) {
      exchange(arr, --more, cur)
    } else {
      cur++
    }
  }
  return [less, more] // =num field
}
Copy the code