algorithm

排序算法

冒泡排序

const main = () => {
  let count = 0;
  let length = arr.length - 1;
  let pos = 0;
  for (let i = 0; i < arr.length - 1; i++) {
    let swap = false;
    for (let j = 0; j < length; j++) {
      count += 1;
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swap = true;
        pos = j;
      }
    }
    length = pos
    if (!swap) {
      break;
    }
  }
  console.log(count, arr);
};

main();

---

快速排序

const arr = [3, 7, 8, 4, 5, 1, 2, 6, 9];

const main = () => {
  quickSort(arr, 0, arr.length - 1);
  console.log(arr);
};

function quickSort(arr, left, right) {
  if (left < right) {
    let splitIndex = split(arr, left, right);
    quickSort(arr, left, splitIndex - 1);
    quickSort(arr, splitIndex + 1, right);
  }
  return arr;
}

function split(arr, left, right) {
  const temp = left;
  let index = left + 1;

  for (let i = index; i <= right; i++) {
    if (arr[i] < arr[temp]) {
      swap(arr, i, index);
      index++;
    }
  }

  swap(arr, temp, index - 1);
  return index - 1;
}

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

main();

---

插入排序

const arr = [3, 7, 8, 4, 5, 1, 2, 6, 9];

const main = () => {
  insertionSort(arr);
  console.log(arr);
};

const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let j = i;
    while (j > 0 && arr[j] < arr[j - 1]) {
      swap(arr, j, j - 1);
      j--;
    }
  }
};

const swap = (arr, i, j) => {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
};

main();

链表算法

删除链表的第 N 个节点

var removeNthFromEnd = function (head, n) {
  let newList = new ListNode(0, head);
  let first = newList;
  let second = head;
  let index = 1;

  while (second != null) {

    second = second.next;

    if (index < n) {
      index += 1;
    } else {
      if (second) {
        first = first.next;
      }
    }
  }
  first.next = first.next.next;

  return newList.next;
};

递归算法