Python中的就地快速排序

Question

我不得不用自己选择的语言实现作业的快速排序算法，我选择了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的就地实现，所以我想最好问问。

Answer 1

下面是另一个实现：

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 

Answer 2

当然不是最好的方法，加上这个著名的算法将有几十个完美的实现。。这是我的，很容易理解

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)

好的，首先是分区子程序的一个独立函数。它需要阵列， 兴趣的起点和终点，以及轴的索引。这些功能应该是清楚的

快速排序然后在整个数组上第一次调用分区子例程；然后 调用recursevely本身，将所有内容按轴进行排序，然后再进行排序。

问你是否不明白

Answer 3

我最近开始学习python，下面是我使用python实现quicksort的尝试。希望能有所帮助。欢迎反馈：）

#!/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()