This article documents common sorting and search algorithms in JavaScript.

The sorting

  • To arrange an array of random numbers in ascending or descending order
  • The sort in JS is passedsortmethods

search

  • Finds the index of an element in the array
  • JS search is throughindexOfmethods

Bubble sort

  • Compare all adjacent elements and swap them if the first is larger than the second.
  • After a round, the last element is guaranteed to be the largest.
  • Do n – 1 rounds to complete the sorting.

Code display:

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

Complexity analysis:

  • Time complexity: O(n^2)
  • Space complexity: O(n)

Selection sort

  • Find the smallest value in the array, select it and place it first
  • Then find the second smallest value, select it and place it second
  • And so on, perform the N-1 round

Code display:

Const arr =,3,2,1,4 [5]; function selectionSort(arr) { for (let i = 0; i < arr.length; i++) { let minIndex = i; for (let j = i; j < arr.length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex ! = i) [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]] } return arr; } selectionSort(arr);Copy the code

Complexity analysis:

  • Time complexity: O(n^2)
  • Space complexity: O(n)

Insertion sort

  • Let’s start with the second numberForward than.
  • Bigger than it isTo the rear.
  • And so on down to the last number.

Code display:

Const arr =,3,2,1,4 [5]; function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { const temp = arr[i]; let j = i; while (j > 0 && arr[j - 1] > temp) { arr[j] = arr[j - 1]; j--; } arr[j] = temp; } return arr; } insertionSort(arr);Copy the code

Complexity analysis:

  • Time complexity: O(n^2)
  • Space complexity: O(1)

Merge sort

  • Divide the array in half and recursively divide the subarrays until they are separated into individual numbers.

  • Merge the two numbers into an ordered array, and then merge the ordered arrays until all the subarrays are merged into a complete array.

Code display:

Const arr =,3,2,1,4 [5]; function mergeSort(arr) { const res = (arr) => { if (arr.length === 1) return arr; const mid = Math.floor(arr.length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid, arr.length); const orderLeft = res(left); const orderRight = res(right); const res = []; while (orderLeft.length || orderRight.length) { if (orderLeft.length && orderRight.length) { res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift()); } else if (orderLeft.length) { res.push(orderLeft.shift()); } else if (orderRight.length) { res.push(orderRight.shift()); } } return res; } const res = res(arr); res.forEach((n, i) => { arr[i] = n; }); return arr; } mergeSort(arr);Copy the code

Complexity analysis:

  • The time complexity of fractions is O(logN), the time complexity of combinations is O(n), the time complexity is O(nlogN).
  • Space complexity: O(n)

Quick sort

  • Partitioning: Randomly select a base from the array, with all elements smaller than the base placed in front of the base and elements larger than the base placed behind it.

  • Merge: Partition the subarray before and after the base recursively.

Const arr =,3,2,1,4 [5]; function quickSort(arr) { const rec = (arr) => { if (arr.length === 1) return arr; const mid = arr[0]; const left = []; const right = []; for (let i = 1; i < arr.length; i++) { if (arr[i] < mid) { left.push(arr[i]); } else { right.push(arr[i]); } } return [...rec(left), mid, ...rec(right)]; } const res = rec(arr); res.forEach((n, i) => { arr[i] = n; }); return arr; } quickSort(arr);Copy the code

Complexity analysis:

  • Recursive time O(logN), partition time O(n), total time O(nlogN)
  • Space complexity: O(n).

Sequential search

const arr = [5, 2, 1, 4, 3];
function sequentialSearch(arr, item) {
    for (let i = 0; i < arr.length; i += 1) {
        if (arr[i] === item) {
            return i;
        }
    }
    return -1;
}
sequentialSearch(arr, 3)
Copy the code

Complexity analysis:

  • Time complexity: O(n)

Binary search

  • Premise: The array is ordered
const arr = [1, 2, 3, 4, 5];

function binarySearch(arr, item) {
    let low = 0;
    let high = arr.length - 1;
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (arr[mid] < item) {
            low = mid + 1;
        } else if (arr[mid] > item) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}
binarySearch(arr, 4);
Copy the code

Complexity analysis:

  • Time complexity: O(logn)

Leetcode topic

179. Most of large Numbers

56. Consolidated intervals

/** * @param {number[][]} intervals * @return {number[][]} */ var merge = function(intervals) { if (intervals.length ===  0 || intervals.length === 1) return intervals; intervals.sort((a, b) => a[0] - b[0]); for (let i = 0; i < intervals.length - 1; i++) { const b0 = intervals[i][0]; const b1 = intervals[i][1]; const p0 = intervals[i + 1][0]; const p1 = intervals[i + 1][1]; if (b1 >= p0) intervals.splice(i--, 2, [Math.min(b0, p0), Math.max(b1, p1)]); } return intervals; };Copy the code

148. Sort linked lists

/** * @param {ListNode} head * @return {ListNode} */ var sortList = function(head) { if (! head || ! head.next) return head; let slow = head; let fast = head; let preSlow = null; while (fast && fast.next) { preSlow = slow; slow = slow.next; fast = fast.next.next; } preSlow.next = null; let l = sortList(head); let r = sortList(slow); return mergeSort(l, r); }; var mergeSort = (l1, l2) => { const dummy = new ListNode(0); let p1 = l1; let p2 = l2; let p3 = dummy; while (p1 && p2) { if (p1.val < p2.val) { p3.next = p1; p1 = p1.next; } else { p3.next = p2; p2 = p2.next; } p3 = p3.next; } if (p1) p3.next = p1; if (p2) p3.next = p2; return dummy.next; }Copy the code

Insert sort on linked lists

/** * @param {ListNode} head * @return {ListNode} */ var insertionSortList = function(head) { if (! head) return head; const dummyHead = new ListNode(0); dummyHead.next = head; let lastSorted = head, curr = head.next; while (curr) { if (lastSorted.val <= curr.val) { lastSorted = lastSorted.next; } else { let prev = dummyHead; while (prev.next.val <= curr.val) { prev = prev.next; } lastSorted.next = curr.next; curr.next = prev.next; prev.next = curr; } curr = lastSorted.next; } return dummyHead.next; }Copy the code

conclusion

Familiar with the principle of several common algorithms, as well as the linked list sorting, can better understand the sorting and linked list.