隨機快速排序

兩種方法來實現隨機化快速排序，隨機快速排序

方法一：選擇一個隨機樞軸

方法2：生成輸入的隨機置換和其饋送到選擇了第一個元素作爲樞軸

一個快速排序

就隨機化而言，方法1與方法2是否相同？

注意：看起來像Method2產生所有分區的可能性相同，但method1不會。所以如果它們不一樣，那麼我想了解性能影響是什麼。

2013-02-13 vikky.rk

我會說是。在每個步驟中的二進制分區在兩種方法中遵循相同的規律。 – 2013-02-13 21:46:15

是的。在任何一種情況下，選擇任何特定元素作爲支點的概率都是1/len（輸入）。（但是，第二種方法幾乎可以肯定比一個常數要慢，因爲它需要一個額外的線性過程來產生隨機排列。）

2013-02-13 22:13:48 jacobm

但是對於一個特定的輸入，第二種方法有所有n！排列的可能性相同，但第1種方法不會更改輸入的相對排序，因此它不包括輸入的所有可能分區。所以我覺得有所不同，但不知道它會有什麼影響。 – 2013-02-13 23:30:37

我不確定「所有可能的分區」是什麼意思。大於或小於主元素的元素集合完全不依賴於它們的順序。 – jacobm 2013-02-13 23:34:37

對不起，我感到困惑，我現在明白了。謝謝 – 2013-02-21 05:49:11

回答