我的分析是爲了確定解決此任務的最佳排序算法是否正確？

這是一個面試問題，我想知道我的分析是否正確：我的分析是爲了確定解決此任務的最佳排序算法是否正確？

'magic select'函數基本上生成大小爲n的數組中的'mth'最小值。其任務是使用高效的算法以升序排列'm'元素。我的分析是首先使用「魔法選擇」功能來獲得「第m個」最小值。然後我使用了一個分區函數來創建一個數據透視表，以獲得左側的所有較小元素。在那之後，我覺得鬥式排序應該能夠完成有效排序左側任務的任務。

我只是想知道這是排序'm'最小元素的最好方法。我也看到了在這裏使用快速排序的可能性。但是，我認爲避免基於比較的排序可能導致O（n）。是否也可以使用基數排序或堆排序（O（nlogn））？如果我沒有以最好的方式做到這一點，那麼這可能是實現這一目標的最佳途徑？數組是我被允許使用的數據結構。

非常感謝！

來源

2013-10-28 acc_so

你能詳細點嗎？ oracle的速度有多快？甲骨文每次總是繞着相同的位置轉動，還是可以控制？ – templatetypedef

我不太確定我明白你的意思是由甲骨文。然而，爲這個問題增加一點點：這是一個關於算法的問題。 'm'可以是用戶定義的，m in的範圍是（0..n-1），其中n是數組的大小。 –

我使用「oracle」來引用你的「魔法選擇」對象。你知道使用「魔術選擇」對象的運行時間嗎？ – templatetypedef

我敢肯定，你不能做任何比任何標準算法更好的選擇按排序順序從數組中選出k個最低元素的算法。你的「魔術機器」的時間複雜度是O（n），這與你從標準選擇算法（如中位數算法或快速選擇）中獲得的時間複雜度相同。

因此，您的方法看起來非常合理。我懷疑你可以漸進地做得更好。

希望這會有所幫助！

來源

2013-10-29 02:41:07 templatetypedef

非常感謝您的關注！ –

我的分析是爲了確定解決此任務的最佳排序算法是否正確？

回答

相關問題