用php構建quicksort

Question

我最近閱讀了關於quicksort的內容，想知道用quicksort構建我自己的函數來分類還是不太合適。你認爲內建的sort函數比自建quicksort函數更好嗎？

Answer 1

從http://php.net/sort

注：與大多數PHP排序 函數一樣，sort（）使用»Quicksort的 實現。

核心PHP函數會在C實現的，而不是PHP，所以他們一般應該比任何你可以寫自己在PHP顯著更快。有些情況下編寫自己的代碼會更快，但是我想這是在你有一個非常特殊的情況下，你可以爲此做出自己特定的優化。我認爲這不太可能是這種情況。

Answer 2

堅持內置排序功能。 Quicksort是一種簡單的算法，但要在實際使用的計算機上獲得良好的性能，需要一點技巧。內置函數比在合理的時間內寫入的任何內容都更加優化。 （使用C而不是PHP編寫的恆定因子加速也可能有幫助。）

如果您排序的排序函數減慢了很多元素，那麼您可能做錯了什麼。 （這是PHP畢竟。您應該使用數據密集型處理的通用語言，這將是更容易編寫你的代碼，它會運行得更快。）

Answer 3

事實上，我在一個演示文稿中爲一個數據點做了這件事。該測試使用本地排序函數和使用php編寫的quicksort算法的實現對250,000個整數的數組進行排序。數組的內容對於兩次運行都完全相同，數據是隨機的，報告的時間僅用於執行排序，而不是調用php解釋器所需的其他處理。

結果：

 
    Native sort implementation: 1.379 seconds 
PHP quicksort implementation: 30.615 seconds 

肯定使用本機實現。任何解釋型語言都應該如此。

對我使用在相同的硬件和操作系統一樣執行相同的條件下測試的其他語言的結果，提供了一個有趣的性能比較，並把PHP結果透視：

 
       C: 0.107 seconds 
      Java: 0.250 seconds 
JavaScript (FF3): 4.401 seconds 

值得注意的是，Chrome瀏覽器Safari對JavaScript測試的執行速度更快，但我不在這裏包括這些測試，因爲這些測試是在不同的環境中記錄的。

Answer 4

僅供參考有一個PHP實現此處

http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Quicksort#C.23

Answer 5

有一件事對PHP的快速排序（ASORT，arsort等）是他們惹你相等的值，也就是說，價值觀使用不同的密鑰將隨機交換位置，即使在不同的運行之間。令人驚訝的是，代碼可以一次又一次地使用相同的數據產生不同的順序。最後，我不得不實施自己的快速排序來消除這種異常情況。

Answer 6

只是爲了好玩，這裏是就地版本PHP快速排序的我想出了。這裏的技巧是傳遞數組作爲參考。

function partition(&$arr,$leftIndex,$rightIndex) 
{ 
    $pivot=$arr[($leftIndex+$rightIndex)/2]; 

    while ($leftIndex <= $rightIndex) 
    {   
     while ($arr[$leftIndex] < $pivot)    
       $leftIndex++; 
     while ($arr[$rightIndex] > $pivot) 
       $rightIndex--; 
     if ($leftIndex <= $rightIndex) { 
       $tmp = $arr[$leftIndex]; 
       $arr[$leftIndex] = $arr[$rightIndex]; 
       $arr[$rightIndex] = $tmp; 
       $leftIndex++; 
       $rightIndex--; 
     } 
    } 
    return $leftIndex; 
} 

function quickSort(&$arr, $leftIndex, $rightIndex) 
{ 
    $index = partition($arr,$leftIndex,$rightIndex); 
    if ($leftIndex < $index - 1) 
     quickSort($arr, $leftIndex, $index - 1); 
    if ($index < $rightIndex) 
     quickSort($arr, $index, $rightIndex); 
}