快速排序

def quick_sort(a: list[int]) -> list[int]:
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    left = [x for x in a if x < pivot]
    middle = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

if __name__ == '__main__':
    a = [5, 3, 1, 2, 4]
    print(quick_sort(a))  # [1, 2, 3, 4, 5]
# 单向快速排序
def quick_sort(a: list[int], lo: int, hi: int):
    if lo >= hi:
        return
    index = partition(a, lo, hi)
    quick_sort(a, lo, index - 1)
    quick_sort(a, index + 1, hi)

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1
    for j in range(lo, hi):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i + 1], a[hi] = a[hi], a[i + 1]
    return i + 1

if __name__ == '__main__':
    a = [5, 3, 1, 2, 4]
    quick_sort(a, 0, len(a) - 1)
    print(a)  # [1, 2, 3, 4, 5]

递归部分:调用分区方法返回一个位置,然后以这个位置为分界,将数组分成两部分,递归的调用该方法

分区部分:好比一个人在最后一个位置,然后安排小弟1在开头前一位,小弟2从头开始遍历数组,当小弟2发现自己的值比老大还小,那么就让小弟1右移一位,并交换两个小弟的值,当小弟2遍历完成了,再让小弟1右移一位并和老大交换值

# 双向快速排序
from random import randint

def quick_sort(a: list[int], lo: int, hi: int):
    if lo >= hi:
        return
    index = partition(a, lo, hi)
    quick_sort(a, lo, index - 1)
    quick_sort(a, index + 1, hi)

def partition(a, lo, hi):
    r = randint(lo, hi)
    a[lo], a[r] = a[r], a[lo]
    pivot = a[lo]
    i = lo + 1
    j = hi
    while True:
        while a[i] < pivot:
            if i == hi:
                break
            i += 1
        while a[j] > pivot:
            if j == lo:
                break
            j -= 1
        if i >= j:
            break
        a[i], a[j] = a[j], a[i]

    a[lo], a[j] = a[j], a[lo]
    return j

if __name__ == '__main__':
    a = [5, 3, 1, 2, 4]
    quick_sort(a, 0, len(a) - 1)
    print(a)  # [1, 2, 3, 4, 5]

递归部分:同上

分区部分:好比一个人在第一个位置,然后安排小弟1在第一数组第二个位子,小弟2在最后一个位子,然后小弟1从左往右找比老大大的值,小弟2从右往左找比老大小的值,只要他两没碰头,然后交换两个小弟的值,当他们碰头后,交换老大和小弟2的值

03-22 10:50