用分治法实现快速排序的可视化代码

以下是使用Python实现快速排序可视化的代码，基于分治法实现：

import pygame
import random

# Initialize Pygame
pygame.init()

# Set the window dimensions
WINDOW_WIDTH = 800
WINDOW_HEIGHT = 600

# Set the colors
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLUE = (0, 0, 255)

# Set the font
font = pygame.font.SysFont('Calibri', 25, True, False)

# Set the screen
screen = pygame.display.set_mode((WINDOW_WIDTH, WINDOW_HEIGHT))
pygame.display.set_caption("Quick Sort Visualization")

# Set the clock
clock = pygame.time.Clock()

# Set the array
array = [random.randint(10, 500) for i in range(50)]

# Set the pivot color
PIVOT_COLOR = BLUE

# Set the partition color
PARTITION_COLOR = GREEN

# Set the sorted color
SORTED_COLOR = RED

# Set the unsorted color
UNSORTED_COLOR = WHITE

# Set the function for quick_sort
def quick_sort(array, start, end):
    if start < end:
        pivot_index = partition(array, start, end)
        quick_sort(array, start, pivot_index - 1)
        quick_sort(array, pivot_index + 1, end)

# Set the function for partition
def partition(array, start, end):
    pivot_index = start
    pivot_value = array[end]
    for i in range(start, end):
        if array[i] < pivot_value:
            array[i], array[pivot_index] = array[pivot_index], array[i]
            pivot_index += 1
    array[pivot_index], array[end] = array[end], array[pivot_index]
    return pivot_index

# Set the function for draw_text
def draw_text(text, color, x, y):
    text_surface = font.render(text, True, color)
    screen.blit(text_surface, (x, y))

# Set the function for draw_array
def draw_array(array):
    for i in range(len(array)):
        pygame.draw.rect(screen, UNSORTED_COLOR, (i * 15 + 50, WINDOW_HEIGHT - array[i], 10, array[i]))

# Set the function for draw_partition
def draw_partition(array, start, end):
    for i in range(start, end + 1):
        pygame.draw.rect(screen, PARTITION_COLOR, (i * 15 + 50, WINDOW_HEIGHT - array[i], 10, array[i]))

# Set the function for draw_sorted
def draw_sorted(array, start, end):
    for i in range(start, end + 1):
        pygame.draw.rect(screen, SORTED_COLOR, (i * 15 + 50, WINDOW_HEIGHT - array[i], 10, array[i]))

# Set the function for draw_pivot
def draw_pivot(array, pivot_index):
    pygame.draw.rect(screen, PIVOT_COLOR, (pivot_index * 15 + 50, WINDOW_HEIGHT - array[pivot_index], 10, array[pivot_index]))

# Set the function for main
def main():
    # Set the initial values
    start = 0
    end = len(array) - 1
    quick_sort(array, start, end)
    done = False
    pivot_index = -1
    while not done:
        # Check for events
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                done = True
        # Clear the screen
        screen.fill(BLACK)
        # Draw the text
        draw_text("Quick Sort Visualization", WHITE, 50, 25)
        # Draw the array
        draw_array(array)
        # Draw the partition
        if pivot_index != -1:
            draw_partition(array, start, pivot_index - 1)
            draw_partition(array, pivot_index + 1, end)
        # Draw the sorted
        if pivot_index != -1:
            draw_sorted(array, start, pivot_index - 1)
            draw_sorted(array, pivot_index + 1, end)
        # Draw the pivot
        if pivot_index != -1:
            draw_pivot(array, pivot_index)
        # Update the screen
        pygame.display.flip()
        # Delay the loop
        clock.tick(30)
        # Call quick_sort
        if pivot_index == -1:
            pivot_index = start
        elif pivot_index == end:
            pivot_index = -1
        elif array[pivot_index] > array[pivot_index + 1]:
            array[pivot_index], array[pivot_index + 1] = array[pivot_index + 1], array[pivot_index]
            pivot_index += 1
        else:
            pivot_index += 1

# Call main
if __name__ == '__main__':
    main()

这个可视化程序使用Pygame库绘制图形，生成一个包含随机整数的列表并将其进行快速排序。在每一步排序中，程序将突出显示分区中的元素、排序的元素和枢轴元素，并在排序过程中更新显示。