Quicksort pivote選擇

Question

我讀過pivot的可以是3個數字的中位數，bottom，middle和top。但是，這可能會產生溢出？如果中位數返回的值大於數組大小，會發生什麼情況？ 我假設這個選擇是通過假定它們的數組值不能超過數組的大小。 我覺得我很困惑究竟是什麼。

Answer 1

數據透視圖只是您比較其他數值的值 - 數值越低，數據左邊越高，數據越高。可以通過採用數組中的任何現有值來選擇主元。如果數組完全未排序，則選擇哪個值無關緊要。如果它有點排序，你應該從數組中間選擇一個值。

更新：一些閱讀通知我，更好的樞軸選擇可能是選擇數組中的3個值的中值（例如中間，底部和頂部或3個隨機位置）。有些人主張採用5個數值的中位數。樞軸接近陣列中最小值或最大值時，發生快速排序的最差情況，此策略旨在防禦發生的情況。這只是對某些類型數據的優化 - 這不是必需的。