排序

快排

平均时间复杂度 O(nlogn)，最坏情况（如数组已是有序的，且每次选边上元素作为基准）退化为 O(n^2)。空间复杂度 O(logn)。

核心思想：

定一个基准（Pivot）。
将比基准小的数放到左边，大的数放到右边（分区操作 Partition）。
对左右两边递归执行上述操作。

面试避坑指南：很多网上的教程会教下面这种“声明两个新数组 left 和 right”的写法。在严格的算法面试中，这种写法是不合格的！因为它的空间复杂度高达 O(n)，丧失了快排“原地排序（In-place）”的核心优势。

// ❌ 不推荐的写法（浪费空间，面试易挂）：
function badQuickSort(arr) {
  if (arr.length <= 1) return arr;
  return [
    ...badQuickSort(arr.slice(1).filter((item) => item < arr[0])),
    arr[0],
    ...badQuickSort(arr.slice(1).filter((item) => item >= arr[0])),
  ];
}

✅ 推荐写法：原地快排（双指针法）

这是标准的、能够应对大厂面试的原地快排实现，空间复杂度为 O(logn)。

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    // 找到分区点
    const pivotIndex = partition(arr, left, right);
    // 递归排序左半部分
    quickSort(arr, left, pivotIndex - 1);
    // 递归排序右半部分
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

// 分区函数：将数组按基准值分成两部分，并返回基准值的最终索引
function partition(arr, left, right) {
  // 通常取最右侧元素作为基准值（也可以随机取以避免最坏情况）
  const pivot = arr[right];
  let i = left; // i 指向小于基准值的区域边界

  for (let j = left; j < right; j++) {
    if (arr[j] < pivot) {
      // 发现比基准小的，就把它交换到前面去
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  // 最后把基准值换到中间的分界点
  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

归并排序

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

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;
}

冒泡排序

时间复杂度：O(n^2)。稳定排序。

核心思想：相邻元素两两比较，如果前一个比后一个大，则交换。每一轮遍历，最大的元素会像气泡一样“浮”到数组末尾。

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    // 每一轮遍历后，最后的 i 个元素已经是有序的了，无需再比
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

面试常考：如何优化冒泡排序？
优化思路 1：提前结束标志。如果某一轮遍历中，没有任何元素发生交换，说明整个数组已经完全有序，可以直接结束循环，无需继续瞎比。这能把最好情况（数组已有序）的时间复杂度降到 O(n)。

// ✅ 优化后的冒泡排序
function optimizedBubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    let hasSwapped = false; // 增加提前结束标志
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        hasSwapped = true;
      }
    }
    // 如果这一趟没有发生交换，说明已经完全有序，直接退出
    if (!hasSwapped) break;
  }
  return arr;
}

选择排序

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));

分类​

快排​

归并排序​

插入排序​

冒泡排序​

选择排序​

堆排序​

分类

快排

归并排序

插入排序

冒泡排序

选择排序

堆排序