我必须使用插入排序和递归（无循环）对数组进行排序

Question

我必须使用插入排序和递归而不使用循环对数组进行排序。我已经尝试过，但它没有对任何内容进行排序。这是我的代码：

def recursiveInsertionSort(array, i, j):
    n = len(array)
    if i < n:
        temp = array[i]
        j = i - 1
        if j >= 0 and array[j] > temp:
            array[j + 1] = array[j]
            recursiveInsertionSort(array, i, j - 1)
        array[j + 1] = temp
        recursiveInsertionSort(array, i + 1, j)
    return array

arr = [10, 8, 7, 50, 60, 3, 9, -1]
print(recursiveInsertionSort(arr, 1, 0))

输出为 [10, 8, 7, 50, 60, 3, 9, -1] 与给定数组相同。预期输出为 [-1, 3, 7, 8, 9, 10, 50, 60] 谁能帮我找到问题出在哪里？

Answer 1

递归是函数式遗产，因此以函数式风格使用它会产生最佳结果。这意味着避免突变、变量重新分配和其他副作用。

我们可以使用

归纳推理

来写insertion_sort(t)。从输入源

src = t

和空目标数组

dst = []

-

开始

1. 如果

   src

   为空，则没有剩余内容可供排序。返回

   dst

   数组
2. （归纳）

   src

   至少有一个元素。

   insert

   将第一个元素

   src[0]

   放入

   dst

   并在子问题

   src[1:]

上重复出现

def insertion_sort(t):
  def run(src, dst):
    if not src:
      return dst                                # 1
    else:
      return run(src[1:], insert(dst, src[0]))  # 2
  return run(t, [])

insert(t, x)

可以使用相同的技术来编写 -

1. 如果输入

   t

   为空，则唯一可能的输出是

   [x]

2. （归纳）

   t

   至少有一个元素。如果第一个元素

   t[0]

   小于要插入的元素

   x

   ，则将

   t[0]

   添加到递归子问题的结果

   insert(t[1:], x)

3. （归纳）

   t

   第一个元素大于或等于

   x

   。将

   x

   添加到

   t

def insert(t, x):
  if not t:
    return [x]                        # 1
  elif t[0] < x:
    return [t[0]] + insert(t[1:], x)  # 2
  else:
    return [x] + t                    # 3

最后打印结果

arr = [10, 8, 7, 50, 60, 3, 9, -1]
print(insertion_sort(arr))

[-1, 3, 7, 8, 9, 10, 50, 60]

可视化

写出评估步骤可以帮助我们直观地了解递归计算如何增长。 首先我们看一下两者中更简单的一个，

insert(t,x)

insert([3, 7, 8, 10, 50, 60], 9)
== [3] + insert([7, 8, 10, 50, 60], 9)
== [3] + [7] + insert([8, 10, 50, 60], 9)
== [3] + [7] + [8] + insert([10, 50, 60], 9)
== [3] + [7] + [8] + [9] + [10, 50, 60]
== [3, 7] + [8] + [9] + [10, 50, 60]
== [3, 7, 8] + [9] + [10, 50, 60]
== [3, 7, 8, 9] + [10, 50, 60]
== [3, 7, 8, 9, 10, 50, 60]

现在让我们想象一下

insertion_sort(t)

-

insertion_sort([10, 8, 7, 50, 60, 3, 9, -1])
== run([10, 8, 7, 50, 60, 3, 9, -1], [])
== run([8, 7, 50, 60, 3, 9, -1], [10])
== run([7, 50, 60, 3, 9, -1], [8, 10])
== run([50, 60, 3, 9, -1], [7, 8, 10])
== run([60, 3, 9, -1], [7, 8, 10, 50])
== run([3, 9, -1], [7, 8, 10, 50, 60])
== run([9, -1], [3, 7, 8, 10, 50, 60])
== run([-1], [3, 7, 8, 9, 10, 50, 60])
== run([], [-1, 3, 7, 8, 9, 10, 50, 60])
== [-1, 3, 7, 8, 9, 10, 50, 60]

Answer 2

老实说，你的代码中有太多错误，我无法列出，但这可行：

def recursiveInsertionSort(array, i, j):
    n = len(array)
    if i < n and j >= 0:
        if array[j] > array[j + 1]:
            temp = array[j + 1]
            array[j + 1] = array[j]
            array[j] = temp
        recursiveInsertionSort(array, i, j - 1)
    if j == 0:
        recursiveInsertionSort(array, i + 1, i)
    return array

arr = [10, 8, 7, 50, 60, 3, 9, -1]
print(recursiveInsertionSort(arr, 1, 0))

输出：

[-1, 3, 7, 8, 9, 10, 50, 60]

Answer 3

这个对我有用，

def insertionSort(a, index):
    if index == len(a):
        return a
    else:
        if index > 0:
            for i in range(index, len(a)):
                temp = a[i]
                j = i - 1
                while j>=0 and a[j] > temp:
                    a[j+1] = a[j]
                    j -= 1
                a[j+1] = temp
        return insertionSort(a, index+1)

print(insertionSort([10, 8, 7, 50, 60, 3, 9, -1], 0))