基数排序（java 实现）复杂度

Question

这是我的第一个问题，希望我没有违反任何规则。我终于设法为基数排序算法编写了代码，但我想知道我是否做错了。让我这么认为的是，我的算法看起来复杂度为 O(n^3)，但基数排序是出了名的 O(k.n) 算法。是我算法的复杂度计算有误，还是我写的代码真的很糟糕？

private static void radixSort(int[] A){
    ArrayList<Integer>[] bucket = new ArrayList[10];
    int maxNumberOfDigits = 0;
    for(int number : A){
        if(numberOfDigitsIn(number) > maxNumberOfDigits) maxNumberOfDigits = numberOfDigitsIn(number);
    }
    for(int c=0; c<bucket.length; c++){
        bucket[c] = new ArrayList<Integer>();
    }
    int i = 0;
    int digit;
    int j;
    while(i < maxNumberOfDigits){
        for(j = 0; j<A.length; j++){
            digit = getDigit(A[j], i);
            bucket[digit].add(A[j]);
        }

        int index = 0;
        for(int z = 0; z<bucket.length; z++){
            for (int k=0; k<bucket[z].size(); k++){
                A[index] = bucket[z].get(k);
                index += 1;

            }
            bucket[z].clear();
        }
        i += 1;
    }
}

getDigit() 和 numberOfDigitsIn() 方法是恒定时间的。

Answer 1

    for(int z = 0; z<bucket.length; z++){
        for (int k=0; k<bucket[z].size(); k++){

这里的关键是所有桶大小的总和将等于 n，所以这些循环组合起来只需要 O(n)。 j 上的循环采用 O(n)，而 i 上的 while 循环将运行进行 maxNumberOfDigits 迭代，并且该数字代表您描述的 O(kn) 运行时间内的 k。所以总数实际上是 O(kn)。

基数排序（java 实现）复杂度

radix sort (java implementation) complexity

java

sorting

time-complexity

radix-sort