0

我正在研究基数排序，但我不明白为什么基数排序中的数组访问是11N+4R+1. 以下是用 Java 编写的基数排序代码。

int n = a.length;
String[] aux = new String[n]; //N
int[] count = new int[R + 1]; //R+1

for (int i = 0; i < n; i++) { 
    count[a[i]+1]++; } //why 3N?

for (int r = 0; r < R; r++) {
    count[r + 1] += count[r]; } //3R

for (int i = 0; i < n; i++) {
    aux[count[a[i]]++] = a[i]; } //3N(?)+N+N = 5N

for (int i = 0; i < n; i++) {
    a[i] = aux[i]; }  //2N

count[a[i]+1]++;等于count[a[i]+1]=count[a[i]+1]+1;。我认为每个count[a[i]+1]都有 2N 个数组访问，所以总数是 4N。如果你看第三个 for 循环，a[i]在两边也是重复的，aux[count[a[i]]++] = a[i]但右边的只是一个数组访问。为什么要count[a[i]+1]++数到 3N？

4

0 回答 0