排序

快排

平均时间复杂度 O(nlogn)，当基准数是最小数或最大数时，会达到最差情况 O(n^2)

定一个基准
比基准小的数放到左边，大的数放到右边
递归

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  return [
    ...quickSort(arr.slice(1).filter((item) => item < arr[0])),
    arr[0],
    ...quickSort(arr.slice(1).filter((item) => item >= arr[0])),
  ];
}

归并排序

递归对半分割数组，从单个元素的数组开始合并
需要一个临时数组来存放合并的数组
借助左右双指针，如果左边项比右边项小，先将其推入新数组，否则将右边项推入

function mergeSort(arr) {
  let len = arr.length;
  if (len === 1) return arr;
  let devideNum = Math.floor(len / 2);
  let arrLeft = arr.slice(0, devideNum);
  let arrRight = arr.slice(devideNum, len);
  return merge(mergeSort(arrLeft), mergeSort(arrRight));
}
function merge(arrLeft, arrRight) {
  let lp = 0; // 左指针
  let rp = 0; // 右指针
  let result = [];
  console.log("当前数组", arrLeft, arrRight);
  while (lp < arrLeft.length && rp < arrRight.length) {
    if (arrLeft[lp] < arrRight[rp]) {
      result.push(arrLeft[lp++]);
    } else {
      result.push(arrRight[rp++]);
    }
  }
  result = result.concat(arrLeft.slice(lp)).concat(arrRight.slice(rp));
  console.log(result);
  return result;
}
console.log(mergeSort(arr));

插入排序

function insertionSort(arr) {
  let len = arr.length;
  for (let i = 1; i < len; i++) {
    let j = i;
    let tmp = arr[i];
    while (j > 0 && arr[j - 1] > tmp) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = tmp;
  }
  return arr;
}

冒泡排序

function bubbleSort(arr) {
  const newArr = [...arr];
  for (let i = 0; i < newArr.length; i++) {
    for (let j = 0; j < newArr.length - 1 - i; j++) {
      if (newArr[j] > newArr[j + 1]) {
        [newArr[j], newArr[j + 1]] = [newArr[j + 1], newArr[j]];
      }
    }
  }
  return newArr;
}

如何优化？参考 https://cloud.tencent.com/developer/article/1947681

选择排序

function selectionSort(arr) {
  const newArr = [...arr];
  for (let i = 0; i < newArr.length - 1; i++) {
    let min = i;
    for (let j = i + 1; j < newArr.length; j++) {
      if (newArr[j] < newArr[min]) {
        min = j;
      }
    }
    if (min !== i) {
      [newArr[min], newArr[i]] = [newArr[i], newArr[min]];
    }
  }
  return newArr;
}

堆排序

var len;
// 建最大堆
function buildHeap(arr) {
  len = arr.length;
  for (var i = Math.floor(arr.length / 2); i >= 0; i--) {
    adjustHeap(arr, i);
  }
}
// 调整堆
function adjustHeap(arr, i) {
  var left = 2 * i + 1, // 左节点位置
    right = 2 * i + 2, // 右节点位置
    largest = i; // 最大值位置

  // 如果左节点存在并且左节点大于当前最大节点，交换位置
  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }
  // 如果右节点存在并且右节点大于当前最大节点，交换位置
  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }
  // 如果发现修改了，则交换位置，调整大顶堆
  if (largest !== i) {
    swap(arr, i, largest);
    adjustHeap(arr, largest);
  }
}
// 交换位置
function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
// 堆排序算法
function heapSort(arr) {
  buildHeap(arr); // 建堆
  for (var i = len - 1; i > 0; i--) {
    swap(arr, 0, i); // 堆顶一定是最大元素，将堆顶和尾部元素交换，最大元素就保存在尾部，并且不参与后面的调整
    len--; // 去掉这个是从大到小排序
    adjustHeap(arr, 0); // 将最大的元素进行调整，将最大的元素调整到堆顶
  }
  return arr;
}

console.log(heapSort(arr));

分类​

快排​

归并排序​

插入排序​

冒泡排序​

选择排序​

堆排序​

分类

快排

归并排序

插入排序

冒泡排序

选择排序

堆排序