c++ - O(n) 排序算法

Question

这是一个非常可怕的排序算法，它只适用于从 0 到 size 的整数。我不会对大量数据或其中包含大量数据的数据使用这样的算法，因为它需要太多内存。考虑一下，这个算法在技术上不会在 O(n) 时间内运行吗？

谢谢

#include <iostream>
#define size 33

int main(){

    int b[size];

    int a[size] = {1,6,32,9,3,7,4,22,5,2,1,0};

    for (int n=0; n<size; n++) b[n] = 0;

    for (int n=0; n<size; n++){
        if (size <= a[n]) throw std::logic_error("error");
        b[a[n]]++;
    }

    int x = 0;
    for (int n=0; n<size; n++){
        for (int t=0; t<b[n]; t++){
            a[x] = n;
            x++;
        }
    }

    for (int n=0; n<size; n++) printf("%d ",a[n]);
}

Answer 1

您正在显示 radix sort 的变体.连同 bucket sort ，这些算法是不基于比较的排序的主要示例，可以提供比 O(n logn) 更好的复杂性。

但是请注意，您的实现实际上是 O(n + size)。