如何保證quicksort將排序整數數組？

Question

在講座中被問到了...有點難住了。

如何保證quicksort總是對整數數組進行排序？

謝謝。

Answer 1

快速排序功能通過獲取一個數據透視值，並將其餘數據分爲兩組。一個更高，一個更低。然後，您會依次對每個組執行此操作，直到獲得不超過一個的組爲止。此時，您可以保證數據的排序，因爲您可以保證任何樞軸值都位於正確的位置，因爲您已直接將其與另一個樞軸值進行比較，該值也位於正確的位置。最後，剩下的大小爲1或大小爲0的集合無法排序，因爲它們無法重新排列，因此已經排序。

希望這會有所幫助，這正是我們爲A Level高等數學（英國16-18）所教授的內容。

Answer 2

你的教授可能指的是「穩定性」。看看這裏：http://en.wikipedia.org/wiki/Stable_sort#Stability。穩定的排序算法用相同的密鑰維護記錄的相對順序。如果所有的鍵都不同，那麼這個區別就沒有必要了。

快速排序（在高效實現中）不是一個穩定的排序，因此確保穩定性的一種方法是確保數組中沒有重複的整數。

Answer 3

無償剽竊Wikipedia：

分區算法的正確性是基於以下 兩個參數：

• 在每次迭代中，所有迄今 處於期望的處理的元件位置：在樞軸之前如果小於主軸的 的值，則在樞軸之後如果大於主軸的值（循環 不變）。
• 每次迭代只剩下一個要處理的元素 （循環變體）。

整體算法的正確性可通過感應來證明 ：零個或一個元件，該算法離開數據 不變;對於較大的數據集，它會生成兩個部分的連接，元素小於主鍵和大於它的元素， 自己按遞歸假設排序。