matlab中的快速选择代码

Question

让我们考虑以下伪代码

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

我在matlab中写了下面的代码

function []=Quickselect(A,k);
% A-unsorted array
%k-we  want to return kth largest element
% let r be chosen uniformly at random in the range 1 to length(A)
i=1; %initialize index
j=1; %initialize index
n=length(A);%length of array
r=floor(1+(n-1)*rand);%random index
pivot=A(r);  % choose pivot  as  A(r);
A1=zeros(1,n);  %create additional  arrays
A2=zeros(1,n);%create additional  arrays
for m=1:n
    if A(m)<k
      A1(i)=A(m);
      i=i+1;
    else if A(m)>k
      A2(j)=A(m);
      j=j+1;
        end
    end
end
if k <= numel(A1)
  return Quickselect(A1,k);

    else if k > (length(A) - length(A2))
   return Quickselect(A2, k - (length(A) - length(A2)));
        else 
        return pivot;
        end
end
end

>> A=[2 1 4 3 6 5 7 9 8 10 11 13 21 12];
>> Quickselect(A,3)
Error: File: Quickselect.m Line: 23 Column: 10
Unexpected MATLAB expression.

我不明白错误的原因，我不能在 Matlab 中使用递归属性吗？提前致谢

Answer 1

这不是递归问题，只是 Matlab 语法错误。

在Matlab中，return不会强制变量的return，只是让函数停止并退出。如果你想 return 你的函数应该以以下内容开头：

function [outvar]=Quickselect(A,k);

每次你有一个

return pivot;

或

return Quickselect(A1,k);

你应该修改它

outvar=pivot; % or outvar=Quickselect(A1,k);
return;

Answer 2

好的，这是您的代码的问题所在。我已经评论过将 pivot 替换为 k，但在更仔细地查看代码后，我发现了更多错误。 @AnderBiguri 已经确定了几个问题，为了完整起见，我也会在这里提及这些问题。

function []=Quickselect(A,k);

正如 Ander 提到的，您需要 return 值。我打算直接使用pivot。函数声明后不需要 ;。您实际上是在创建一个空白的第一行。

function pivot = Quickselect(A,k)

你让我对评论感到困惑：

% A-unsorted array
%k-we  want to return kth largest element
% let r be chosen uniformly at random in the range 1 to length(A)

你给出的伪代码实际上找到了第k个最小的元素。在列表 [1, 2, 3, 4, 5] 中，1 将是最小的元素，2 将是第二小的元素，而 5 将是第五小的元素。

i=1; %initialize index
j=1; %initialize index
n=length(A);%length of array
r=floor(1+(n-1)*rand);%random index

我不知道你为什么不在这里使用 randi。您的操作方式实际上并没有错，但是 randi.

更清晰，更简洁

r=randi(n);     % random index

注意这里的 % create additional arrays 部分：

pivot=A(r);     % choose pivot as A(r);
A1=zeros(1,n);  % create additional arrays
A2=zeros(1,n);  % create additional arrays

这些数组创建时的大小与 A 相同，并且始终与 A 的大小相同。 Ander 在他的评论中提到了这一点，稍后将变得非常重要。

现在 for 循环：

for m=1:n
    if A(m)<k

你的伪代码说：

    if A[i] < pivot then

pivot 是被选为基准的元素的值，您正试图将 A 分成两个列表：一个元素小于基准，另一个元素大于基准支点。 k 是您要查找其值的元素的 index。伪代码正确使用了pivot，所以你的代码应该是：

  if A(m)<pivot

A(m)>k也是如此。应该是A(m)>pivot。另外，在 Matlab 中，关键字是 elseif，没有 space。我有点偏离了对出现的个别行进行评论的方法，但我想让下一节不被打断以指出其他内容。

      A1(i)=A(m);
      i=i+1;
    else if A(m)>k
      A2(j)=A(m);
      j=j+1;
        end
    end
end

首先看到那个 end？它结束了什么？最好查看整个代码，但最后一个 end 结束了 for 循环。倒数第二个 end 结束 if-elsif。第一个 end 是错误的，应该删除。事实上，我很惊讶 Ander 没有提到这一点，但如果你正确地缩进了你的代码，你就永远不会产生这个错误。事实上，出于这个原因以及可读性，您的整个代码应该 一致地 重新缩进。 for 循环部分应如下所示：

   for m=1:n
      if A(m)<pivot
         A1(i)=A(m);
         i=i+1;
      elseif A(m)>pivot
         A2(j)=A(m);
         j=j+1;
      end
   end

现在很明显 ends 有哪些块，我们需要多少块。

您代码中的下一行是：

if k <= numel(A1)

这是我在上面提到的 Ander 评论中提到的错误。 numel(A1) 将始终等于 numel(A)，因为这是您创建数组的方式。因此，k 将总是小于或等于输入数组的大小。（好吧，它应该是，但是在伪代码或您的代码中没有明确检查它，但是哦好吧。）

那么我们从哪里得到实际添加到A1中的元素数量呢？好吧，我们回到那个 for 循环，我们使用 i 作为要添加到 A1 和 next 元素的索引和 j 作为要添加到 A2 的下一个元素的索引。这意味着 A1 的有效长度是 i-1 而 A2 的有效长度是 j-1。所以你的 if 语句应该是：

   if k <= (i-1)

接下来我们有：

  return Quickselect(A1,k);

Ander Biguri 也提到了这个。 Matlab 不会 return 以这种方式取值；您只需设置函数声明中定义的 return 变量的值。我使用了 pivot，所以我们从对 Quickselect 的递归调用中获取值 returned 并将其分配给我们的 pivot 副本。当函数结束时，此变量的值自动变为 return 值。

现在是传递给递归调用的参数。我已经说过 numel(A1) == numel(A)。因此，如果您在 A1 上递归调用 Quickselect，您实际上并没有减少数组的大小。我们只想传递 A1 的有效部分，因为我们知道它有 i-1 个有效元素，我们可以只取前 i-1 个元素，即 A1(1:i-1).

正确的行是：

      pivot = Quickselect(A1(1:i-1),k);

现在我们运行再次进入长度问题，您已经从使用 numel 切换到使用 length。就目前而言，实际上并没有错，但风格不好。

    else if k > (length(A) - length(A2))
   return Quickselect(A2, k - (length(A) - length(A2)));

这始终为零。 A 的长度减去与 A 相同长度的东西的长度为零。 A2 的有效长度为 j-1。另外，我们已经知道 A 的大小，从一开始就是 n。更正的行：

   elseif k > (n - (j-1))
      pivot = Quickselect(A2(1:j-1), k - (n - (j-1)));

所以我们到了代码的结尾：

        else 
        return pivot;
        end
end
end

如前所述，return 不设置任何 return 值，它只是来自函数的 returns。因为无论如何我们都在函数的末尾，所以没有必要 return。再一次，正确的缩进会告诉你这里还有一个额外的 end。我们需要一个用于 if-elseif 块，一个用于结束函数本身，但第三个是无关紧要的。

如果您进行这些更改，您将拥有一个有效的快速选择功能。

matlab中的快速选择代码

quickselect code in matlab

matlab

tail-recursion