如果我必須對陣列進行排序，并且必須在冒泡排序和雞尾酒排序之間進行選擇，那么使用雞尾酒排序是否總是更好，因為它有利于更小和更大的元素？如果不是，我應該如何決定使用哪種演算法？
uj5u.com熱心網友回復：
使用雞尾酒排序總是更好嗎
不，反例是 [9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8]
冒泡排序將需要兩次將 10 和 9 移動到它們的最終位置，并且在第三次通過時，它將看到陣列已排序并退出（如果實施了此優化）。
Cocktail Sort 將在第一次向前傳遞中將 10 移動到其最終位置，然后將執行向后傳遞，其中 0 被移動到其最終位置。在下一次向前傳遞中，9 被移動（進一步）到它的最終位置，然后向后傳遞，沒有做任何事情，因此演算法可以退出。
所以冒泡排序進行了 3 次傳球和雞尾酒 4 次傳球（2 向前 2 向后）。
一個更極端的例子是 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]
冒泡排序需要 10 或 11 次對陣列進行排序，而雞尾酒排序只需要 3 次。
對于隨機陣列，預計 Cocktail 會更快一些（或者更好：不那么慢）。如維基百科所述：
雖然它通過更快地將專案移動到串列的開頭來改進冒泡排序，但它只提供了邊際性能改進。
...和：
它可以實作比標準冒泡排序稍好的性能。這樣做的原因是冒泡排序僅在一個方向上通過串列，因此每次迭代只能將專案向后移動一步。
你問：
如果不是，我應該如何決定使用哪種演算法？
差異并不顯著。它在某些類別的輸入中表現良好。例如，上面的維基百科文章提到：
如果每個元素的位置與其將要到達的位置最多相差 ?? (?? ≥ 1)，則雞尾酒調酒器排序的復雜性變為 O(????)。
但是如果你的陣列是完全隨機的，沒有這些特征，并且可以變大，那么不要選擇這些劣質排序演算法中的任何一種。請參閱Wikipedia 上的基于比較的排序演算法串列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/419810.html
標籤：
上一篇：前綴到后綴Java