SorryToPerson logo
返回
算法2026-04-15·8 分钟

算法知识库：排序算法实现

常见排序算法的 JavaScript/TypeScript 实现，包括快速排序、归并排序、堆排序等。

排序算法实现

1. 常见排序算法

  • 归并排序（Merge Sort）。
  • 快速排序（Quick Sort）。
  • 堆排序（Heap Sort）。
  • 插入排序、选择排序、冒泡排序。

2. 快速排序（Quick Sort）

时间复杂度: 平均 O(n log n)，最坏 O(n²)，最好 O(n log n) 空间复杂度: O(log n) (递归栈空间)

js
function quickSort(arr) {
  if (arr.length <= 1) return [...arr];
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = [];
  const equal = [];
  const right = [];

  for (const item of arr) {
    if (item < pivot) left.push(item);
    else if (item > pivot) right.push(item);
    else equal.push(item);
  }

  return [...quickSort(left), ...equal, ...quickSort(right)];
}

3. 归并排序（Merge Sort）

时间复杂度: O(n log n) 空间复杂度: O(n)

js
function mergeSort(arr) {
  if (arr.length <= 1) return [...arr];
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i), right.slice(j));
}

4. 堆排序（Heap Sort）

js
function heapSort(arr) {
  const result = [...arr];
  buildMaxHeap(result);

  for (let end = result.length - 1; end > 0; end -= 1) {
    [result[0], result[end]] = [result[end], result[0]];
    siftDown(result, 0, end);
  }

  return result;
}

function buildMaxHeap(arr) {
  const start = Math.floor(arr.length / 2) - 1;
  for (let i = start; i >= 0; i -= 1) {
    siftDown(arr, i, arr.length);
  }
}

function siftDown(arr, idx, heapSize) {
  let largest = idx;
  const left = 2 * idx + 1;
  const right = 2 * idx + 2;

  if (left < heapSize && arr[left] > arr[largest]) largest = left;
  if (right < heapSize && arr[right] > arr[largest]) largest = right;

  if (largest !== idx) {
    [arr[idx], arr[largest]] = [arr[largest], arr[idx]];
    siftDown(arr, largest, heapSize);
  }
}

5. 简单排序实现

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

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

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

6. 关键实现点

  • 快速排序在最坏情况下 O(n^2)，可通过随机化枢轴改善。
  • 归并排序稳定且时间复杂度为 O(n log n)，但需要额外空间。
  • 堆排序可实现原地排序，时间复杂度 O(n log n)。
  • 插入排序适用于近乎有序数据。
  • 选择排序和冒泡排序主要用于教学和简单场景。
算法排序JavaScript