Sorting algorithm is a very common interview question, with this, no longer afraid

1. Bubble sort

Adjacent elements are compared in pairs, and the larger numbers are sorted backwards

function bubble(arr) { let flag = false; If (arr. Length < 2) return arr; for (let i = 0; i < arr.length; i++) { flag = false; For (let j = 0; j < arr.length - 1 - i; If (arr[j] > arr[j + 1]) {const temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag = true; }} if (! flag) break; } console.log("arr", arr); return arr; } // bubble([1, 4, 3, 4, 5, 6, 3, 2, 21, 2]);Copy the code

2. Insert sort

Take one element, compare it to all of the previous elements, and swap places as long as it’s bigger.

function insert(arr) { let len = arr.length; if (len < 2) { return arr; } let cur, pre; for (var i = 1; i < len; I ++) {// Start with 1 and end with len. pre = i - 1; while (pre >= 0 && cur < arr[pre]) { arr[pre + 1] = arr[pre]; pre--; } arr[pre + 1] = cur; } console.log("arr", arr); return arr; } // insert([1, 4, 3, 4, 5, 6, 3, 2, 21, 2]);Copy the code

3. Select sort

The smallest element is placed in the starting position, and the smallest element from the remaining unsorted array is placed after the sorted one. Place the minimum value after the sorted array each time you find it

function select(arr) { let len = arr.length; let minIndex, temp; for (let i = 0; i < arr.length - 1; i++) { minIndex = i; // define the smallest element index for (let j = I + 1; j < arr.length; j++) { if (arr[minIndex] > arr[j]) { minIndex = j; Temp = arr[I]; temp = arr[I]; temp = arr[I]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } console.log(arr); return arr; } // select([1, 4, 3, 4, 5, 6, 3, 2, 21, 2]);Copy the code

4. Merge sort

  • Divide-and-conquer recursively deals with subproblems and then merges
  • First, sort the array recursively by dividing it into two parts
Function mergeSort(arr) {function mergeSort(left, right) {const result = []; Let I = 0, // initialize I,j = 0; // If both I and j are less than the corresponding array length, While (I < left.length &&j < right.length) {if (left[I] < right[j]) {result.push(left[I ++]);  } else { result.push(right[j++]); } } while (i < left.length) { result.push(left[i++]); } while (j < right.length) { result.push(right[j++]); } return result; } function sort(arr) {if (arr. Length === 1) return arr; const middle = Math.floor(arr.length / 2); const left = arr.slice(0, middle); const right = arr.slice(middle, arr.length); Merge (mergeSort(left), mergeSort(right)); } return sort(arr); }Copy the code

5. Quicksort

According to a datum, the number smaller than the datum is placed on the left and the number larger is placed on the right. By this rule, recurse to the left and right of two arrays

Function quick(arr) {if (arr. Length <= 1) return arr; const baseIndex = Math.floor(arr.length >> 1); Const base = arr.splice(baseIndex, 1)[0]; Const left = [], right = []; const left = [], right = []; for (let i = 0; i < arr.length; i++) { if (arr[i] > base) { right.push(arr[i]); } else { left.push(arr[i]); } } return quick(left).concat([base], quick(right)); Arr. Length <=1} let result = quick(arr); return result; } let result = quickSort([1, 4, 3, 4, 5, 6, 3, 2, 21, 2]); console.log(result, "result");Copy the code

6. The heap sort

  • A heap is a special kind of tree that satisfies two things:
  • The heap is a complete binary tree
  • The value of each node in the heap must be greater than or equal to (or less than or equal to) the value of each node in its child tree
  • If the heap is represented as an array, given the subscript I of A node (I starts at 1), its parent must be A[I / 2], its left child A[2i], and its right child A[2i + 1].
function heapSort(arr) { buildTop(arr, arr.length - 1); let size = arr.length - 1; for (let i = size; i > 1; i--) { swap(arr, i, 1); size--; heapify(arr, size, 1); } return arr; Function buildTop(arr, size) {for (let I = math.floor (size / 2); i >= 1; i--) { heapify(arr, size, i); }} function heapify(arr, size, I) {while (true) {let maxIndex = I; if (2 * i <= size && arr[i] < arr[i * 2]) { maxIndex = i * 2; } if (2 * i + 1 <= size && arr[maxIndex] < arr[i * 2 + 1]) { maxIndex = i * 2 + 1; } if (maxIndex === i) { break; } swap(arr, maxIndex, i); i = maxIndex; Function swap(arr, I, j) {let temp = arr[I]; arr[i] = arr[j]; arr[j] = temp; } // let result = heapSort([1, 4, 3, 4, 5, 6, 3, 2, 21, 2]); // console.log(result, "result");Copy the code

Time and space complexity and stability comparison of six sorting algorithms