Python 快速排序类型错误

Question

以下是我的代码抛出的错误：

File "python", line 39, in <module>
File "python", line 8, in quicksort
File "python", line 8, in quicksort
TypeError: unsupported operand type(s) for -: 'NoneType' and 'int'

以下是我的快速排序代码：

#!/usr/bin/python
# -*- coding: utf-8 -*-
def quicksort(arr, beg, end):
if beg < end:
pivot = partition(arr, beg, end)
quicksort(arr, beg, pivot - 1)
quicksort(arr, pivot + 1, end)
def partition(arr, beg, end):
left = beg
right = end
loc = beg
while arr[loc] <= arr[right] and loc != right:
right = right - 1
if loc == right:
return loc
elif arr[loc] > arr[right]:
(arr[loc], arr[right]) = (arr[right], arr[loc])
loc = right
while arr[loc] >= arr[left] and loc != left:
left = left + 1
if loc == left:
return loc
elif arr[loc] < arr[left]:
(arr[loc], arr[left]) = (arr[left], arr[loc])
loc = left
y = [9,7,5,1,5]
quicksort(y, 0, 4)
print(y)

Answer 1

您不能从不同类型的变量(None和int(中减去 2 个变量。
你之所以None，是因为并非所有函数partition路径都返回一些东西。
我在末尾添加了一条对我来说最有意义的return语句：

#!/usr/bin/python
# -*- coding: utf-8 -*-
def quicksort(arr, beg, end):
if beg < end:
pivot = partition(arr, beg, end)
quicksort(arr, beg, pivot - 1)
quicksort(arr, pivot + 1, end)
def partition(arr, beg, end):
left = beg
right = end
loc = beg
while arr[loc] <= arr[right] and loc != right:
right = right - 1
if loc == right:
return loc
elif arr[loc] > arr[right]:
(arr[loc], arr[right]) = (arr[right], arr[loc])
loc = right
while arr[loc] >= arr[left] and loc != left:
left = left + 1
if loc == left:
return loc
elif arr[loc] < arr[left]:
(arr[loc], arr[left]) = (arr[left], arr[loc])
loc = left
return loc

y = [9,7,5,1,5]
quicksort(y, 0, 4)
print(y)  # >>> [1, 5, 5, 7, 9]

但是，我没有检查每个场景的代码逻辑的正确性。
您可以检查此线程以查看 python 中快速排序的实现。

Answer 2

从函数partition你没有返回任何内容。你已经把它分配给pivot变量。这就是问题所在。照顾您应该返回的值。