维基百科
臭皮匠排序
臭皮匠排序(英語:Stooge Sort)是一种采用分治法的低效排序算法,甚至慢于冒泡排序。在《算法导论》第二版第7章(快速排序)的思考题中被提到,是由Howard、Fine等教授提出的所谓“漂亮的”排序算法。
实现
- 如果最后一个值小于第一个值,则交换這兩個數
- 如果当前集合元素数量大于等于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
實作範例
Julia (程式語言)
# Julia Sample : Stooge Sort function StoogeSort(A,v1,v2) if A[v1]>A[v2] A[v1],A[v2] = A[v2],A[v1] end if (v2-v1+1)>2 t = Int(round((v2-v1+1)/3)) StoogeSort(A, v1 , v2-t) StoogeSort(A, v1+t, v2 ) StoogeSort(A, v1 , v2-t) end return A end # Main Code A = [16,586,1,31,354,43,3] println(A) # Original Array println(StoogeSort(A,1,length(A))) # Stooge Sort Array
参考
- 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 (页面存档备份,存于互联网档案馆)
- ^ 存档副本 (PDF). [2017-11-30]. (原始内容 (PDF)于2017-12-01).