臭皮匠排序

臭皮匠排序
	使用臭皮匠排序為一列數字進行排序的過程
概况
類別	排序算法
資料結構	數組
复杂度
最坏时间复杂度	O(nlog 3 /log 1.5)
空間複雜度	O(n)
最佳解	No
相关变量的定义

臭皮匠排序（英語：）是一种采用分治法的低效排序算法，甚至慢于冒泡排序。在《算法导论》第二版第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. . 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）.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] (PDF). [2017-11-30]. （原始内容存档 (PDF)于2017-12-01）.