如何在java中找到中位數的快速排序

Question

所以我一直在努力正確實施一個快速排序算法的作業分配整晚，並在搜索了幾個小時後，我找不到任何具體實施的中位數分區。所以，我被困在一個巨大的障礙，我不知道我的算法的哪一部分是可怕的，因爲所有在線算法都是僞代碼（所以他們對分區的描述極其模糊），所以不可能我檢查我的實施。所以這裏是我的弗蘭肯斯坦的代碼在閱讀文檔之後，文檔說明了中位數的樞軸選擇如何與java中的快速排序一起工作。

http://mitpress.mit.edu/algorithms/solutions/chap9-solutions.pdf：

這裏是我發現到目前爲止，甚至遠程有用的唯一來源，而且都是上使算法的工作零件痛苦含糊其辭，故意將花費這麼多時間搜索後似乎

http://www.cs.umd.edu/~meesh/351/mount/lectures/lect9-medians-selection.pdf

* HTTP：//www.ics.uci.edu/~eppstein/161/960130.html

* HTTP：//en.wikipedia.org/wiki/Selection_algorithm

這裏是我的快速排序算法：

{Removed Code} 

這是我的選擇方法，我覺得可怕搞砸的部分是，我如何選擇中位數，中位數和中位數，但我無法在網上找到的任何東西引導我的分區：

{Removed Code} 

也爲我的分區我用我的正常快速排序劃分方法，但這樣的樞軸作爲參數略有改變，我不知道是否有別的我應該這樣做，因爲網上的所有來源在這方面都是模糊的：

{Removed Code} 

這裏是我的排序的5組插入排序，以防萬一：

{Removed Code} 

任何深入瞭解我搞砸了算法的哪一部分會非常讚賞，因爲我一直將我的頭撞在牆上試圖找出錯誤的地方。在選擇算法中肯定存在一個巨大的錯誤，因爲我的JUnit測試對預選結果爲50的中位數的[1..100]預失敗，但我的算法總是吐出54個。

Answer 1

Where您應該從5元素「子集」中選擇您在其旁邊選取元素的中位數：中位數的索引值爲2，但您選擇的索引值爲3。您需要：

int median = subset[2]; // Or sslength/2 if you don't like hardcoded values 

順便說一句，在「位數的中位數」的[1..100]將是48或53，而不是50 20寫的5網格數字：在價值觀中間行（3,8,13，...）是「子集」的中間值。