您可能会考虑更容易实现快速排序。例如,
my_list = [52,8,45,43,6,56,76,36,54,12,34,98,41,30]
def quicksort(arr):
high = []
low = []
pivot_list = []
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
for i in arr:
if i < pivot:
low.append(i)
elif i > pivot:
high.append(i)
else:
pivot_list.append(i)
high = quicksort(high)
low = quicksort(low)
return low + pivot_list + high
print quicksort(my_list)
[6, 8, 12, 30, 34, 36, 41, 43, 45, 52, 54, 56, 76, 98]
这个相当简单的实现很容易解释。 您正在根据主键的任意选择对列表进行分区。在这种情况下,arr[0] = 52
。然后你遍历整个列表,如果元素大于pivot(52),你把它放到'high'分区,如果它小于52,你就把它放到'low'分区。在通过一个运行后这一点(我们运行high = quicksort(high)
之前),我们有
low = [8, 45, 43, 6, 36, 12, 34, 41, 30]
high = [56, 76, 54, 98]
pivot_list = [52]
然后,我们对“低”和“高”的分区上运行此快速排序功能。例如,对于高分区,pivot = arr[0] = 56
。我们遍历高分区,如果元素小于主分区(56),我们将它放在一个新的低分区组中,该分区组是高分区的子组。如果元素大于56,那么我们把它放在新的高分区中,高分区是高分区的子组。你可以把它看作是从一个我们想要排序的列表开始,然后分成一个高分区和一个低分区,然后每个分区分支到他们自己的高分区和低分区。这就是递归进来的地方