是否有这种名称？

this answer中使用的排序的名称是什么？我谷歌搜索“完美插入排序”，但没有找到任何东西。下面是该答案的代码：是否有这种名称？

#this is O(n) instead of O(n log n) or worse 
sub perfect_insert_sort { 
    my $h = shift; 
    my @k; 
    for my $k (keys %$h) { 
     $k[$h->{$k}{order}] = $k; 
    } 
    return @k; 
}

来源

2010-09-07 One Handed Pete

这是怎么回事？这只是一个“重新排序”。真正的排序发生在“订单”字段被填充时。 – Arkadiy 2010-09-07 12:50:35

@Arkadiy它是一种排序，因为顺序是单调函数的结果。你可能会说你不能对一组正整数（它正在做什么）进行排序。它只是一个特殊情况下的桶排序（由于数据是如何创建的，我们知道它是连续的，从0开始，没有重复或跳过，因此是完美的前缀）。 – 2010-09-07 13:00:05

请通过显示'$ h'的内容来澄清您的答案。否则，这是将某个置换应用于数组的更一般情况。 – MAK 2010-09-08 19:48:09

我想我可能应该命名为perfect_bucket_sort而不是perfect_insertion_sort。

来源

2010-09-07 12:50:04

它仍然没有执行任何排序。请参阅[我更新的答案]（http://stackoverflow.com/questions/3658761/is-there-a-name-for-this-sort/3661108#3661108）为什么。排序意味着订单的确定。这不是确定顺序，而是重新构建顺序。 – 2010-09-08 19:11:57

@Robert P'perl -MList :: Util = shuffle -le'$ a [$ _] = $ _ for shuffle 0 .. 9; @ a''的打印与'perl -MList :: Util = shuffle -le'打印类似{$ a <=> $ b} shuffle 0 .. 9''第一种是显着更快（因为我们知道关于我们正在分类的价值的东西，并且可以作弊）。回去重读那个维基百科页面。 – 2010-09-08 20:43:15

-1

我认为这不过是一种插入排序。

来源

2010-09-07 12:49:34 user441425

不，[[插入排序]]（http://en.wikipedia.org/wiki/Insertion_sort）是不同的（请参阅我的答案中的链接和链接）。我只是懒得去找正确的名字，所以我在开始时就投入了完美，并称之为完成。 – 2010-09-07 12:52:36

这不是插入排序，实际上它甚至不是比较排序，因为理论上的最低界限是O（nlogn）。

所以它可能是斗式排序;也注意到没有比较:)

来源

2010-09-07 12:52:03

这不是一种真正的排序。它实际上主要是一个map或一个转换。这是他们拥有的数据结构的一个例子：

my $hash = { 
    foo => { order => 3 }, 
    bar => { order => 20 }, 
    baz => { order => 66 }, 
};

它只是'order'到数组元素的转换。例如，如果你将这个$ hash传递给perfect_insert_sort，它将返回一个67元素的数组，其中有三个项目（一个在索引3，一个在20，一个在66），其余的都是undef，并且完全是未分类的订购。

没有关于该功能的任何类型的任何排序。如果有是在其他答案中进行的任何排序，则在之前发生该函数被调用。

@downvoter：

而且看对方的回答中，排序发生在插入时间。这个组件可能被认为是一种排序。然而，这个子程序不会创建这个顺序 - 它只是重新构建它。

看一看的classical definition为一种：

输出是在非递减顺序（每个元素是根据期望的总时间比该前一元素不小于）

的输出是一个输入的排列或重新排序。

第2部分肯定会得到满足：哈希结构转换为正在进行的列表。但是，第1部分并不满意。没有确定订单的情况。订单在插入期间已经预先确定。如果这是一个“排序”，那么下面也将是一个排序：

my @data = ... ; my $index = -1; my %stored = map { ++$index; $_ => { order => $index } } @data; my @remade_data; @remade_data[(map { $stored{$_}{order} } keys %stored)] = keys %stored;

正如你所看到的，没有排序的代码该块，仅仅改造正在进行。

来源

2010-09-07 17:32:18

那么你称之为基数排序，计数排序和桶排序？它们都是在该页面上命名的排序（并且算法可以是一个桶排序或一个计数排序，具体取决于您的看法）。实际上，当键被插入到散列**中时，确实将键**排序，而不是通过它们的值。如果你阅读[有问题的代码]（http://stackoverflow.com/questions/3638690/iterating-hash-based-on-the-insertion-order/3638696#3638696），你会看到这种排序是在插入顺序，而不是键的值。就Perl 5的排序而言，它将是'sort {$ h {$ a} {order} <=> $ h {$ b} {order}}''。 – 2010-09-08 19:47:56

是否有这种名称？

回答

相关问题