我應該在OCaml中快速排序之前洗牌嗎？

建議我們在快速排序之前對數組進行洗牌。然而，如果我們想要快速排序列表，則首先洗牌列表將採用O(nlogn)，例如，我們爲列表中的每個項目分配一個隨機密鑰，然後合併（鍵，項目）列表。我應該在OCaml中快速排序之前洗牌嗎？

然後我的問題是：

如果我們不得不花費O(nlogn)先洗牌的名單，那有什麼OCaml中實現了快速排序名單的地步？

我們應該直接使用mergesort對吧？

來源

2013-07-17 Jackson Tale

在OP的問題：

但是，如果我們想快速排序名單，改組名單將首先取O（nlogn）

我認爲一個隨機洗牌成本只有O(n)時間，如果首先將列表轉換爲數組，然後使用Fisher–Yates shuffle，這也是Python的random.shuffle中使用的算法。

來源

2013-07-18 02:40:11

那麼，做一些基準，然後顯示結果。從理論上講，你在實踐中是正確的，合併排序會擊敗你。 –

我喜歡'轉換列表到數組，然後轉換數組，然後轉換回'想法 –

@JacksonTale相信我，我已經實現了所有合理的排序算法，包括異國情調。我已經用各種編程語言實現了其中的許多語言，包括異域和深奧的語言。我正在實際應用中實現非常專業的超快速排序算法。首先，洗牌數組將在相同的開始工作時殺死緩存一致性並增加常量。其次，快速排序是NlogN平均值，N^2最差。混洗使這種最壞情況的概率最小化，但仍然存在比NlogN差的概率。最差情況下合併排序爲NlogN。 –

我會按照你的建議使用mergesort。 Mergesort甚至比quicksort更適合功能語言。

來源

2013-07-17 23:23:27

我應該在OCaml中快速排序之前洗牌嗎？

回答

相關問題