数据结构（四）快速排序

# -*- coding: utf-8 -*-


def sort(arr, lo, hi):
    if hi <= lo:
        return

    # 分片
    mid = partition(arr, lo, hi)

    sort(arr, lo, mid - 1)
    sort(arr, mid + 1, hi)


def partition(arr, lo, hi):
    value = arr[lo]

    i = lo + 1
    j = hi
    while True:
        while arr[i] <= value and i != hi:
            i += 1
        while arr[j] > value and j != lo:
            j -= 1
        if i < j:
            # 交换 i、j 位置的值
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp
        else:
            # 交换 low、j 位置的值
            temp = arr[j]
            arr[j] = arr[lo]
            arr[lo] = temp
            break
    return j


arrTest = [10, 9, 7, 8, 3, 1]
sort(arrTest, 0, len(arrTest) - 1)
print(arrTest)