python写的快速排序动态演示程序

python写的快速排序动态演示程序

import matplotlib.pyplot as plt
import random

def quick_sort(data, left, right):
    if left >= right:
        return

    pivot = data[random.randint(left, right)]
    i, j = left, right

    while i <= j:
        while data[i] < pivot:
            i += 1
        while data[j] > pivot:
            j -= 1
        if i <= j:
            data[i], data[j] = data[j], data[i]
            i += 1
            j -= 1

    quick_sort(data, left, j)
    quick_sort(data, i, right)

def show_sorting_process(data):
    fig, ax = plt.subplots()
    ax.bar(range(len(data)), data)
    ax.set_xlim(0, len(data))
    ax.set_ylim(0, max(data) + 10)
    plt.title('Quick Sort')
    plt.show(block=False)

    quick_sort_animation(data, 0, len(data)-1, ax)

    plt.show()

def quick_sort_animation(data, left, right, ax):
    if left >= right:
        return

    pivot = data[random.randint(left, right)]
    i, j = left, right

    while i <= j:
        while data[i] < pivot:
            i += 1
        while data[j] > pivot:
            j -= 1
        if i <= j:
            data[i], data[j] = data[j], data[i]
            i += 1
            j -= 1

        # update the bar chart
        color = ['b'] * len(data)
        color[i-1] = 'r'
        color[j+1] = 'g'
        ax.clear()
        ax.bar(range(len(data)), data, color=color)
        ax.set_xlim(0, len(data))
        ax.set_ylim(0, max(data) + 10)
        plt.title('Quick Sort (Pivot = {})'.format(pivot))
        for k in range(len(data)):
            plt.text(k, data[k] + 1, data[k], horizontalalignment='center', fontweight='bold', color='black')
        plt.text(i-1, data[i-1] + 5, str(data[i-1]), horizontalalignment='center', fontweight='bold', color='black')
        plt.text(j+1, data[j+1] + 5, str(data[j+1]), horizontalalignment='center', fontweight='bold', color='white')
        plt.pause(1)

    quick_sort_animation(data, left, j, ax)
    quick_sort_animation(data, i, right, ax)

if __name__ == '__main__':
    # Generate random data
    data = [random.randint(0, 100) for _ in range(10)]
    print('Unsorted data:', data)

    # Show the sorting process
    show_sorting_process(data)

    # Sort the data using quick sort
    quick_sort(data, 0, len(data)-1)

    print('Sorted data:', data)

在这个代码中，我们定义了一个名为 partition 的函数来执行分割操作。在分割过程中，我们将最后一个元素作为枢轴元素，然后遍历数组，将小于枢轴元素的元素放在数组左侧，将大于枢轴元素的元素放在数组右侧，并将枢轴元素移到正确的位置上。分割操作完成后，我们递归调用 quick_sort_animation 函数来排序左子数组和右子数组。

在 quick_sort_animation 函数中，我们首先使用 partition 函数将数组分割成两个子数组，然后用 matplotlib 显示当前状态的柱状图。在显示柱状图时，我们将枢轴元素的颜色设置为绿色。接着，我们对左子数组和右子数组分别递归调用 quick_sort_animation 函数，直到整个数组有序。在显示柱状图时，我们使用 plt.pause 函数来控制动画的速度。