python写的插入排序动态演示程序

python

写的插入排序动态演示程序

import matplotlib.pyplot as plt
import time
import random

def insertion_sort(data):
    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and data[j] > key:
            data[j+1] = data[j]
            j -= 1
        data[j+1] = key

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('Insertion Sort')
    plt.show(block=False)

    for i in range(1, len(data)):
        key = data[i]
        j = i - 1
        while j >= 0 and data[j] > key:
            # move
            color = ['b'] * len(data)
            color[j] = 'r'
            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('Insertion Sort (Round {})'.format(i))
            for k in range(len(data)):
                plt.text(k, data[k] + 1, data[k], horizontalalignment='center', fontweight='bold', color='black')
            plt.text(j, data[j] + 5, str(data[j]), horizontalalignment='center', fontweight='bold', color='white')
            plt.pause(1)

            data[j+1] = data[j]
            j -= 1

        data[j+1] = key

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

    plt.show()

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 insertion sort
    insertion_sort(data)

    print('Sorted data:', data)

在上面的代码中，我们使用了类似于冒泡排序的方法，将比较和移动过程分别表示出来。在移动过程中，我们使用红色的条形来表示当前正在移动的元素。同时，我们在每一轮结束后，在条形图上标出了当前轮次中最小值，以方便展示插入排序中的插入过程。