Stooge 排序的 Python 程序

pythonserver side programmingprogramming

在本文中，我们将了解下面给出的问题陈述的解决方案。

问题陈述 − 给定一个数组，我们需要使用 stooge 排序对其进行排序。

算法

1. 检查索引 0 处的值是否大于最后一个索引处的值，然后交换它们。
2. 对数组的初始 2/3 进行排序。
3. 对数组的最后 2/3 进行排序。
4. 再次对初始 2/3 进行排序以确认。

现在让我们观察下面实现中的解决方案 −

示例

def stoogesort(arr, l, h):
   if l >= h:
      return
   # 交换
   if arr[l]>arr[h]:
      t = arr[l]
      arr[l] = arr[h]
      arr[h] = t
   # 超过 2 个元素
   if h-l+1 > 2:
      t = (int)((h-l+1)/3)
      # 对前 2/3 个元素进行排序
      stoogesort(arr, l, (h-t))
      # 对后 2/3 个元素进行排序
      stoogesort(arr, l+t, (h))
      # 再次对前 2/3 个元素进行排序
      stoogesort(arr, l, (h-t))
# main
arr = [1,4,2,3,6,5,8,7]
n = len(arr)
stoogesort(arr, 0, n-1)
print ("排序后的序列为:")
for i in range(0, n):
   print(arr[i], end = " ")