排序算法实现

问题

实现六种常见排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。

解答

冒泡排序

// 相邻元素两两比较，每轮将最大值冒泡到末尾
function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    // 优化：标记本轮是否发生交换
    let swapped = 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]];
        swapped = true;
      }
    }
    // 没有交换说明已经有序
    if (!swapped) break;
  }
  return arr;
}

选择排序

// 每轮选择最小元素放到已排序序列末尾
function selectionSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;
    // 找到未排序部分的最小值
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 交换到已排序序列末尾
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

插入排序

// 将未排序元素插入到已排序序列的正确位置
function insertionSort(arr) {
  const len = arr.length;
  for (let i = 1; i < len; i++) {
    const current = arr[i];
    let j = i - 1;
    // 将大于 current 的元素后移
    while (j >= 0 && arr[j] > current) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = current;
  }
  return arr;
}

快速排序

// 分治：选基准，分区，递归排序左右两部分
function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];

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

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

// 原地快排版本（更省空间）
function quickSortInPlace(arr, low = 0, high = arr.length - 1) {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSortInPlace(arr, low, pivotIndex - 1);
    quickSortInPlace(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  const pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

归并排序

// 分治：拆分成小数组，排序后合并
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)).concat(right.slice(j));
}

堆排序

// 利用最大堆，每次取出堆顶最大值
function heapSort(arr) {
  const len = arr.length;

  // 构建最大堆（从最后一个非叶子节点开始）
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
    heapify(arr, len, i);
  }

  // 依次取出堆顶元素
  for (let i = len - 1; i > 0; i--) {
    // 堆顶与末尾交换
    [arr[0], arr[i]] = [arr[i], arr[0]];
    // 重新调整堆
    heapify(arr, i, 0);
  }

  return arr;
}

// 调整以 i 为根的子树为最大堆
function heapify(arr, heapSize, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

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

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, heapSize, largest);
  }
}

测试

const arr = [64, 34, 25, 12, 22, 11, 90];

console.log(bubbleSort([...arr]));    // [11, 12, 22, 25, 34, 64, 90]
console.log(selectionSort([...arr])); // [11, 12, 22, 25, 34, 64, 90]
console.log(insertionSort([...arr])); // [11, 12, 22, 25, 34, 64, 90]
console.log(quickSort([...arr]));     // [11, 12, 22, 25, 34, 64, 90]
console.log(mergeSort([...arr]));     // [11, 12, 22, 25, 34, 64, 90]
console.log(heapSort([...arr]));      // [11, 12, 22, 25, 34, 64, 90]

关键点

算法	时间复杂度（平均）	时间复杂度（最坏）	空间复杂度	稳定性
冒泡	O(n²)	O(n²)	O(1)	稳定
选择	O(n²)	O(n²)	O(1)	不稳定
插入	O(n²)	O(n²)	O(1)	稳定
快速	O(n log n)	O(n²)	O(log n)	不稳定
归并	O(n log n)	O(n log n)	O(n)	稳定
堆	O(n log n)	O(n log n)	O(1)	不稳定

• 小数据量或基本有序时，插入排序效率高
• 快速排序平均性能最好，但最坏情况退化为 O(n²)
• 归并排序稳定且时间复杂度稳定，但需要额外空间
• 堆排序原地排序，适合内存受限场景
• 稳定性指相等元素排序后相对位置是否不变