python挖坑法实现快排

快速排序

快速排序就是快

排序思路

• 取一个元素p（第一个元素），使元素p归位；
• 列表被p分成两部分，左边的数一定不大于p，右边的数一定不小于p；
• 递归完成排序。

Python代码示例:

lst = [5, 7, 4, 3, 1, 2, 9, 8]


def quick_sort(data, left, right):
    if left < right:
        mid = partition(data, left, right)
        quick_sort(data, left, mid - 1)
        quick_sort(data, mid + 1, right)


# 挖坑大法
# 此函数执行结束后，左边的数一定不大于tmp，右边的数一定不小于tmp
def partition(data, left, right):
    tmp = data[left]
    while left < right:
        while left < right and data[right] >= tmp:
            right -= 1
        data[left] = data[right]
        while left < right and data[left] <= tmp:
            left += 1
        data[right] = data[left]
    data[left] = tmp
    return left


quick_sort(lst, 0, len(lst) - 1)

print(lst)

# partition还有其它的写法，这里写的是比较简单的一种