臭皮匠排序

臭皮匠排序(英语: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

原文地址:https://zh.wikipedia.org/wiki/%E8%87%AD%E7%9A%AE%E5%8C%A0%E6%8E%92%E5%BA%8F

知识共享 署名-相同方式共享 3.0协议之条款下提供

文章作者: 张拓
文章链接: http://www.xssl.online/%e8%87%ad%e7%9a%ae%e5%8c%a0%e6%8e%92%e5%ba%8f/
版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 许可协议。转载请注明来自 张拓的博客
浏览次数: 531

张拓

陕西西安蓝田张拓QQ1070410059。一生所求不过“心安”二字。 然,尘世多纷扰。

发表回复