时间戳

首页 > 解决方案 > Python 快速排序实现

python - Python 快速排序实现

问题描述

我尝试在 Python 中实现递归快速排序，但它不起作用。我知道存在数组未排序的问题，因为枢轴始终高于i，这导致问题i始终等于m。

def partition(array):
    pivot = array[-1]
    m = 0

    for i in range(len(array) - 1):
        if array[i] < pivot:
            array[i], array[m] = array[m], array[i]
            m += 1

        else:
            continue

    array[m], array[len(array)-1] = array[len(array)-1], array[m]

    return m

def quicksort(array):
    if len(array) > 1:
        m = partition(array)
        quicksort(array[:m])
        quicksort(array[m+1:])
        return array


def main():
    testarray = [3,6,2,4,5,1,9,8,7,10,14]
    print(quicksort(testarray))

if __name__ == '__main__':
    main()

标签： pythonsorting

解决方案

两件事情。首先，当它的长度为 1 时你忘记了返回array，其次你在返回之前实际上并没有进行修改array。这将起作用。

def quicksort(array):
    if len(array) > 1:
        m = partition(array)

        # return the concatenation of the two sorted arrays
        return quicksort(array[:m]) + quicksort(array[m:])

    else:
        return array

推荐阅读