快速排序的Python实现

1、双指针法

def quick_sort(arr, start, end):
    # 递归结束条件
    if start >= end:
        return

    pivot = arr[start]
    left = start
    right = end

    while left != right:
        while right > left and arr[right] > pivot:
            right -= 1

        while left < right and arr[left] <= pivot:
            left += 1

        if left < right:
            arr[right], arr[left] = arr[left], arr[right]

    arr[start] = arr[left]
    arr[left] = pivot

    quick_sort(arr, start, left-1)
    quick_sort(arr, left+1, end)

2、单指针法

def quick_sort2(arr, start, end):
    # 递归结束条件
    if start >= end:
        return

    pivot = arr[start]
    mark = start
    cur = start

    while cur <= end:
        if arr[cur] < pivot:
            mark += 1
            arr[mark], arr[cur] = arr[cur], arr[mark]

        cur += 1

    arr[start] = arr[mark]
    arr[mark] = pivot

    quick_sort2(arr, start, mark-1)
    quick_sort2(arr, mark+1, end)