排序算法复杂度分析

问题

分析常见排序算法的时间复杂度与空间复杂度，理解各算法的适用场景。

解答

复杂度对比表

算法	最好时间	最坏时间	平均时间	空间	稳定性
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n²)	O(n log n)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定

冒泡排序

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

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

function heapify(arr, size, root) {
  let largest = root;
  const left = 2 * root + 1;
  const right = 2 * root + 2;

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

  if (largest !== root) {
    [arr[root], arr[largest]] = [arr[largest], arr[root]];
    heapify(arr, size, largest);
  }
}

关键点

O(n²) 算法：冒泡、选择、插入适合小数据量或基本有序的数据
O(n log n) 算法：归并、快排、堆排序适合大数据量
稳定性：相等元素排序后相对位置不变为稳定，归并和插入排序是稳定的
空间换时间：归并排序需要 O(n) 额外空间，但时间复杂度稳定
快排最坏情况：数组已有序时退化为 O(n²)，可用随机选择基准优化