在 python 中实现快速排序并交换枢轴值

Question

我们知道，在实施快速排序时，我们 select 一个主元 value.And 在分区阶段我们用右标记交换主元值。这是我的代码：

def quicksort(mylist):
    quicksorthelper(mylist,0,len(mylist)-1)


def quicksorthelper(mylist,first,last):
   if first< last:
      splitpoint=partition(mylist,first,last)
      quicksorthelper(mylist,first,splitpoint-1)
      quicksorthelper(mylist,splitpoint+1,last)

def partition(mylist,first,last):
    pivot= mylist[first]
    leftmark= first +1
    rightmark= last
    done = False
    counter = 0
    while not done:
          while leftmark <= rightmark and mylist[leftmark]< pivot:
                leftmark = leftmark +1
          while leftmark <= rightmark and mylist[rightmark]>pivot:
                rightmark= rightmark -1

          if leftmark>rightmark:
            done = True
          else:
              temp = mylist[leftmark]
              mylist[leftmark]=mylist[rightmark]
              mylist[rightmark]=temp
              counter +=1


    temp= pivot                  #pivot = mylist[first]
    pivot = mylist[rightmark]
    mylist[rightmark]=temp

    return rightmark

mylist= [54,26,93,17,77,31,44,55,20]
quicksort(mylist)
print(mylist)

所以问题是，如果我写 pivot 而不是 mylist[first]，程序就无法运行，而如果我写 mylist[first] 代替 pivot，同时与 rightmark 交换值，它就可以正常工作。你能告诉我为什么会这样吗

此外，如果我尝试做类似的事情： mylist = [54, 26, 93, 17, 77, 31, 44, 55, 20] sortlist=quicksort(mylist) print(sortlist) 然后输出是None。不知道那有什么问题

Answer 1

关于您的最后一个问题：快速排序不会 return 任何东西。这就是为什么 sortlist=quicksort(mylist) 将排序列表设置为 None。

阅读 How do I pass a variable by reference? 以了解发生了什么。

Answer 2

此实现不起作用：

temp= pivot                  #pivot = mylist[first]
pivot = mylist[rightmark]
mylist[rightmark]=temp

因为你不变异 mylist当你变异

pivot = mylist[rightmark]

你只是给变量分配一个新值pivot:

>>> i = 2
>>> j = 4
>>> somelist = ['a','b','c','d','e','f','g']
>>> pivot = somelist[i]
>>> pivot
'c'
>>> temp = pivot
>>> pivot = somelist[j]
>>> pivot
'e'
>>> somelist[j] = temp
>>> pivot
'e'
>>> somelist
['a', 'b', 'c', 'd', 'c', 'f', 'g']

出于同样的原因，执行以下操作不会更改列表：

>>> anotherlist = [1, 2, 3]
>>> x = anotherlist[1]
>>> x
2
>>> x = 53
>>> x
53
>>> anotherlist
[1, 2, 3]

你必须做到：

>>> anotherlist[0] = 53
>>> anotherlist
[53, 2, 3]
>>>

或者您可以使用增变器方法。

最后，你不需要 temp 变量来交换 Python:

>>> a = 42
>>> b = 88
>>> a,b = b,a
>>> a
88
>>> b
42
>>>

或使用列表：

>>> somelist = ['a','b','c','d','e','f','g']
>>> i = 2
>>> j = 4
>>> somelist[i], somelist[j] = somelist[j], somelist[i]
>>> somelist
['a', 'b', 'e', 'd', 'c', 'f', 'g']

在 python 中实现快速排序并交换枢轴值

Implementation of Quick sort in python and exchanging pivot value

python

sorting

algorithm

quicksort

python-3.x