尝试在极其有限的“python”版本中创建另一个数组的索引的排序数组

Question

我正在尝试创建一个排序函数，它将创建“输入数组”的索引数组。

例如。 Array(19,21,15,50,14) 将返回 Array(4,2,0,1,3)

这听起来可能很简单，但我使用的“python”版本非常有限。 （不要问哪个或为什么用引号引起来，这不是重点。）以下是限制：

• 无法通过函数传递变量（

  return

  ，以及诸如

  def func(var2, var1)

  之类的东西），但我可以使用它们来更改全局变量的值
• 不能使用嵌入数组
• 不能使用任何“预构建”Python 函数，例如

  sort()

  或其他
• 无法更改同一行中的 2 个变量的值，例如

  var1,var2 = var2,var1

我正在寻找一种时间复杂度最低的方法。我觉得我知道如何使用冒泡排序或插入排序来做到这一点，但我需要排序的数组有 41 个项目长......

我尝试编写合并排序和快速排序，因为它们的时间复杂度较低，但我不知道如何在函数之间不携带变量的情况下实现它们。

如果你确实想出了一个算法，请用Python编写它，以便我可以将它翻译成我非常酷的Python版本。

Answer 1

根据问题的前提，要排序的数组是全局的，如array[]。

声明一个全局索引数组：index[]。根据全局数组中的值对索引进行排序。比较会使用类似 (array[index[i]] <= array[index[j]]).

然后，如果稍后要完成的话，您可以重新排序索引[]和数组[]，以在O(n)时间内对索引[]和数组[]进行排序。这主要用于根据其中之一对多个数组进行排序：根据 array1[] 中的值对 array1[]、array2[]、array[3]、... 进行排序。