当前位置：首页 > JavaScript

js实现复杂度n的排序

2026-04-05 03:48:32JavaScript

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

在 JavaScript 中，实现时间复杂度为 O(n) 的排序算法通常需要满足特定条件，例如数据范围有限或分布均匀。以下是几种常见的 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;
}

桶排序（Bucket Sort）

桶排序适用于数据均匀分布的场景。将数据分到多个桶中，对每个桶单独排序后合并。

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

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

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

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

    return sortedArr;
}

基数排序（Radix Sort）

基数排序适用于整数或字符串排序，按位进行比较。

js实现复杂度n的排序

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

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