這種情況下最好的排序算法是什麼？

myarray = empty 
n = 10000 
range = 1000 
loop 1 to n { 
    x = random number between 1 and range 
    if x not in myarray { 
     add x to myarray 
     sort myarray 
     do something 
    } 
}

我認爲插入排序，但那需要元素轉移。快速排序在已排序的列表上會很糟糕。我現在能想到的最好的是Min Heap。有一些鮮爲人知的排序算法更適合這種情況嗎？它在C++的STL中嗎？這種情況下最好的排序算法是什麼？

來源

2012-01-20 user1161604

大多數快速排序實現在已排序的列表上很快。 std :: sort是爲大致均勻分佈的數據而設計的，就是你如何擁有它。 –

爲什麼你甚至在這裏排序？這種情況不需要重複分類。你要添加元素，如果它不存在，只需在該循環之後對其進行排序。 – King

@King我的錯誤，我將添加一個做某事的行，所以我需要在每次迭代後對其進行排序。 – user1161604

您正在尋找std::set。它會在插入時對事物進行排序，併爲您提供快速的「不在」操作。

來源

2012-01-20 22:58:03

最好的選擇是根本不排序數組，然後等到排序結束。在一個數組中重複排序將會很昂貴，因爲您將不得不通過一種方式或另一種方式切換元素。

既然你感興趣的操作

插入元素
檢查元素是否有
保持有序

你應該考慮尋找到一個不同的結構一個數組，可能是二叉搜索樹，它支持快速（O（log n））插入，並可用於檢索排序的順序。

希望這會有所幫助！

來源

2012-01-20 22:58:19 templatetypedef

的最好的選擇當你知道你正在排序的數字將永遠是0和max_value之間是Counting sort，具有無法超越的複雜性：O(n)。

來源

2012-01-20 23:02:49 juliomalegria

或甚至對於小範圍bool contains_element [範圍]，contains_element [ixd]如果idx在myarray中則爲true – NoSenseEtAl

這種情況下最好的排序算法是什麼？

回答

相關問題