# GESP等级：四级 | GESP Python 四级考点 """ ================================================== 选择排序 vs 插入排序 —— turtle对比动画 面向7-10岁少儿编程教学 ================================================== 使用方法： 1. 直接运行本文件，左右两屏同时展示两种排序 2. 左边 = 选择排序（选秀），右边 = 插入排序（摸牌） 3. 可以修改 DATA 列表来改变排序数据 口诀： "选择排序选最矮，放到前排再继续" "插入排序像摸牌，新牌插入合适位" ================================================== """ import turtle import time import random # ================================================== # 配置区 —— 你可以在这里修改参数！ # ================================================== # 要排序的数据 DATA = [5, 3, 1, 4, 2] # 排序速度（数字越小越快） SPEED = 0.3 # 颜色列表 COLORS = ["red", "orange", "gold", "green", "blue", "purple", "pink"] # ================================================== # turtle设置 —— 创建两个画布左右对比 # ================================================== # 左边画布（选择排序） screen_left = turtle.Screen() screen_left.setup(1600, 500) screen_left.title("选择排序（选秀） vs 插入排序（摸牌）") screen_left.bgcolor("white") screen_left.tracer(0) screen_left.colormode(255) # 创建左画笔 t_left = turtle.Turtle() t_left.speed(0) t_left.hideturtle() # 创建右画笔 t_right = turtle.Turtle() t_right.speed(0) t_right.hideturtle() # 信息画笔 info = turtle.Turtle() info.speed(0) info.hideturtle() info.penup() # 统计画笔 stats = turtle.Turtle() stats.speed(0) stats.hideturtle() stats.penup() # ================================================== # 绘图工具 # ================================================== def draw_bar(t, x, height, color, bar_width=25): """画单个柱子""" t.penup() t.goto(x, -180) t.pendown() t.fillcolor(color) t.begin_fill() for _ in range(2): t.forward(bar_width) t.left(90) t.forward(height * 10) t.left(90) t.end_fill() # 在柱子上方写数字 t.penup() t.goto(x + bar_width / 2, -180 + height * 10 + 5) t.write(str(height), align="center", font=("Arial", 10, "bold")) def draw_array(t, arr, start_x, bar_width=25, highlight=None, special=None): """画一组柱子""" t.clear() n = len(arr) gap = 4 total_width = n * (bar_width + gap) for i in range(n): color = COLORS[i % len(COLORS)] # 高亮正在操作的元素 if highlight and i in highlight: color = "yellow" if special and i in special: color = "lime green" x = start_x + i * (bar_width + gap) draw_bar(t, x, arr[i], color, bar_width) screen_left.update() def draw_title(): """在屏幕上方显示标题""" info.goto(-350, 220) info.write("选择排序（选秀）", align="center", font=("Arial", 18, "bold")) info.goto(350, 220) info.write("插入排序（摸牌）", align="center", font=("Arial", 18, "bold")) info.goto(0, 200) info.write("👇 同一份数据，两种不同的排序方法！", align="center", font=("Arial", 14, "normal")) def draw_stats(sel_comp, ins_comp, sel_swap, ins_shift): """显示统计信息（比较次数和交换/移动次数）""" stats.goto(-350, -220) stats.write(f"比较: {sel_comp}次 交换: {sel_swap}次", align="center", font=("Arial", 12, "normal")) stats.goto(350, -220) stats.write(f"比较: {ins_comp}次 后移: {ins_shift}次", align="center", font=("Arial", 12, "normal")) def draw_round_info(text, x, y=-240): """在指定位置显示轮次信息""" stats.goto(x, y) stats.write(text, align="center", font=("Arial", 11, "normal")) def draw_finished(t, arr, start_x, msg, x_msg): """显示排序完成的效果""" bar_width = 25 gap = 4 n = len(arr) for i in range(n): x = start_x + i * (bar_width + gap) draw_bar(t, x, arr[i], "gold", bar_width) screen_left.update() info.goto(x_msg, 180) info.write(f"🎉 {msg}", align="center", font=("Arial", 14, "bold")) # ================================================== # 选择排序（带可视化） # ================================================== def selection_sort_visual(arr, start_x): """ 选择排序 + turtle可视化 口诀：每轮找最小的，放到最前面 """ n = len(arr) compare_count = 0 swap_count = 0 for i in range(n - 1): min_idx = i draw_round_info(f"第{i+1}轮：找最小", start_x) # 在未排序部分找最小 for j in range(i + 1, n): # 高亮当前比较的两个元素 draw_array(t_left, arr, start_x, highlight=[min_idx, j]) compare_count += 1 draw_stats(compare_count, 0, swap_count, 0) time.sleep(SPEED / 2) if arr[j] < arr[min_idx]: min_idx = j # 标记新的最小值 draw_array(t_left, arr, start_x, special=[min_idx]) time.sleep(SPEED / 4) # 交换（如果最小值不在当前位置） if min_idx != i: arr[i], arr[min_idx] = arr[min_idx], arr[i] swap_count += 1 draw_array(t_left, arr, start_x, special=[i]) draw_round_info(f"第{i+1}轮：{arr[i]}放到第{i+1}位 ✅", start_x) draw_stats(compare_count, 0, swap_count, 0) time.sleep(SPEED) else: draw_round_info(f"第{i+1}轮：{arr[i]}已经在正确位置 👍", start_x) time.sleep(SPEED / 2) # 全部排好 draw_finished(t_left, arr, start_x, "选择排序完成！", -350) return arr, compare_count, swap_count # ================================================== # 插入排序（带可视化） # ================================================== def insertion_sort_visual(arr, start_x): """ 插入排序 + turtle可视化 口诀：新牌插入到合适位置 """ n = len(arr) compare_count = 0 shift_count = 0 for i in range(1, n): key = arr[i] j = i - 1 draw_round_info(f"第{i}步：摸到{key}", start_x) # 标记取出的元素 draw_array(t_right, arr, start_x, special=[i]) time.sleep(SPEED) # 向前比较，后移元素 while j >= 0 and arr[j] > key: compare_count += 1 # 高亮正在比较的两个位置 draw_array(t_right, arr, start_x, highlight=[j, j + 1]) draw_stats(0, compare_count, 0, shift_count) time.sleep(SPEED / 2) # 后移 arr[j + 1] = arr[j] shift_count += 1 draw_array(t_right, arr, start_x, highlight=[j + 1]) draw_round_info(f"{arr[j]}往后移一位", start_x) draw_stats(0, compare_count, 0, shift_count) time.sleep(SPEED / 3) j -= 1 compare_count += 1 if j >= 0 else 0 # 最后一次循环条件判断也计数 # 插入 arr[j + 1] = key draw_array(t_right, arr, start_x, special=[j + 1]) draw_round_info(f"插入{key}到第{j+2}位 ✅", start_x) draw_stats(0, compare_count, 0, shift_count) time.sleep(SPEED) # 全部排好 draw_finished(t_right, arr, start_x, "插入排序完成！", 350) return arr, compare_count, shift_count # ================================================== # 辅助函数 # ================================================== def run_comparison(data): """运行两种排序的对比""" # 复制数据 arr1 = data.copy() arr2 = data.copy() # 计算起始位置 n = len(data) bar_width = 25 gap = 4 total_width = n * (bar_width + gap) left_start = -400 - total_width // 2 right_start = 400 - total_width // 2 # 画初始状态 draw_title() draw_array(t_left, arr1, left_start) draw_array(t_right, arr2, right_start) draw_stats(0, 0, 0, 0) time.sleep(1) # 同时运行两种排序 print("\n🎯 开始对比排序！") print("=" * 40) print(f"数据：{data}") print() print("▶️ 【左边】选择排序（选秀）开始...") sorted1, sel_comp, sel_swap = selection_sort_visual(arr1, left_start) print("\n▶️ 【右边】插入排序（摸牌）开始...") sorted2, ins_comp, ins_shift = insertion_sort_visual(arr2, right_start) # 显示最终对比结果 print("\n" + "=" * 50) print("📊 最终对比结果：") print(f" 选择排序：比较 {sel_comp} 次，交换 {sel_swap} 次") print(f" 插入排序：比较 {ins_comp} 次，后移 {ins_shift} 次") print(f" 结果：{sorted1}") print("=" * 50) def test_sorted_array(): """测试已排好序的数组（展示插入排序的优势）""" data = [1, 2, 3, 4, 5] print("\n🌟 测试已排好序的数据：") print(f"数据：{data}") arr1 = data.copy() arr2 = data.copy() left_start = -400 - 5 * 29 // 2 right_start = 400 - 5 * 29 // 2 draw_title() draw_array(t_left, arr1, left_start) draw_array(t_right, arr2, right_start) draw_stats(0, 0, 0, 0) time.sleep(1) sorted1, sel_comp, sel_swap = selection_sort_visual(arr1, left_start) sorted2, ins_comp, ins_shift = insertion_sort_visual(arr2, right_start) print(f"\n📊 结果：") print(f" 选择排序：比较 {sel_comp} 次") print(f" 插入排序：比较 {ins_comp} 次（哇！少了好多！）") def test_reversed_array(): """测试完全逆序的数组""" data = [5, 4, 3, 2, 1] print("\n🔥 测试完全逆序的数据：") print(f"数据：{data}") arr1 = data.copy() arr2 = data.copy() left_start = -400 - 5 * 29 // 2 right_start = 400 - 5 * 29 // 2 draw_title() draw_array(t_left, arr1, left_start) draw_array(t_right, arr2, right_start) draw_stats(0, 0, 0, 0) time.sleep(1) sorted1, sel_comp, sel_swap = selection_sort_visual(arr1, left_start) sorted2, ins_comp, ins_shift = insertion_sort_visual(arr2, right_start) print(f"\n📊 结果：") print(f" 选择排序：比较 {sel_comp} 次，交换 {sel_swap} 次") print(f" 插入排序：比较 {ins_comp} 次，后移 {ins_shift} 次") def on_click(x, y): """点击屏幕重新排序""" global DATA random.seed() DATA = [random.randint(1, 15) for _ in range(6)] info.clear() stats.clear() screen_left.update() run_comparison(DATA) # ================================================== # 主程序 # ================================================== if __name__ == "__main__": print("🌟 欢迎来到排序对比乐园！") print("=" * 40) print("左边：选择排序（选秀） | 右边：插入排序（摸牌）") print("=" * 40) print("当前数据：", DATA) print() # 运行对比 run_comparison(DATA) # 点击屏幕重新排序 screen_left.listen() screen_left.onclick(on_click) print("\n💡 提示：点击屏幕可以随机生成新数据！") print("💡 按 ESC 或关闭窗口退出程序") screen_left.mainloop()