computer-science - 如何对 5 个正整数进行排序？

Question

我有一个 5 个唯一整数的随机集合，范围从 1 到 15，我想从右到左按升序对它们进行排序。

Example input:  15 6 7 3 4
Desired output: 15 7 6 4 3

规则:

我们一次只能“看到”(15 6 7 3 4) 中最右边的三个整数 (7 3 4)，并且只能对数组中最右边的整数 (4 )。我们还可以在代码中使用最多 5 个整型变量。

可能的操作:

putend，最右边的整数放在数组最左边的位置

(15 6 7 3 4) -> (4 15 6 7 3)

swap，最右边的整数与第二个整数交换。 最右边的整数在数组中向左移动一步。

(15 6 7 3 4) -> ( 15 6 7 4 3)

双交换，最右边的整数与第二个元素交换，然后与第三个元素交换。 最右边的整数在数组中向左移动 2 步。

(15 6 7 3 4) -> (15 6 4 7 3).

<小时/>

我的尝试:

while (not solved)
  if first element < 2nd element
    putend
  else if first element > 2nd element
    if first element > 3rd element
        double swap
    else
      swap

输出:

15 6 7 3 4  swap
15 6 7 4 3  putend
3 15 6 7 4  putend
4 3 15 6 7  swap
4 3 15 7 6  putend
6 4 3 15 7  putend
7 6 4 3 15 (problem here, triggers double swap but want putend and somehow detect that I am done)

Answer 1

我创建了一个可用的 Python 程序来演示算法，但我认为它对于每个人来说都像伪代码一样可读(我使代码非常简单)。解决方案相当残酷，但似乎有效。进一步优化的潜力也很大。我在评论中添加了描述:

x = [15, 12, 3, 2, 13]

def putend():
    x.append(x.pop(0))

def swap():
    x[0], x[1] = x[1], x[0]

def doubleswap():
    x[0], x[1], x[2] = x[1], x[2], x[0]


def put_smallest_back():
  smallest = min(x[0], x[1], x[2])
  if x[2] == smallest:
    # Move smallest to x[1]
    doubleswap()
  if x[1] == smallest:
    # Move smallest to x[0]
    swap()
  putend()

# Put back two smallest values of four to make sure two largest are in front
put_smallest_back()
put_smallest_back()

# Now two largest values are in three accessible cells
# Find and put back second largest
largest = max(x[0], x[1], x[2])
smallest = min(x[0], x[1], x[2])
if x[2] != largest and x[2] != smallest:
  doubleswap()
if x[1] != largest and x[1] != smallest:
  swap()
putend()

# Find and put back largest
# Largest is in x[0] or x[1]
if x[1] == largest:
  swap()

# Largest is in x[0]
putend()

# Two largest values are sorted
# Time to sort x[2]
if x[0] > x[1] and x[0] > x[2]:
  doubleswap()
elif x[1] > x[0] and x[1] > x[2]:
  swap()
  doubleswap()

# Last step, sort x[0] and x[1]
if x[0] > x[1]:
  swap()

# Voilla!
print(x)

我使用了 min() 和 max() 函数，但没有定义它们，但它们的实现很简单，特别是它们总是对集合的前三个元素进行操作。