Python解決快速排序

遞歸

def partition_v2(start_index, end_index, array=None):
    # 取第一個位置的元素作為基準元素（也可以選擇随機位置）
    if array is None:
        array = []
    pivot = array[start_index]
    mark = start_index
    for i in range(start_index + 1, end_index + 1):
        if array[i] < pivot:
            mark += 1
            array[mark], array[i] = array[i], array[mark]
    array[start_index] = array[mark]
    array[mark] = pivot
    return mark


def quick_sort(start_index, end_index, array=None):
    # 遞歸結束條件：startIndex大等于endIndex的時候
    if array is None:
        array = []
    if start_index >= end_index:
        return
    # 得到基準元素位置
    pivot_index = partition_v2(start_index, end_index, array)
    # 根據基準元素，分成兩部分遞歸排序
    quick_sort(start_index, pivot_index - 1, array)
    quick_sort(pivot_index + 1, end_index, array)


if __name__ == '__main__':
    my_array = list([3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11])
    quick_sort(0, len(my_array) - 1, my_array)
    print(my_array)

           

棧

def partition(start_index, end_index, array=None):
    # 取第一個位置的元素作為基準元素（也可以選擇随機位置）
    if array is None:
        array = []
    pivot = array[start_index]
    mark = start_index
    for i in range(start_index + 1, end_index + 1):
        if array[i] < pivot:
            mark += 1
            p = array[mark]
            array[mark] = array[i]
            array[i] = p
    array[start_index] = array[mark]
    array[mark] = pivot
    return mark


def quick_sort(start_index, end_index, array=None):
    # 用一個集合棧來代替遞歸的函數棧
    if array is None:
        array = []
    quick_sort_stack = []
    # 整個數列的起止下标，以哈希的形式入棧
    root_param = {"startIndex": start_index, "endIndex": end_index}
    quick_sort_stack.append(root_param)

    # 循環結束條件：棧為空時結束
    while len(quick_sort_stack) > 0:
        # 棧頂元素出棧，得到起止下标
        param = quick_sort_stack.pop()
        # 得到基準元素位置
        pivot_index = partition(param.get("startIndex"), param.get("endIndex"), array)
        # 根據基準元素分成兩部分, 把每一部分的起止下标入棧
        if param.get("startIndex") < pivot_index - 1:
            left_param = {"startIndex": param.get("startIndex"), "endIndex": pivot_index - 1}
            quick_sort_stack.append(left_param)
        if pivot_index + 1 < param.get("endIndex"):
            right_param = {"startIndex": pivot_index + 1, "endIndex": param.get("endIndex")}
            quick_sort_stack.append(right_param)


if __name__ == '__main__':
    my_array = list([3, 4, 14, 1, 5, 6, 7, 8, 1, -1, 0, 9, 11])
    quick_sort(0, len(my_array) - 1, my_array)
    print(my_array)