臭皮匠排序
外观
臭皮匠排序 | |
---|---|
使用臭皮匠排序為一列數字進行排序的過程 | |
概况 | |
類別 | 排序算法 |
資料結構 | 數組 |
复杂度 | |
最坏时间复杂度 | O(nlog 3 /log 1.5) |
空間複雜度 | O(n) |
最佳解 | No |
相关变量的定义 |
臭皮匠排序(英語:Stooge Sort)是一种采用分治法的低效排序算法,甚至慢于冒泡排序。在《算法导论》第二版第7章(快速排序)的思考题中被提到,是由Howard、Fine等教授提出的所谓“漂亮的”排序算法。
该算法得名于三个臭皮匠,每个臭皮匠都能暴打其他两个,其他兩個也會卯起來扁其中一個。[1]
实现
- 如果最后一个值小于第一个值,则交换這兩個數
- 如果当前集合元素数量大于等于3:
- 使用臭皮匠排序法排序前2/3的元素
- 使用臭皮匠排序法排序后2/3的元素
- 再次使用臭皮匠排序法排序前2/3的元素
algorithm stoogesort(array L, i = 0, j = length(L)-1)
if L[j] < L[i] then
L[i] ↔ L[j]
if (j - i + 1) >= 3 then
t = (j - i + 1) / 3
stoogesort(L, i , j-t)
stoogesort(L, i+t, j )
stoogesort(L, i , j-t)
return L
参考
- Black, Paul E. stooge sort. Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology. [2011-06-18]. (原始内容存档于2008-09-20).
- Everything2.com – Stooge sort (页面存档备份,存于互联网档案馆)
- Sorting Algorithms(包含臭皮匠排序) (页面存档备份,存于互联网档案馆)
- Stooge sort – implementation and comparison (页面存档备份,存于互联网档案馆)
|
|