QuickSort在算法的征服階段實現排序？

我非常困惑。一個測驗題是「真或假，快速排序實現在算法的征服階段排序」因爲我記得讀我選擇了正確的：QuickSort在算法的征服階段實現排序？

三個步驟快速排序如下：

除法：重新排列元素並將數組拆分爲兩個子數組和中間元素，以便左側子數組中的每個元素小於或等於中間元素，並且右側子數組中的每個元素都大於中間元素。

征服：對兩個子陣列進行遞歸排序。

組合：無。

然而，答案的猜謎說，答案是沒有任何解釋假...

由於文字書說，快速排序如下分而治之算法中征服階段遞歸兩個子陣列進行排序，不該答案是否屬實？

任何啓發將不勝感激。

2017-07-25 J.J.Trie

我投票結束這個問題作爲題外話，因爲我認爲它屬於計算機科學 –

快速排序選擇一個關鍵點，將一切放在左側，一切放大到右側。

這是您所指的分步驟。

征服部分是在左側和右側子集上遞歸執行此操作。

然而，在分步，元素已經被排序（左小，更大的右）和快速排序工作，因爲遞歸這樣做可以確保一切都在正確的地方。

的定義是沒有錯的，因爲征服重複這種對左側和右側，但分的部分是真正的分裂和重新排列它們，如前所述。

2017-07-25 03:34:58

gee是有道理的！謝謝 –

不用擔心！另一種思考它的方式正如下面有人指出的那樣，在每一個劃分步驟中，主軸都被放置在正確的位置（分類）。希望能幫助到你！ –

對於小於或大於主元的值，等於主元的值可能會被調換到右側或左側。將較小的值放在左側，將較大的值放在正確的位置，這樣每個分割步驟都會增加元素的排序，直到獲得2或3個元素，並將這些元素移動到正確的位置。與其他一些分治算法不同，對於快速排序，分割後沒有任何組合。 – rcgldr

實際上，快速排序可以在算法的分階段實現排序。分割數組後，中間元素位於其正確的位置，因此您有一個元素在每個分割階段之後排序。

2017-07-25 03:34:59 lsdsjy

小於或大於數據透視點的值將移動到每個分區的右邊位置，因此在每個分區步驟中排序變得更接近排序。 – rcgldr

回答