use*_*481 80 python sorting algorithm quicksort
我是python的新手,我正在尝试实现quicksort.有人可以帮我完成我的代码吗？
我不知道如何连接三个数组并打印它们.
def sort(array=[12,4,5,6,7,3,1,15]):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
if x == pivot:
equal.append(x)
if x > pivot:
greater.append(x)
sort(less)
sort(pivot)
sort(greater)
Bri*_*ius 228
def sort(array=[12,4,5,6,7,3,1,15]):
"""Sort the array by using quicksort."""
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
elif x == pivot:
equal.append(x)
elif x > pivot:
greater.append(x)
# Don't forget to return something!
return sort(less)+equal+sort(greater) # Just use the + operator to join lists
# Note that you want equal ^^^^^ not pivot
else: # You need to handle the part at the end of the recursion - when you only have one element in your array, just return the array.
return array
suq*_*ant 141
快速排序,无需额外内存(就地)
用法:
array = [97, 200, 100, 101, 211, 107]
quicksort(array)
# array -> [97, 100, 101, 107, 200, 211]
def partition(array, begin, end):
pivot = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot += 1
array[i], array[pivot] = array[pivot], array[i]
array[pivot], array[begin] = array[begin], array[pivot]
return pivot
def quicksort(array, begin=0, end=None):
if end is None:
end = len(array) - 1
def _quicksort(array, begin, end):
if begin >= end:
return
pivot = partition(array, begin, end)
_quicksort(array, begin, pivot-1)
_quicksort(array, pivot+1, end)
return _quicksort(array, begin, end)
zan*_*ngw 68
还有另一个简洁而美丽的版本
def qsort(arr):
if len(arr) <= 1:
return arr
else:
return qsort([x for x in arr[1:] if x < arr[0]]) + \
[arr[0]] + \
qsort([x for x in arr[1:] if x >= arr[0]])
# this comment is just to improve readability due to horizontal scroll!!!
让我解释一下上面的代码细节
选择数组的第一个元素arr[0]作为pivot
[arr[0]]
qsort 数组中那些小于数组的元素 List Comprehension
qsort([x for x in arr[1:] if x < arr[0]])
qsort 那些比pivot更大的数组元素 List Comprehension
qsort([x for x in arr[1:] if x >= arr[0]])
ali*_*noi 29
如果我在Google中搜索"python quicksort implementation",这个问题就是弹出的第一个结果.我知道最初的问题是"帮助纠正代码"但是已经有很多答案无视这个要求:目前排名第二的被选中的一个,可笑的单行与热闹的"你被解雇"的评论,一般来说,许多非就地实现(即使用与输入列表大小成比例的额外内存).这个答案提供了一个就地解决方案,但它是为了python 2.x.因此,下面是我对Rosetta Code的就地解决方案的解释,它也可以正常工作python 3:
import random
def qsort(l, fst, lst):
if fst >= lst: return
i, j = fst, lst
pivot = l[random.randint(fst, lst)]
while i <= j:
while l[i] < pivot: i += 1
while l[j] > pivot: j -= 1
if i <= j:
l[i], l[j] = l[j], l[i]
i, j = i + 1, j - 1
qsort(l, fst, j)
qsort(l, i, lst)
如果你愿意放弃就地财产,下面是另一个更好地说明quicksort背后的基本思想的版本.除了可读性之外,它的另一个优点是它是稳定的(相同的元素以与它们在未排序列表中相同的顺序出现在排序列表中).这种稳定性属性不适用于上面提到的内存消耗较少的就地实现.
def qsort(l):
if not l: return l # empty sequence case
pivot = l[random.choice(range(0, len(l)))]
head = qsort([elem for elem in l if elem < pivot])
tail = qsort([elem for elem in l if elem > pivot])
return head + [elem for elem in l if elem == pivot] + tail
Aar*_*all 22
使用Python进行Quicksort
在现实生活中,我们应该始终使用Python提供的内置类型.但是,了解quicksort算法是有益的.
我的目标是打破主题,使读者易于理解和复制,而无需返回参考资料.
快速排序算法基本上如下:
如果数据是随机分布的,则选择第一个数据点作为枢轴等同于随机选择.
首先,让我们看一个使用注释和变量名称指向中间值的可读示例:
def quicksort(xs):
"""Given indexable and slicable iterable, return a sorted list"""
if xs: # if given list (or tuple) with one ordered item or more:
pivot = xs[0]
# below will be less than:
below = [i for i in xs[1:] if i < pivot]
# above will be greater than or equal to:
above = [i for i in xs[1:] if i >= pivot]
return quicksort(below) + [pivot] + quicksort(above)
else:
return xs # empty list
要重述此处演示的算法和代码 - 我们将数值移动到枢轴上方的右侧,并将值移动到左侧的数据集下方,然后将这些分区传递给相同的函数以进一步排序.
这可以打高尔夫球到88个字符:
q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])
要了解我们如何实现这一目标,请先阅读我们的可读示例,删除注释和文档字符串,然后找到就地支点:
def quicksort(xs):
if xs:
below = [i for i in xs[1:] if i < xs[0]]
above = [i for i in xs[1:] if i >= xs[0]]
return quicksort(below) + [xs[0]] + quicksort(above)
else:
return xs
现在找到以下,就地:
def quicksort(xs):
if xs:
return (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))
else:
return xs
现在,知道and如果为false则返回前一个元素,否则如果为true,则计算并返回以下元素,我们有:
def quicksort(xs):
return xs and (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))
由于lambdas返回单个epression,并且我们已经简化为单个表达式(即使它变得越来越难以理解),我们现在可以使用lambda:
quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] )
+ [xs[0]]
+ quicksort([i for i in xs[1:] if i >= xs[0]]))
并且为了简化我们的示例,将函数和变量名称缩短为一个字母,并消除不需要的空格.
q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])
请注意,这个lambda与大多数代码打高尔夫球一样,风格相当糟糕.
先前的实现创建了许多不必要的额外列表.如果我们能够就地做到这一点,我们将避免浪费空间.
下面的实现使用Hoare分区方案,您可以在维基百科上阅读更多信息(但我们显然partition()通过使用while循环语义而不是do-while并将缩小步骤移动到结束时每次调用最多删除4个冗余计算外部while循环.).
def quicksort(a_list):
"""Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
def _quicksort(a_list, low, high):
# must run partition on sections with 2 elements or more
if low < high:
p = partition(a_list, low, high)
_quicksort(a_list, low, p)
_quicksort(a_list, p+1, high)
def partition(a_list, low, high):
pivot = a_list[low]
while True:
while a_list[low] < pivot:
low += 1
while a_list[high] > pivot:
high -= 1
if low >= high:
return high
a_list[low], a_list[high] = a_list[high], a_list[low]
low += 1
high -= 1
_quicksort(a_list, 0, len(a_list)-1)
return a_list
不确定我是否彻底测试过:
def main():
assert quicksort([1]) == [1]
assert quicksort([1,2]) == [1,2]
assert quicksort([1,2,3]) == [1,2,3]
assert quicksort([1,2,3,4]) == [1,2,3,4]
assert quicksort([2,1,3,4]) == [1,2,3,4]
assert quicksort([1,3,2,4]) == [1,2,3,4]
assert quicksort([1,2,4,3]) == [1,2,3,4]
assert quicksort([2,1,1,1]) == [1,1,1,2]
assert quicksort([1,2,1,1]) == [1,1,1,2]
assert quicksort([1,1,2,1]) == [1,1,1,2]
assert quicksort([1,1,1,2]) == [1,1,1,2]
该算法经常在计算机科学课程中教授,并要求进行面试.它有助于我们思考递归和分而治之.
Quicksort在Python中不太实用,因为我们的内置时序算法非常有效,并且我们有递归限制.我们希望对列表进行排序list.sort或创建新的排序列表sorted- 两者都采用key和reverse参数.
Seb*_*ren 21
已经有很多答案,但我认为这种方法是最干净的实现:
def quicksort(arr):
""" Quicksort a list
:type arr: list
:param arr: List to sort
:returns: list -- Sorted list
"""
if not arr:
return []
pivots = [x for x in arr if x == arr[0]]
lesser = quicksort([x for x in arr if x < arr[0]])
greater = quicksort([x for x in arr if x > arr[0]])
return lesser + pivots + greater
您当然可以跳过将所有内容存储在变量中并将其直接返回,如下所示:
def quicksort(arr):
""" Quicksort a list
:type arr: list
:param arr: List to sort
:returns: list -- Sorted list
"""
if not arr:
return []
return quicksort([x for x in arr if x < arr[0]]) \
+ [x for x in arr if x == arr[0]] \
+ quicksort([x for x in arr if x > arr[0]])
功能方法:
def qsort(list):
if len(list) < 2:
return list
pivot = list.pop()
left = filter(lambda x: x <= pivot, list)
right = filter(lambda x: x > pivot, list)
return qsort(left) + [pivot] + qsort(right)
这是使用霍尔分区方案的快速排序的一个版本，具有较少的交换和局部变量
def quicksort(array):
qsort(array, 0, len(array)-1)
def qsort(A, lo, hi):
if lo < hi:
p = partition(A, lo, hi)
qsort(A, lo, p)
qsort(A, p + 1, hi)
def partition(A, lo, hi):
pivot = A[lo]
i, j = lo-1, hi+1
while True:
i += 1
j -= 1
while(A[i] < pivot): i+= 1
while(A[j] > pivot ): j-= 1
if i >= j:
return j
A[i], A[j] = A[j], A[i]
test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print quicksort(test)
使用 grokking 算法轻松实现
def quicksort(arr):
if len(arr) < 2:
return arr #base case
else:
pivot = arr[0]
less = [i for i in arr[1:] if i <= pivot]
more = [i for i in arr[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(more)