matlab - randperm 基于什么算法？

Question

我在哪里可以找到 Matlab 的randperm函数使用的算法？是Fisher-yates（Knuth）洗牌算法还是别的什么？

Answer 1

对于早在 R2009b 的 MATLAB 版本，randperm实现如下：

function p = randperm(n)
    [ignore, p] = sort(rand(1, n));

您可以通过键入以下内容自己查看：

type randperm

基本上randperm生成n 个数字并对它们进行排序，将有序索引的结果数组p作为随机排列返回。时间复杂度最多为O ( n log n )，比Fisher-and-Yates 的 shuffle差，后者运行时间为O ( n )。

编辑：丹尼斯指出，在以后的版本中randperm运行在O ( n ) 时间，所以显然它得到了改进。但是，它是一个内置函数，因此不可能看到它的实现。