当前位置：首页 > JavaScript

js实现复杂度n的排序

2026-03-02 02:57:29JavaScript

实现复杂度为 O(n) 的排序算法

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

计数排序（Counting Sort）

计数排序适用于整数且范围较小的数据集。核心思想是通过统计每个元素的出现次数，然后按顺序输出。

function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  const output = [];

  for (const num of arr) {
    count[num]++;
  }

  for (let i = 0; i < count.length; i++) {
    while (count[i] > 0) {
      output.push(i);
      count[i]--;
    }
  }

  return output;
}

桶排序（Bucket Sort）

桶排序将数据分到有限数量的桶中，每个桶单独排序（通常使用其他排序算法），最后合并结果。当数据分布均匀时，时间复杂度接近 O(n)。

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

  for (const num of arr) {
    const bucketIndex = Math.floor((num - min) / bucketSize);
    buckets[bucketIndex].push(num);
  }

  const sorted = [];
  for (const bucket of buckets) {
    bucket.sort((a, b) => a - b);
    sorted.push(...bucket);
  }

  return sorted;
}

基数排序（Radix Sort）

基数排序按数字的每一位进行排序，从最低位到最高位。适用于整数或固定长度的字符串排序。

function radixSort(arr) {
  const maxDigits = Math.max(...arr).toString().length;
  for (let i = 0; i < maxDigits; i++) {
    const buckets = Array.from({ length: 10 }, () => []);
    for (const num of arr) {
      const digit = getDigit(num, i);
      buckets[digit].push(num);
    }
    arr = buckets.flat();
  }
  return arr;
}

function getDigit(num, place) {
  return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}