快速排序中位數3運行時間

Question

我正在考慮快速排序算法，選擇分區函數中的樞軸作爲數組中三個（一致）隨機選擇項的中值。有人知道一般情況下的運行時間嗎？

Answer 1

小假設：所有元素都不相同。

有了這個假設，即使您選擇pivot作爲一個隨機元素，平均運行時間爲O（n * log n）。 最樂觀的情況也是O（n * log n）。 選擇三個隨機元素的中位數不會使平均情況更糟糕，所以它也必須是O（n * log n）。 通過查看中位數得出的結果與平均數的偏差較小。 這種快速排序的版本更不好運氣。

如果元素不必不同，請考慮一個案例，他們都是平等的。 如果你的算法仍然在O（n * log n）時間內工作，它可能會完全相同。