臭皮匠排序

维基百科,自由的百科全书
跳转至: 导航搜索
臭皮匠排序
Sorting stoogesort anim.gif
使用臭皮匠排序為一列數字進行排序的過程
分類 排序算法
數據結構 數組
最差時間複雜度 O(nlog 3 /log 1.5)
最差空間複雜度 O(n)

Stooge 排序是一种低效的递归排序算法,甚至慢于冒泡排序。在《算法导论》第二版第7章(快速排序)的思考题中被提到,是由HowardFine等教授提出的所谓“漂亮的”排序算法。

该算法得名于三个臭皮匠,每个臭皮匠都打其他两个。[來源請求]

实现[编辑]

  • 如果最后一个值小于第一个值,则交换它们
  • 如果当前子集元素数量大于等于3:
  1. 使用臭皮匠排序前2/3的元素
  2. 使用臭皮匠排序后2/3的元素
  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

参考[编辑]