我对 python 完全陌生，我正在尝试在其中实现快速排序。有人可以帮我完成我的代码吗？
我不知道如何连接三个数组并打印它们。
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)
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
无需额外内存的快速排序（就地）
用法：
array = [97, 200, 100, 101, 211, 107]
quicksort(array)
print(array)
# array -> [97, 100, 101, 107, 200, 211]
def partition(array, begin, end):
pivot = begin
for i in range(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)
还有一个简洁漂亮的版本
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]])
让我解释一下上面的代码以了解详细信息
选择数组的第一个元素arr[0]作为枢轴
[arr[0]]
qsort数组中小于枢轴的那些元素List Comprehension
qsort([x for x in arr[1:] if x < arr[0]])
qsort那些大于枢轴的数组元素List Comprehension
qsort([x for x in arr[1:] if x >= arr[0]])
此答案是针对Python 2.x. 我的回答是对Rosetta Code的就地解决方案的解释，它也适用于Python 3：
import random
def qsort(xs, fst, lst):
'''
Sort the range xs[fst, lst] in-place with vanilla QuickSort
:param xs: the list of numbers to sort
:param fst: the first index from xs to begin sorting from,
must be in the range [0, len(xs))
:param lst: the last index from xs to stop sorting at
must be in the range [fst, len(xs))
:return: nothing, the side effect is that xs[fst, lst] is sorted
'''
if fst >= lst:
return
i, j = fst, lst
pivot = xs[random.randint(fst, lst)]
while i <= j:
while xs[i] < pivot:
i += 1
while xs[j] > pivot:
j -= 1
if i <= j:
xs[i], xs[j] = xs[j], xs[i]
i, j = i + 1, j - 1
qsort(xs, fst, j)
qsort(xs, i, lst)
如果你愿意放弃就地属性，下面是另一个版本，它更好地说明了快速排序背后的基本思想。除了可读性之外，它的另一个优点是它是稳定的（相同的元素出现在排序列表中的顺序与它们在未排序列表中的顺序相同）。这种稳定性属性不适用于上面介绍的内存较少的就地实现。
def qsort(xs):
if not xs: return xs # empty sequence case
pivot = xs[random.choice(range(0, len(xs)))]
head = qsort([x for x in xs if x < pivot])
tail = qsort([x for x in xs if x > pivot])
return head + [x for x in xs if x == pivot] + tail
使用 Python 进行快速排序
在现实生活中，我们应该始终使用 Python 提供的内置排序。然而，理解快速排序算法是有益的。
我的目标是分解主题，使其易于读者理解和复制，而无需返回参考资料。
快速排序算法本质上如下：
如果数据是随机分布的，则选择第一个数据点作为枢轴相当于随机选择。
首先，让我们看一个使用注释和变量名指向中间值的可读示例：
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如果为假则返回前一个元素，否则如果为真，它评估并返回以下元素，我们有：
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 分区方案，您可以在 wikipedia 上阅读更多信息（但我们显然partition()通过使用 while-loop 语义而不是 do-while 并将缩小步骤移至外部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]
该算法经常在计算机科学课程中教授，并在工作面试中被要求。它帮助我们思考递归和分而治之。
快速排序在 Python 中不是很实用，因为我们内置的timsort算法非常有效，而且我们有递归限制。我们希望使用 就地排序列表list.sort或创建新的排序列表sorted- 两者都接受一个key和reverse参数。
已经有很多答案了，但我认为这种方法是最干净的实现：
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(lst):
if len(lst) < 2:
return list
pivot = lst.pop()
left = list(filter(lambda x: x <= pivot, lst))
right = list(filter(lambda x: x > pivot, lst))
return qsort(left) + [pivot] + qsort(right)
从 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)
函数式编程方法
smaller = lambda xs, y: filter(lambda x: x <= y, xs)
larger = lambda xs, y: filter(lambda x: x > y, xs)
qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else []
print qsort([3,1,4,2,5]) == [1,2,3,4,5]
这是使用 Hoare 分区方案的快速排序版本，交换和局部变量更少
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)
我认为这里的两个答案都适用于提供的列表（它回答了原始问题），但如果传递了包含非唯一值的数组，则会中断。因此，为了完整起见，我只想指出每个小错误并解释如何修复它们。
例如，尝试使用Brionius算法对以下数组 [12,4,5,6,7,3,1,15,1] （注意 1 出现两次）进行排序 .. 在某些时候会以较少的数组为空而结束以及具有一对值 (1,1) 的相等数组，在下一次迭代中无法分离，并且len() > 1 ...因此您将得到一个无限循环
您可以通过返回数组来修复它（如果less为空，或者更好地通过不在相等数组中调用 sort 来修复它，如zangw答案中所示）
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)
elif x == pivot:
equal.append(x)
else: # if 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 hande the part at the end of the recursion - when you only have one element in your array, just return the array.
return array
更高级的解决方案也中断了，但由于不同的原因，它缺少递归行中的return子句，这将导致在某些时候返回 None 并尝试将其附加到列表中......
要修复它，只需在该行添加一个返回
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]])
分区- 通过枢轴拆分数组，较小的元素向左移动，较大的元素向右移动，反之亦然。枢轴可以是数组中的随机元素。为了制作这个算法，我们需要知道什么是数组的开始和结束索引以及枢轴点在哪里。然后设置两个辅助指针L，R。
所以我们有一个数组 user[...,begin,...,end,...]
L 和 R 指针的起始位置
[...,begin,next,...,end,...]
R L
while L < end
1. 如果 user[pivot] > user[L] 然后将 R 移动 1 并将 user[R] 与 user[L] 交换
2. 将 L 移动 1
在将 user[R] 与 user[pivot] 交换之后
快速排序- 使用分区算法，直到由枢轴分割的每个下一部分的开始索引都大于或等于结束索引。
def qsort(user, begin, end):
if begin >= end:
return
# partition
# pivot = begin
L = begin+1
R = begin
while L < end:
if user[begin] > user[L]:
R+=1
user[R], user[L] = user[L], user[R]
L+= 1
user[R], user[begin] = user[begin], user[R]
qsort(user, 0, R)
qsort(user, R+1, end)
tests = [
{'sample':[1],'answer':[1]},
{'sample':[3,9],'answer':[3,9]},
{'sample':[1,8,1],'answer':[1,1,8]},
{'sample':[7,5,5,1],'answer':[1,5,5,7]},
{'sample':[4,10,5,9,3],'answer':[3,4,5,9,10]},
{'sample':[6,6,3,8,7,7],'answer':[3,6,6,7,7,8]},
{'sample':[3,6,7,2,4,5,4],'answer':[2,3,4,4,5,6,7]},
{'sample':[1,5,6,1,9,0,7,4],'answer':[0,1,1,4,5,6,7,9]},
{'sample':[0,9,5,2,2,5,8,3,8],'answer':[0,2,2,3,5,5,8,8,9]},
{'sample':[2,5,3,3,2,0,9,0,0,7],'answer':[0,0,0,2,2,3,3,5,7,9]}
]
for test in tests:
sample = test['sample'][:]
answer = test['answer']
qsort(sample,0,len(sample))
print(sample == answer)
或者，如果您更喜欢单行代码，它还说明了 C/C++ 可变参数、lambda 表达式和 if 表达式的 Python 等效项：
qsort = lambda x=None, *xs: [] if x is None else qsort(*[a for a in xs if a<x]) + [x] + qsort(*[a for a in xs if a>=x])
def quick_sort(self, nums):
def helper(arr):
if len(arr) <= 1: return arr
#lwall is the index of the first element euqal to pivot
#rwall is the index of the first element greater than pivot
#so arr[lwall:rwall] is exactly the middle part equal to pivot after one round
lwall, rwall, pivot = 0, 0, 0
#choose rightmost as pivot
pivot = arr[-1]
for i, e in enumerate(arr):
if e < pivot:
#when element is less than pivot, shift the whole middle part to the right by 1
arr[i], arr[lwall] = arr[lwall], arr[i]
lwall += 1
arr[i], arr[rwall] = arr[rwall], arr[i]
rwall += 1
elif e == pivot:
#when element equals to pivot, middle part should increase by 1
arr[i], arr[rwall] = arr[rwall], arr[i]
rwall += 1
elif e > pivot: continue
return helper(arr[:lwall]) + arr[lwall:rwall] + helper(arr[rwall:])
return helper(nums)
我知道很多人都正确回答了这个问题，我很喜欢阅读它们。我的答案与 zangw 几乎相同，但我认为以前的贡献者没有很好地从视觉上解释事情的实际运作方式......所以这是我试图帮助其他可能在未来访问这个问题/答案的人快速排序实现的简单解决方案。
它是如何工作的 ？
这是一个带有视觉效果的示例...（枢轴）9,11,2,0
平均：n 的 n 对数
最坏的情况：n^2
编码：
def quicksort(data):
if (len(data) < 2):
return data
else:
pivot = data[0] # pivot
#starting from element 1 to the end
rest = data[1:]
low = [each for each in rest if each < pivot]
high = [each for each in rest if each >= pivot]
return quicksort(low) + [pivot] + quicksort(high)
项目=[9,11,2,0] 打印（快速排序（项目））
该算法包含两个边界，一个具有小于枢轴的元素（由索引“j”跟踪），另一个具有大于枢轴的元素（由索引“i”跟踪）。
在每次迭代中，通过递增 j 来处理一个新元素。
不变：-
如果违反不变量，则交换第 i 个和第 j 个元素，并且 i 递增。
在处理完所有元素以及对枢轴之后的所有内容进行分区之后，将枢轴元素与最后一个小于它的元素交换。
枢轴元素现在将位于序列中的正确位置。它之前的元素将小于它，它之后的元素将大于它，并且它们将是未排序的。
def quicksort(sequence, low, high):
if low < high:
pivot = partition(sequence, low, high)
quicksort(sequence, low, pivot - 1)
quicksort(sequence, pivot + 1, high)
def partition(sequence, low, high):
pivot = sequence[low]
i = low + 1
for j in range(low + 1, high + 1):
if sequence[j] < pivot:
sequence[j], sequence[i] = sequence[i], sequence[j]
i += 1
sequence[i-1], sequence[low] = sequence[low], sequence[i-1]
return i - 1
def main(sequence):
quicksort(sequence, 0, len(sequence) - 1)
return sequence
if __name__ == '__main__':
sequence = [-2, 0, 32, 1, 56, 99, -4]
print(main(sequence))
一个“好的”支点将产生两个大小大致相同的子序列。确定性地，可以以简单的方式选择枢轴元素，也可以通过计算序列的中值来选择。
选择枢轴的简单实现将是第一个或最后一个元素。在这种情况下，最坏的运行时间将是输入序列已经排序或反向排序时，因为其中一个子序列将为空，这将导致每次递归调用仅删除一个元素。
当枢轴是序列的中值元素时，可以实现完美平衡的拆分。大于它和小于它的元素数量相等。这种方法保证了更好的整体运行时间，但更耗时。
选择枢轴的非确定性/随机方式是随机均匀地选择一个元素。这是一种简单且轻量级的方法，可以最大限度地减少最坏情况，并导致大致平衡的拆分。这也将在幼稚方法和选择枢轴的中值方法之间提供平衡。
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
def quick_sort(array):
return quick_sort([x for x in array[1:] if x < array[0]]) + [array[0]] \
+ quick_sort([x for x in array[1:] if x >= array[0]]) if array else []
def Partition(A,p,q):
i=p
x=A[i]
for j in range(p+1,q+1):
if A[j]<=x:
i=i+1
tmp=A[j]
A[j]=A[i]
A[i]=tmp
l=A[p]
A[p]=A[i]
A[i]=l
return i
def quickSort(A,p,q):
if p<q:
r=Partition(A,p,q)
quickSort(A,p,r-1)
quickSort(A,r+1,q)
return A
一个“真正的”就地实现 [来自 Michael T. Goodrich 和 Roberto Tamassia 的算法设计和应用书的算法 8.9、8.11]：
from random import randint
def partition (A, a, b):
p = randint(a,b)
# or mid point
# p = (a + b) / 2
piv = A[p]
# swap the pivot with the end of the array
A[p] = A[b]
A[b] = piv
i = a # left index (right movement ->)
j = b - 1 # right index (left movement <-)
while i <= j:
# move right if smaller/eq than/to piv
while A[i] <= piv and i <= j:
i += 1
# move left if greater/eq than/to piv
while A[j] >= piv and j >= i:
j -= 1
# indices stopped moving:
if i < j:
# swap
t = A[i]
A[i] = A[j]
A[j] = t
# place pivot back in the right place
# all values < pivot are to its left and
# all values > pivot are to its right
A[b] = A[i]
A[i] = piv
return i
def IpQuickSort (A, a, b):
while a < b:
p = partition(A, a, b) # p is pivot's location
#sort the smaller partition
if p - a < b - p:
IpQuickSort(A,a,p-1)
a = p + 1 # partition less than p is sorted
else:
IpQuickSort(A,p+1,b)
b = p - 1 # partition greater than p is sorted
def main():
A = [12,3,5,4,7,3,1,3]
print A
IpQuickSort(A,0,len(A)-1)
print A
if __name__ == "__main__": main()
该算法有 4 个简单的步骤：
python中算法的代码：
def my_sort(A):
p=A[0] #determine pivot element.
left=[] #create left array
right=[] #create right array
for i in range(1,len(A)):
#if cur elem is less than pivot, add elem in left array
if A[i]< p:
left.append(A[i])
#the recurssion will occur only if the left array is atleast half the size of original array
if len(left)>1 and len(left)>=len(A)//2:
left=my_sort(left) #recursive call
elif A[i]>p:
right.append(A[i]) #if elem is greater than pivot, append it to right array
if len(right)>1 and len(right)>=len(A)//2: # recurssion will occur only if length of right array is atleast the size of original array
right=my_sort(right)
A=left+[p]+right #append all three part of the array into one and return it
return A
my_sort([12,4,5,6,7,3,1,15])
用左右部分递归地继续这个算法。
另一个快速排序实现：
# A = Array
# s = start index
# e = end index
# p = pivot index
# g = greater than pivot boundary index
def swap(A,i1,i2):
A[i1], A[i2] = A[i2], A[i1]
def partition(A,g,p):
# O(n) - just one for loop that visits each element once
for j in range(g,p):
if A[j] <= A[p]:
swap(A,j,g)
g += 1
swap(A,p,g)
return g
def _quicksort(A,s,e):
# Base case - we are sorting an array of size 1
if s >= e:
return
# Partition current array
p = partition(A,s,e)
_quicksort(A,s,p-1) # Left side of pivot
_quicksort(A,p+1,e) # Right side of pivot
# Wrapper function for the recursive one
def quicksort(A):
_quicksort(A,0,len(A)-1)
A = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,-1]
print(A)
quicksort(A)
print(A)
对于 Python 3.x 版本：一种函数式使用operator模块，主要是为了提高可读性。
from operator import ge as greater, lt as lesser
def qsort(L):
if len(L) <= 1: return L
pivot = L[0]
sublist = lambda op: [*filter(lambda num: op(num, pivot), L[1:])]
return qsort(sublist(lesser))+ [pivot] + qsort(sublist(greater))
并被测试为
print (qsort([3,1,4,2,5]) == [1,2,3,4,5])
这是一个简单的实现：-
def quicksort(array):
if len(array) < 2:
return array
else:
pivot= array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([10, 5, 2, 3]))
我的回答与@alisianoi 的伟大回答非常相似。但是，我相信他的代码效率低下（请参阅我的评论），我将其删除。此外，我添加了更多解释，并对重复（枢轴）值的问题进行了更具体的说明。
def quicksort(nums, begin=0, end=None):
# Only at the beginning end=None. In this case set to len(nums)-1
if end is None: end = len(nums) - 1
# If list part is invalid or has only 1 element, do nothing
if begin>=end: return
# Pick random pivot
pivot = nums[random.randint(begin, end)]
# Initialize left and right pointers
left, right = begin, end
while left < right:
# Find first "wrong" value from left hand side, i.e. first value >= pivot
# Find first "wrong" value from right hand side, i.e. first value <= pivot
# Note: In the LAST while loop, both left and right will point to pivot!
while nums[left] < pivot: left += 1
while nums[right] > pivot: right -= 1
# Swap the "wrong" values
if left != right:
nums[left], nums[right] = nums[right], nums[left]
# Problem: loop can get stuck if pivot value exists more than once. Simply solve with...
if nums[left] == nums[right]:
assert nums[left]==pivot
left += 1
# Now, left and right both point to a pivot value.
# All values to its left are smaller (or equal in case of duplicate pivot values)
# All values to its right are larger.
assert left == right and nums[left] == pivot
quicksort(nums, begin, left - 1)
quicksort(nums, left + 1, end)
return
没有递归：
def quicksort(nums, ranges=None):
if ranges is None:
ranges = [[0, len(nums) - 1]]
while ranges != []:
[start, end] = ranges[0]
ranges = ranges[1:]
if start >= end:
continue
pivot = nums[randint(start, end)]
left = start
right = end
while left < right:
while nums[left] < pivot:
left += 1
while nums[right] > pivot:
right -= 1
if left != right:
nums[left], nums[right] = nums[right], nums[left]
if nums[left] == nums[right]:
left += 1
ranges = [[start, left - 1], [left + 1, end]] + ranges
我附上下面的代码！由于枢轴值的位置，这种快速排序是一个很好的学习工具。由于它位于一个固定的位置，因此您可以多次浏览它并真正了解它是如何工作的。在实践中，最好随机化枢轴以避免 O(N^2) 运行时间。
def quicksort10(alist):
quicksort_helper10(alist, 0, len(alist)-1)
def quicksort_helper10(alist, first, last):
""" """
if first < last:
split_point = partition10(alist, first, last)
quicksort_helper10(alist, first, split_point - 1)
quicksort_helper10(alist, split_point + 1, last)
def partition10(alist, first, last):
done = False
pivot_value = alist[first]
leftmark = first + 1
rightmark = last
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivot_value:
leftmark = leftmark + 1
while leftmark <= rightmark and alist[rightmark] >= pivot_value:
rightmark = rightmark - 1
if leftmark > rightmark:
done = True
else:
temp = alist[leftmark]
alist[leftmark] = alist[rightmark]
alist[rightmark] = temp
temp = alist[first]
alist[first] = alist[rightmark]
alist[rightmark] = temp
return rightmark
def quick_sort(l):
if len(l) == 0:
return l
pivot = l[0]
pivots = [x for x in l if x == pivot]
smaller = quick_sort([x for x in l if x < pivot])
larger = quick_sort([x for x in l if x > pivot])
return smaller + pivots + larger
在分区步骤打印变量的完整示例：
def partition(data, p, right):
print("\n==> Enter partition: p={}, right={}".format(p, right))
pivot = data[right]
print("pivot = data[{}] = {}".format(right, pivot))
i = p - 1 # this is a dangerous line
for j in range(p, right):
print("j: {}".format(j))
if data[j] <= pivot:
i = i + 1
print("new i: {}".format(i))
print("swap: {} <-> {}".format(data[i], data[j]))
data[i], data[j] = data[j], data[i]
print("swap2: {} <-> {}".format(data[i + 1], data[right]))
data[i + 1], data[right] = data[right], data[i + 1]
return i + 1
def quick_sort(data, left, right):
if left < right:
pivot = partition(data, left, right)
quick_sort(data, left, pivot - 1)
quick_sort(data, pivot + 1, right)
data = [2, 8, 7, 1, 3, 5, 6, 4]
print("Input array: {}".format(data))
quick_sort(data, 0, len(data) - 1)
print("Output array: {}".format(data))
def is_sorted(arr): #check if array is sorted
for i in range(len(arr) - 2):
if arr[i] > arr[i + 1]:
return False
return True
def qsort_in_place(arr, left, right): #arr - given array, #left - first element index, #right - last element index
if right - left < 1: #if we have empty or one element array - nothing to do
return
else:
left_point = left #set left pointer that points on element that is candidate to swap with element under right pointer or pivot element
right_point = right - 1 #set right pointer that is candidate to swap with element under left pointer
while left_point <= right_point: #while we have not checked all elements in the given array
swap_left = arr[left_point] >= arr[right] #True if we have to move that element after pivot
swap_right = arr[right_point] < arr[right] #True if we have to move that element before pivot
if swap_left and swap_right: #if both True we can swap elements under left and right pointers
arr[right_point], arr[left_point] = arr[left_point], arr[right_point]
left_point += 1
right_point -= 1
else: #if only one True we don`t have place for to swap it
if not swap_left: #if we dont need to swap it we move to next element
left_point += 1
if not swap_right: #if we dont need to swap it we move to prev element
right_point -= 1
arr[left_point], arr[right] = arr[right], arr[left_point] #swap left element with pivot
qsort_in_place(arr, left, left_point - 1) #execute qsort for left part of array (elements less than pivot)
qsort_in_place(arr, left_point + 1, right) #execute qsort for right part of array (elements most than pivot)
def main():
import random
arr = random.sample(range(1, 4000), 10) #generate random array
print(arr)
print(is_sorted(arr))
qsort_in_place(arr, 0, len(arr) - 1)
print(arr)
print(is_sorted(arr))
if __name__ == "__main__":
main()
该算法不使用递归函数。
让N是任何带有 的数字列表len(N) > 0。设置K = [N]并执行以下程序。
注意：这是一个稳定的排序算法。
def BinaryRip2Singletons(K, S):
K_L = []
K_P = [ [K[0][0]] ]
K_R = []
for i in range(1, len(K[0])):
if K[0][i] < K[0][0]:
K_L.append(K[0][i])
elif K[0][i] > K[0][0]:
K_R.append(K[0][i])
else:
K_P.append( [K[0][i]] )
K_new = [K_L]*bool(len(K_L)) + K_P + [K_R]*bool(len(K_R)) + K[1:]
while len(K_new) > 0:
if len(K_new[0]) == 1:
S.append(K_new[0][0])
K_new = K_new[1:]
else:
break
return K_new, S
N = [16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]
K = [ N ]
S = []
print('K =', K, 'S =', S)
while len(K) > 0:
K, S = BinaryRip2Singletons(K, S)
print('K =', K, 'S =', S)
节目输出：
K = [[16, 19, 11, 15, 16, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1]] S = []
K = [[11, 15, 10, 12, 14, 4, 10, 5, 2, 3, 4, 7, 1], [16], [16], [19]] S = []
K = [[10, 4, 10, 5, 2, 3, 4, 7, 1], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[4, 5, 2, 3, 4, 7, 1], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[2, 3, 1], [4], [4], [5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = []
K = [[5, 7], [10], [10], [11], [15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4]
K = [[15, 12, 14], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [[12, 14], [15], [16], [16], [19]] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11]
K = [] S = [1, 2, 3, 4, 4, 5, 7, 10, 10, 11, 12, 14, 15, 16, 16, 19]
可能只是一个偏好，但我喜欢在我的函数顶部添加验证。
def quicksort(arr):
if len(arr) <= 1:
return arr
left = []
right = []
equal = []
pivot = arr[-1]
for num in arr:
if num < pivot:
left.append(num)
elif num == pivot:
equal.append(num)
else:
right.append(num)
return quicksort(left) + equal + quicksort(right)
不要将三个不同的数组用于较小的相等较大的数组，然后将所有数组连接起来，而是尝试传统的概念（分区方法）：
http://pythonplanet.blogspot.in/2015/08/quick-sort-using-traditional-partition.html
这是不使用任何内置功能。
分区函数 -
def partitn(alist, left, right):
i=left
j=right
mid=(left+right)/2
pivot=alist[mid]
while i <= j:
while alist[i] < pivot:
i=i+1
while alist[j] > pivot:
j=j-1
if i <= j:
temp = alist[i]
alist[i] = alist[j]
alist[j] = temp
i = i + 1
j = j - 1
我将使用 numpy 库进行快速排序。我认为这是一个非常有用的图书馆。他们已经实现了快速排序方法，但您也可以实现您的自定义方法。
import numpy
array = [3,4,8,1,2,13,28,11,99,76] #The array what we want to sort
indexes = numpy.argsort( array , None, 'quicksort', None)
index_list = list(indexes)
temp_array = []
for index in index_list:
temp_array.append( array[index])
array = temp_array
print array #it will show sorted array
def quick_sort(list):
if len(list) ==0:
return []
return quick_sort(filter( lambda item: item < list[0],list)) + [v for v in list if v==list[0] ] + quick_sort( filter( lambda item: item > list[0], list))
内嵌排序
def qsort(a, b=0, e=None):
# partitioning
def part(a, start, end):
p = start
for i in xrange(start+1, end):
if a[i] < a[p]:
a[i], a[p+1] = a[p+1], a[i]
a[p+1], a[p] = a[p], a[p+1]
p += 1
return p
if e is None:
e = len(a)
if e-b <= 1: return
p = part(a, b, e)
qsort(a, b, p)
qsort(a, p+1, e)
没有递归：
deq = collections.deque()
deq.append((b, e))
while len(deq):
el = deq.pop()
if el[1] - el[0] > 1:
p = part(a, el[0], el[1])
deq.append((el[0], p))
deq.append((p+1, el[1]))
def quicksort(items):
if not len(items) > 1:
return items
items, pivot = partition(items)
return quicksort(items[:pivot]) + [items[pivot]] + quicksort(items[pivot + 1:])
def partition(items):
i = 1
pivot = 0
for j in range(1, len(items)):
if items[j] <= items[pivot]:
items[i], items[j] = items[j], items[i]
i += 1
items[i - 1], items[pivot] = items[pivot], items[i - 1]
return items, i - 1