当前位置：首页 > JavaScript

js实现复杂度n的排序

2026-01-31 11:40:42JavaScript

时间复杂度为 O(n) 的排序算法

在 JavaScript 中实现时间复杂度为 O(n) 的排序算法，通常需要满足特定条件（如数据范围有限或具有特定结构）。以下是几种常见的线性时间复杂度排序方法：

计数排序（Counting Sort）

适用于整数且范围较小的数据排序。

function countingSort(arr) {
  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const count = Array(max - min + 1).fill(0);
  const output = Array(arr.length);

  // 统计每个元素的出现次数
  for (let num of arr) {
    count[num - min]++;
  }

  // 计算累加位置
  for (let i = 1; i < count.length; i++) {
    count[i] += count[i - 1];
  }

  // 反向填充结果数组（保证稳定性）
  for (let i = arr.length - 1; i >= 0; i--) {
    const num = arr[i];
    output[count[num - min] - 1] = num;
    count[num - min]--;
  }

  return output;
}

条件要求：

数据为整数且范围 max - min 不宜过大（否则空间复杂度高）。

桶排序（Bucket Sort）

适用于数据均匀分布的场景。

function bucketSort(arr, bucketSize = 5) {
  if (arr.length === 0) return arr;

  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const bucketCount = Math.floor((max - min) / bucketSize) + 1;
  const buckets = Array(bucketCount).fill().map(() => []);

  // 数据分桶
  for (let num of arr) {
    const bucketIdx = Math.floor((num - min) / bucketSize);
    buckets[bucketIdx].push(num);
  }

  // 对每个桶排序（可选用插入排序等）
  const result = [];
  for (let bucket of buckets) {
    bucket.sort((a, b) => a - b);
    result.push(...bucket);
  }

  return result;
}

条件要求：

数据分布均匀，桶数量合理。

基数排序（Radix Sort）

适用于整数或字符串的字典序排序。

function radixSort(arr) {
  const max = Math.max(...arr).toString().length;
  for (let digit = 0; digit < max; digit++) {
    const buckets = Array(10).fill().map(() => []);
    for (let num of arr) {
      const str = num.toString().padStart(max, '0');
      const radix = parseInt(str[max - 1 - digit]) || 0;
      buckets[radix].push(num);
    }
    arr = buckets.flat();
  }
  return arr;
}

条件要求：

js实现复杂度n的排序