是否有這種名稱？

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

是否有這種名稱？

回答

相關問題