Python中的就地QuickSort
Python中的就地QuickSort
提问于 2013-07-21 22:44:14
我必须用自己选择的语言实现作业的QuickSort算法，所以我选择了Python语言。
在讲座中，我们被告知QuickSort是内存高效的，因为它在原地工作；也就是说，它没有用于递归的输入数组部分的额外副本。
考虑到这一点，我尝试用Python语言实现QuickSort算法，但不久之后我意识到，为了编写一段优雅的代码，我必须在递归时将数组的一部分传递给函数本身。由于每次执行此操作时，Python都会创建新列表，因此我尝试使用Python3 (因为它支持非本地关键字)。下面是我的注释代码。
def quicksort2(array):
# Create a local copy of array.
arr = array
def sort(start, end):
# Base case condition
if not start < end:
return
# Make it known to the inner function that we will work on arr
# from the outer definition
nonlocal arr
i = start + 1
j = start + 1
# Choosing the pivot as the first element of the working part
# part of arr
pivot = arr[start]
# Start partitioning
while j <= end:
if arr[j] < pivot:
temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
i += 1
j += 1
temp = arr[start]
arr[start] = arr[i - 1]
arr[i - 1] = temp
# End partitioning
# Finally recurse on both partitions
sort(start + 0, i - 2)
sort(i, end)
sort(0, len(array) - 1)现在，我不确定我是否做得很好，或者我错过了什么。我已经编写了一个更具Pythonic风格的QuickSort版本，但它肯定不能正常工作，因为它会返回输入数组的各个部分并将它们连接在一起。
我的问题是，这是在Python中实现的方法吗？我已经搜索了Google和SO，但还没有找到真正的QuickSort实现，所以我想最好问一下。
回答 7
Stack Overflow用户
回答已采纳
发布于 2013-07-21 22:50:15
当然不是最好的方法，再加上这个著名的算法将有几十个完美的实现。这是我的，很容易理解
def sub_partition(array, start, end, idx_pivot):
'returns the position where the pivot winds up'
if not (start <= idx_pivot <= end):
raise ValueError('idx pivot must be between start and end')
array[start], array[idx_pivot] = array[idx_pivot], array[start]
pivot = array[start]
i = start + 1
j = start + 1
while j <= end:
if array[j] <= pivot:
array[j], array[i] = array[i], array[j]
i += 1
j += 1
array[start], array[i - 1] = array[i - 1], array[start]
return i - 1
def quicksort(array, start=0, end=None):
if end is None:
end = len(array) - 1
if end - start < 1:
return
idx_pivot = random.randint(start, end)
i = sub_partition(array, start, end, idx_pivot)
#print array, i, idx_pivot
quicksort(array, start, i - 1)
quicksort(array, i + 1, end)好的，首先是分区子例程的分离函数。它采用数组、感兴趣的起始点和结束点以及轴心的索引。这个函数应该是清晰的
然后，快速排序第一次在整个数组上调用分区子例程；然后递归地调用它自己来对透视之前的所有内容以及之后的所有内容进行排序。
如果你不明白什么，就问一问
Stack Overflow用户
发布于 2014-04-04 18:03:39
我最近开始学习python，下面是我使用python实现快速排序的尝试。希望对您有所帮助。欢迎反馈:)
#!/usr/bin/python
Array = [ 3,7,2,8,1,6,8,9,6,9]
def partition(a, left, right):
pivot = left + (right - left)/2
a[left],a[pivot] = a[pivot], a[left] # swap
pivot = left
left += 1
while right >= left :
while left <= right and a[left] <= a[pivot] :
left += 1
while left <= right and a[right] > a[pivot] :
right -= 1
if left <= right:
a[left] , a[right] = a[right], a[left] # swap
left += 1
right -= 1
else:
break
a[pivot], a[right] = a[right] , a[pivot]
return right
def quicksort(array , left,right):
if left >= right:
return
if right - left == 1:
if array[right] < array[left]:
array[right], array[left] = array[left] , array[right]
return
pivot = partition(array, left, right)
quicksort(array, left, pivot -1)
quicksort(array, pivot+1,right)
def main():
quicksort(Array, 0 , len(Array) -1)
print Array
main() Stack Overflow用户
发布于 2016-01-22 07:38:15
下面是另一个实现：
def quicksort(alist):
if len(alist) <= 1:
return alist
return part(alist,0,len(alist)-1)
def part(alist,start,end):
pivot = alist[end]
border = start
if start < end:
for i in range(start,end+1):
if alist[i] <= pivot:
alist[border], alist[i] = alist[i], alist[border]
if i != end:
border += 1
part(alist,start,border-1)
part(alist,border+1,end)
return alist 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/17773516
复制相关文章
相似问题
腾讯云开发者
