个人技术分享

学习选择排序的可视化实现（一）

选择排序的基本思路

开始：从数组的第一个元素开始，假设最小（或最大）元素就是第一个元素。
比较：遍历未排序的部分，找到实际的最小（或最大）元素。
交换：将找到的最小（或最大）元素与未排序部分的第一个元素交换位置。
重复：移动到下一个元素，重复步骤2和3，直到数组完全排序。

实现细节

在Rust中，我们可以通过以下步骤实现选择排序的可视化：

定义状态：首先，定义一个枚举SortState来表示排序的不同状态，如Idle、Sorting、Paused等。

实现选择排序步骤：创建一个函数selection_sort_step，该函数每次调用时执行一步选择排序。该函数需要记录当前的索引位置，并在每次调用时更新。

可视化设置：在主函数中，设置Piston窗口库创建可视化窗口，并初始化一组乱序数组。

事件循环：在Piston的事件循环中，根据当前的排序状态和用户输入（如开始、暂停、单步执行等），调用selection_sort_step函数执行排序步骤，并更新窗口以显示当前数组的状态。

绘制数组：每次循环时，根据数组中每个元素的值绘制对应的矩形条，以可视化地表示数组的当前状态。

extern crate piston_window;
use piston_window::*;

use std::time::{Duration, Instant};

#[derive(PartialEq)]
enum SortState {
    Idle,
    Sorting,
    Paused,
    Step,
}

fn selection_sort_step(numbers: &mut Vec<i32>, current_index: &mut usize) -> bool {
    if *current_index < numbers.len() - 1 {
        let mut min_index = *current_index;
        for i in (*current_index + 1)..numbers.len() {
            if numbers[i] < numbers[min_index] {
                min_index = i;
            }
        }
        numbers.swap(*current_index, min_index);
        *current_index += 1;
        true
    } else {
        false // 排序完成
    }
}

fn draw_numbers(window: &mut PistonWindow, e: &Event, numbers: &[i32], current_index: usize) {
    window.draw_2d(e, |c, g, _| {
        clear([1.0; 4], g); // 用白色清空背景
        let size = numbers.len();
        let window_size = c.get_view_size();
        let bar_width = window_size[0] / size as f64;

        for (i, &number) in numbers.iter().enumerate() {
            let x = i as f64 * bar_width;
            let y = window_size[1] - window_size[1] * (number as f64 / size as f64);

            rectangle(
                if i == current_index { [1.0, 0.0, 0.0, 1.0] } else { [0.0, 0.0, 1.0, 1.0] }, // 当前索引红色，其余蓝色
                [x, y, bar_width, window_size[1] - y],
                c.transform,
                g,
            );
        }
    });
}

fn main() {
    let mut window: PistonWindow = WindowSettings::new("Selection Sort Visualization", [800, 600])
        .exit_on_esc(true)
        .build()
        .unwrap();

    let mut numbers = vec![10, 5, 3, 8, 2, 6, 4, 7, 9, 1];
    let mut current_index = 0usize;
    let mut sort_state = SortState::Idle;
    let mut last_update_time = Instant::now();
    let update_delay = Duration::from_millis(500);

    while let Some(e) = window.next() {
        if let Some(Button::Keyboard(key)) = e.press_args() {
            match key {
                Key::S => sort_state = SortState::Sorting,
                Key::P => sort_state = SortState::Paused,
                Key::N => {
                    if sort_state == SortState::Paused || sort_state == SortState::Idle {
                        sort_state = SortState::Step;
                    }
                },
                Key::R => {
                    numbers = vec![10, 5, 3, 8, 2, 6, 4, 7, 9, 1];
                    current_index = 0;
                    sort_state = SortState::Idle;
                },
                _ => {}
            }
        }

        if sort_state == SortState::Sorting || sort_state == SortState::Step {
            if last_update_time.elapsed() >= update_delay {
                if !selection_sort_step(&mut numbers, &mut current_index) && sort_state == SortState::Sorting {
                    sort_state = SortState::Paused; // 排序完成自动暂停
                }
                last_update_time = Instant::now();
                if sort_state == SortState::Step {
                    sort_state = SortState::Paused; // 单步执行后暂停
                }
            }
        }

        draw_numbers(&mut window, &e, &numbers, current_index);
    }
}

优化版本：

extern crate piston_window;
use piston_window::*;
use std::time::{Duration, Instant};

#[derive(PartialEq)]
enum SortState {
    Idle,
    Sorting,
    Paused,
    Step,
}

fn selection_sort_step(numbers: &mut Vec<i32>, current_index: &mut usize) -> bool {
    if *current_index < numbers.len() - 1 {
        let mut min_index = *current_index;
        for i in (*current_index + 1)..numbers.len() {
            if numbers[i] < numbers[min_index] {
                min_index = i;
            }
        }
        numbers.swap(*current_index, min_index);
        *current_index += 1;
        true
    } else {
        false // 排序完成
    }
}

fn draw_numbers(window: &mut PistonWindow, e: &Event, numbers: &[i32], current_index: usize) {
    window.draw_2d(e, |c, g, _| {
        clear([1.0; 4], g); // 用白色清空背景
        let size = numbers.len();
        let window_size = c.get_view_size();
        let bar_width = window_size[0] / size as f64;

        for (i, &number) in numbers.iter().enumerate() {
            let x = i as f64 * bar_width;
            let y = window_size[1] - window_size[1] * (number as f64 / size as f64);

            rectangle(
                if i == current_index { [1.0, 0.0, 0.0, 1.0] } else { [0.0, 0.0, 1.0, 1.0] }, // 当前索引红色，其余蓝色
                [x, y, bar_width, window_size[1] - y],
                c.transform,
                g,
            );
        }
    });
}

fn main() {
    let mut window: PistonWindow = WindowSettings::new("Selection Sort Visualization", [800, 600])
        .exit_on_esc(true)
        .build()
        .unwrap();

    let mut numbers = vec![10, 5, 3, 8, 2, 6, 4, 7, 9, 1];
    let mut current_index = 0usize;
    let mut sort_state = SortState::Idle;
    let mut last_update_time = Instant::now();
    let update_delay = Duration::from_millis(500);

    while let Some(e) = window.next() {
        if let Some(Button::Keyboard(key)) = e.press_args() {
            match key {
                Key::S => sort_state = SortState::Sorting,
                Key::P => sort_state = SortState::Paused,
                Key::N => {
                    if sort_state == SortState::Paused || sort_state == SortState::Idle {
                        sort_state = SortState::Step;
                    }
                },
                Key::R => {
                    numbers = vec![10, 5, 3, 8, 2, 6, 4, 7, 9, 1]; // 可以考虑添加一个函数来生成随机或特定的数字序列
                    current_index = 0;
                    sort_state = SortState::Idle;
                },
                _ => {}
            }
        }

        if sort_state == SortState::Sorting || sort_state == SortState::Step {
            if last_update_time.elapsed() >= update_delay {
                if !selection_sort_step(&mut numbers, &mut current_index) && sort_state == SortState::Sorting {
                    sort_state = SortState::Paused; // 排序完成自动暂停
                }
                last_update_time = Instant::now();
                if sort_state == SortState::Step {
                    sort_state = SortState::Paused; // 单步执行后暂停
                }
            }
        }

        draw_numbers(&mut window, &e, &numbers, current_index);
    }
}