如果數組的大小是偶數而不是奇數，那麼數組的元素是中位數？

Question

我讀，它可能使快速排序運行在O（nlogn）

的算法每一步說，選擇中位數爲支點

但是，假設我們有這個數組：

10 8 39 2 9 20 

哪個值會是中位數？

在數學，如果我記得正確的中位數爲（39 + 2）/ 2 = 41/2 = 20.5

我沒有在我的陣列中的20.5，雖然

在此先感謝

Answer 1

你可以選擇其中之一;如果你認爲輸入是一個限制，那麼擴大就不重要了。

Answer 2

中值實際上是由第一分揀陣列，所以在你的例子中，中值是通過排列的編號2 8 9 10 20 39發現，中位數將是兩個中間元素的平均值，實測值（9 +10）/ 2 = 9.5，這對你一點幫助都沒有。使用中位數是一種理想的情況，但是如果數組至少已經部分排序了，我想可以工作。

隨着偶數數組，你無法找到一個確切的支點，所以我相信你可以使用中間的數字。它會降低效率，但不會大幅度提高，除非您總是對數組進行排序。

Answer 3

我們正在談論的算法描述的確切措辭在這裏，我不知道你在引用的文本。但我認爲在「中位數」的上下文中，它們可能意味着，而不是列表中數值的數學中位數，而是列表中的中間點，即中值INDEX，其在此實數中爲3或4.作爲coffNjava說，你可以拿任何一個。

Answer 4

找到一個未分類的一組數字的中位數爲O（N）的時間內完成，但它是不是真的有必要尋找快速排序的軸的目的，真正的中位數。你只需要找到一個合理的關鍵點。

作爲Wikipedia entry for quicksort says：

在快速排序的非常早期版本中，分區的最左邊的元素往往會被選擇作爲樞轉元件。不幸的是，這會導致已排序數組的最壞情況行爲，這是一種相當常見的用例。這個問題很容易解決，方法是選擇一個隨機索引作爲主鍵，選擇分區的中間索引或者（特別是對於更長的分區），選擇分區的第一個，中間和最後一個元素的中位數（如R. Sedgewick）。

找到三個值的中位數要比找到整個值集合要容易得多，對於具有偶數個元素的集合，找到兩個「中間」元素中的哪一個並不重要你選擇作爲潛在的關鍵。