測試評估：14種排序算法和PHP數組

在這篇文章里，我將向大家介紹用PHP寫的排序算法的測試。
以下是14種排序算法：

• 快速排序
• 計數排序
• 梳排序
• 堆排序
• 歸并排序
• 希爾排序
• 選擇排序
• 插入排序
• 地精排序
• 聯合冒泡排序
• 雞尾酒排序
• 冒泡排序
• 奇偶排序
• 使用標志的冒泡排序

算法不是按字母排序，而是按照它們進行8千個元素排序時整體速度遞減來排序。

以下是用到的數組的大小：

• 1
• 100
• 200
• 400
• 600
• 800
• 1000
• 5000
• 10000
• 15000
• 20000
• 25000
• 30000

每次測量都用不同大小的數組，然后傳入排序函數。

• 第一種情況下，數組被隨機填充（1，N)之間的值，其中N指數組的大小。
• 第二種情況下，數組被隨機填充（1，PHP_INT_MAX）之間的值，其中PHP_INT_MAX是指當前系統中INT類型的最大值，在我的系統中為2^63或大約為9.2233720368548E+18。

每種測試進行3次，然后取其算術平均值。

1000個元素的數組

在當前數組大小的所有算法排序情況。

30000個元素的數組

此時，5種最快的算法進行測試：計數排序，快速排序，梳排序，堆排序和歸并排序。

200000個元素的數組

此時，5種最快的算法進行測試：計數排序，快速排序，梳排序，堆排序和歸并排序。

2000000個元素的數組

在最后一輪2000000個元素的測試中，只有2種算法進行測試：計數排序和快速排序。

總結

快速排序是實至名歸的好算法。計數排序在小值范圍里表現良好；其他情況因為低內存而應 付不來。雞尾酒排序對于隨機值是一個壞選擇。冒泡排序及其變形并不適合實際應用。

所有算法的源代碼+結果：https://drive.google.com/file/d/0B63HSL7JD630VWdSSFgwdHR5RkU/edit?usp=sharing

使用內置排序函數是一個有趣的練習。使用解釋型的PHP來寫排序函數永遠也快不過sort() 采用的C變體。

原文鏈接： ahwoobachairiesaas   翻譯： 伯樂在線 - hoikin-yiu
譯文鏈接： http://blog.jobbole.com/68774/