将列表排序为(Python代码)中的函数

Question

我想编写一些函数，但我遇到了一些困难。

第一个函数是"func"，它基本上类似于“分区”。此函数接受一个列表和两个整数(num1和num2)。该函数“查看”第一个数字的子列表起始索引(num1)，并结束(非独占)最后一个数字的索引(num2)。

一个新的变量- "here"，将是子列表中的最后一个元素。这个函数("func")取代了器官的顺序，这样每个子都会列出哪些器官太小而不能留在"here“中，而所有其他的器官都会在他的右边。此函数返回"here“的新位置的索引。

我定义了变量"position"，即左肢小于"here“的位置的索引。在运行开始时，"position“将等于num1。函数"func“在子列表中所有器官的索引上切换，不包括最后一个元素。如果手臂小于这里的当前索引，我们从器官替换它，而不是here，并将here提升为1。

最后，替换"here“(子列表中最后一个位置的器官)和器官，而不是"position”。函数"func“返回位置。

以下是我创建的示例代码(欢迎告诉我您的想法)：

def func(lst, num1, num2):
    position = num1
    here = lst[num2 - 1]
    for i in range (len(lst)-1):
        if lst[i] < here:
            lst[position], lst[i] = lst[i], lst[position]
            position = position +1
    lst[position], lst[len(lst) - 1] = here, lst[position]
    return position

这段代码很好，至少它可以工作。如果按F5键并在shell中写入：

>>> lst = [41, 7, 17, 3, 24, 16]
>>> func(lst, 0, len(lst))
    2

现在，我想实现另一个函数"a_func2“。此函数接受一个列表和两个数字( num1和num2 )。此函数仅对子列表进行排序，以num1开头，以(不包括) num2结尾，与我之前在问题开头所写的方式相同。不同的是，这一次我想使用我编写的函数"func“，以便对"here”左边和右边的器官进行排序。换句话说，它有点像递归函数，对吧？

 def a_func2(lst, num1, num2):
 ##HAVE NO IDEA 

或者换句话说，第一次排序是不够的。"func“只对列表排序一次。我想让第二个函数"a_func2“对列表进行排序，直到列表有一个完美的顺序。差不多吧。

我被这部分卡住了，我不知道该怎么做。有谁能帮帮我吗？谢谢!

Answer 1

看起来您正在尝试实现Quicksort。您已经完成了算法的“分区”部分，并且希望实现递归部分。这很简单:对列表进行分区，然后快速排序左右两部分。

def func(lst, num1, num2):
    position = num1
    here = lst[num2 - 1]
    for i in range (num1, num2):
        if lst[i] < here:
            lst[position], lst[i] = lst[i], lst[position]
            position = position +1
    lst[position], lst[num2-1] = here, lst[position]
    return position

def quicksort(lst, num1, num2):
    if num2 - num1 <= 1:
        #this portion of lst is only zero or one elements long. Don't need to do anything.
        return
    partition = func(lst, num1, num2)
    #sort left half of lst
    quicksort(lst, num1, partition)
    #sort right half
    quicksort(lst, partition+1, num2)

x = [16,23,15,8,42,4]
quicksort(x, 0, len(x))
print x

结果：

[4, 8, 15, 16, 23, 42]

请注意，我必须稍微修改一下func。主要是用num2-1替换len(lst)-1的所有实例。这是因为前者获得列表的最后一个元素的索引，而后者获得子列表的最后一个元素的索引，这就是您想要的。