COUNTING_SORT - 考试伪代码算法及其工作原理

Question

我遇到了一个我不能完全理解的算法。能不能找人一起逐段分析一下？

这里是：

 1. B <- new matrix (m)
 2. for i<- 1 to m
 3.    B[i] <- 0
 4. for j <- to n
 5.    B[A[j]] <= B[A[j]] + 1
 6. k <- 1, i <-1
 7. while i<= m
 8.    if B[i] = 0 then
 9.        i<- i + 1
 10.   else 
 11.       for j <-1 to B[i]
 12.           A[k]<-i
 13.           k <- k + 1
 14.       i<- i + 1
 15.return A

我了解它的大部分内容，但不了解它的功能。第 5 行是最令人困惑的行，因为它使用假定的 A 数组（我们没有定义但我们会掩盖它）来表示 B 数组中的值。

但是，即使是对这一切的一般性解释，我也将不胜感激。

编辑：为了澄清，这正是我获得伪代码的方式。我没有更改或删除信息。

Answer 1

让我们将其与 countingsort

进行比较

void countingSort(array<int> &a, int k) {
  array<int> c(k, 0);
  for (int i = 0; i < a.length; i++)
    c[a[i]]++;
  for (int i = 1; i < k; i++)
    c[i] += c[i-1];
  array<int> b(a.length);
  for (int i = a.length-1; i >= 0; i--)
    b[--c[a[i]]] = a[i];
  a = b;
}

你的神秘台词

for j <- to n
  B[A[j]] <= B[A[j]] + 1

只是计算从 1 到 n 的值的出现次数。

 6. k <- 1, // final position in array, 1-based
    i <-1   // iterator over count of values AND the value to store.
 7. while i<= m
 8.    if B[i] = 0 then
 9.        i<- i + 1 // there are no counted values so go to next value
 10.   else 
 11.       for j <-1 to B[i] // fill with B[i] with i
 12.           A[k]<-i // put target value into final position
 13.           k <- k + 1 // update final position
 14.       i<- i + 1

仅对从 1 到 m 的值进行排序。

COUNTING_SORT - 考试伪代码算法及其工作原理

COUNTING_SORT - Exam pseudocode algorithm and how it works

algorithm

sorting

pseudocode