import React, { useState, useEffect, useRef, useMemo, useCallback } from 'react'; import { motion, AnimatePresence } from 'framer-motion'; import { Play, Pause, RotateCcw, BarChart3, Settings2, Info } from 'lucide-react'; // ========================================== // Constants & Config // ========================================== const WIDTH = 1200; const HEIGHT = 700; const ARRAY_SIZE = 40; const MIN_VAL = 10; const MAX_VAL = 500; const BAR_WIDTH = 20; const GAP = 8; // Colors const COLOR_BG = '#0f172a'; const COLOR_PRIMARY = '#3b82f6'; // Blue-500 const COLOR_COMPARE = '#fbbf24'; // Amber-400 const COLOR_SWAP = '#ef4444'; // Red-500 const COLOR_SORTED = '#10b981'; // Emerald-500 const COLOR_PIVOT = '#a855f7'; // Purple-500 const COLOR_AUX = '#f472b6'; // Pink-400 // Algorithm Types type AlgoType = 'bubble' | 'selection' | 'insertion' | 'quick' | 'merge' | 'heap' | 'shell'; const ALGO_INFO: Record = { bubble: { name: '冒泡排序', desc: '两两比较相邻元素，大值下沉，小值上浮', complexity: 'O(n²)' }, selection: { name: '选择排序', desc: '每次从未排序区间找到最小值，放到已排序区间末尾', complexity: 'O(n²)' }, insertion: { name: '插入排序', desc: '将元素插入到已排序区间的正确位置', complexity: 'O(n²)' }, quick: { name: '快速排序', desc: '选定基准值(Pivot)，分区递归排序', complexity: 'O(n log n)' }, merge: { name: '归并排序', desc: '分治法，递归将数组减半排序再合并', complexity: 'O(n log n)' }, heap: { name: '堆排序', desc: '利用大顶堆性质，不断移除堆顶元素', complexity: 'O(n log n)' }, shell: { name: '希尔排序', desc: '缩小增量排序，是插入排序的改进版', complexity: 'O(n log n) ~ O(n²)' }, }; // ========================================== // Generator Algorithms // ========================================== // Each generator yields state: { arr, compare: [], swap: [], sorted: [], pivot: number | null } function* bubbleSort(arr: number[]) { const n = arr.length; let sorted: number[] = []; for (let i = 0; i < n - 1; i++) { for (let j = 0; j < n - i - 1; j++) { yield { arr: [...arr], compare: [j, j + 1], swap: [], sorted: [...sorted], pivot: null }; if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; yield { arr: [...arr], compare: [], swap: [j, j + 1], sorted: [...sorted], pivot: null }; } } sorted.push(n - 1 - i); } sorted.push(0); yield { arr: [...arr], compare: [], swap: [], sorted: [...sorted], pivot: null }; } function* selectionSort(arr: number[]) { const n = arr.length; let sorted: number[] = []; for (let i = 0; i < n - 1; i++) { let minIdx = i; for (let j = i + 1; j < n; j++) { yield { arr: [...arr], compare: [j, minIdx], swap: [], sorted: [...sorted], pivot: i }; if (arr[j] < arr[minIdx]) { minIdx = j; } } if (minIdx !== i) { [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]]; yield { arr: [...arr], compare: [], swap: [i, minIdx], sorted: [...sorted], pivot: null }; } sorted.push(i); } sorted.push(n - 1); yield { arr: [...arr], compare: [], swap: [], sorted: [...sorted], pivot: null }; } function* insertionSort(arr: number[]) { const n = arr.length; let sorted: number[] = [0]; // First element technically sorted for (let i = 1; i < n; i++) { let key = arr[i]; let j = i - 1; yield { arr: [...arr], compare: [i], swap: [], sorted: [...sorted], pivot: i }; while (j >= 0 && arr[j] > key) { yield { arr: [...arr], compare: [j, j+1], swap: [], sorted: [...sorted], pivot: i }; arr[j + 1] = arr[j]; yield { arr: [...arr], compare: [], swap: [j, j+1], sorted: [...sorted], pivot: i }; j = j - 1; } arr[j + 1] = key; sorted.push(i); yield { arr: [...arr], compare: [], swap: [j+1], sorted: [...sorted], pivot: null }; } // All sorted yield { arr: [...arr], compare: [], swap: [], sorted: Array.from({length: n}, (_, k) => k), pivot: null }; } function* quickSort(arr: number[]) { const n = arr.length; // Helper generator for recursion function* partition(low: number, high: number) { let pivot = arr[high]; let i = low - 1; for (let j = low; j < high; j++) { yield { arr: [...arr], compare: [j, high], swap: [], sorted: [], pivot: high }; if (arr[j] < pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; yield { arr: [...arr], compare: [], swap: [i, j], sorted: [], pivot: high }; } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; yield { arr: [...arr], compare: [], swap: [i+1, high], sorted: [], pivot: null }; return i + 1; } function* qs(low: number, high: number): Generator { if (low < high) { let pi = yield* partition(low, high); yield* qs(low, pi - 1); yield* qs(pi + 1, high); } } yield* qs(0, n - 1); yield { arr: [...arr], compare: [], swap: [], sorted: Array.from({length: n}, (_, k) => k), pivot: null }; } function* shellSort(arr: number[]) { const n = arr.length; for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) { for (let i = gap; i < n; i++) { let temp = arr[i]; let j; for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) { yield { arr: [...arr], compare: [j, j-gap], swap: [], sorted: [], pivot: gap }; arr[j] = arr[j - gap]; yield { arr: [...arr], compare: [], swap: [j, j-gap], sorted: [], pivot: gap }; } arr[j] = temp; yield { arr: [...arr], compare: [], swap: [j], sorted: [], pivot: gap }; } } yield { arr: [...arr], compare: [], swap: [], sorted: Array.from({length: n}, (_, k) => k), pivot: null }; } function* heapSort(arr: number[]) { const n = arr.length; let sorted: number[] = []; function* heapify(n: number, i: number): Generator { let largest = i; let l = 2 * i + 1; let r = 2 * i + 2; if (l < n) { yield { arr: [...arr], compare: [l, largest], swap: [], sorted: [...sorted], pivot: i }; if (arr[l] > arr[largest]) largest = l; } if (r < n) { yield { arr: [...arr], compare: [r, largest], swap: [], sorted: [...sorted], pivot: i }; if (arr[r] > arr[largest]) largest = r; } if (largest !== i) { [arr[i], arr[largest]] = [arr[largest], arr[i]]; yield { arr: [...arr], compare: [], swap: [i, largest], sorted: [...sorted], pivot: null }; yield* heapify(n, largest); } } for (let i = Math.floor(n / 2) - 1; i >= 0; i--) { yield* heapify(n, i); } for (let i = n - 1; i > 0; i--) { [arr[0], arr[i]] = [arr[i], arr[0]]; yield { arr: [...arr], compare: [], swap: [0, i], sorted: [...sorted], pivot: null }; sorted.unshift(i); // Add to sorted list (visual only) yield* heapify(i, 0); } sorted.unshift(0); yield { arr: [...arr], compare: [], swap: [], sorted: Array.from({length: n}, (_, k) => k), pivot: null }; } // In-place Merge Sort Simulation for visualization simplicity // Real merge sort uses aux array, here we simulate swaps/inserts for visual effect function* mergeSort(arr: number[]) { // We will use a recursive structure that works on the array // To visualize properly we yield states const n = arr.length; function* merge(start: number, mid: number, end: number) { let start2 = mid + 1; if (arr[mid] <= arr[start2]) return; while (start <= mid && start2 <= end) { yield { arr: [...arr], compare: [start, start2], swap: [], sorted: [], pivot: null }; if (arr[start] <= arr[start2]) { start++; } else { let value = arr[start2]; let index = start2; // Shift all the elements between element 1 and element 2, right by 1. while (index !== start) { arr[index] = arr[index - 1]; // Visualizing the shift is chaotic, let's just yield the result of the shift step occasionally index--; } arr[start] = value; yield { arr: [...arr], compare: [], swap: [start, start2], sorted: [], pivot: null }; start++; mid++; start2++; } } } function* ms(l: number, r: number): Generator { if (l < r) { let m = l + Math.floor((r - l) / 2); yield* ms(l, m); yield* ms(m + 1, r); yield* merge(l, m, r); } } yield* ms(0, n - 1); yield { arr: [...arr], compare: [], swap: [], sorted: Array.from({length: n}, (_, k) => k), pivot: null }; } // ========================================== // Main Component // ========================================== export default function SortingVisualizer() { // -- State -- const [activeTab, setActiveTab] = useState('bubble'); const [isPlaying, setIsPlaying] = useState(false); const [speed, setSpeed] = useState(50); // ms delay const [progress, setProgress] = useState(0); // Just for stats // Sorting State const [arr, setArr] = useState([]); const [compareIdx, setCompareIdx] = useState([]); const [swapIdx, setSwapIdx] = useState([]); const [sortedIdx, setSortedIdx] = useState([]); const [pivotIdx, setPivotIdx] = useState(null); // Stats const [stats, setStats] = useState({ comparisons: 0, swaps: 0 }); // Refs for Animation const generatorRef = useRef | null>(null); const timerRef = useRef(null); const lastFrameTime = useRef(0); // -- Init -- const generateRandomArray = useCallback(() => { return Array.from({ length: ARRAY_SIZE }, () => Math.floor(Math.random() * (MAX_VAL - MIN_VAL) + MIN_VAL)); }, []); const reset = useCallback(() => { const newArr = generateRandomArray(); setArr(newArr); setCompareIdx([]); setSwapIdx([]); setSortedIdx([]); setPivotIdx(null); setStats({ comparisons: 0, swaps: 0 }); setProgress(0); setIsPlaying(false); // Initialize generator switch (activeTab) { case 'bubble': generatorRef.current = bubbleSort([...newArr]); break; case 'selection': generatorRef.current = selectionSort([...newArr]); break; case 'insertion': generatorRef.current = insertionSort([...newArr]); break; case 'quick': generatorRef.current = quickSort([...newArr]); break; case 'merge': generatorRef.current = mergeSort([...newArr]); break; case 'heap': generatorRef.current = heapSort([...newArr]); break; case 'shell': generatorRef.current = shellSort([...newArr]); break; } }, [activeTab, generateRandomArray]); // Initial load useEffect(() => { reset(); return () => stopLoop(); }, [reset]); // -- Animation Loop -- const stopLoop = () => { if (timerRef.current) { cancelAnimationFrame(timerRef.current); timerRef.current = null; } }; const step = useCallback(() => { if (!generatorRef.current) return; const { value, done } = generatorRef.current.next(); if (done) { setIsPlaying(false); setCompareIdx([]); setSwapIdx([]); setPivotIdx(null); setSortedIdx(Array.from({length: ARRAY_SIZE}, (_, k) => k)); return; } if (value) { setArr(value.arr); setCompareIdx(value.compare); setSwapIdx(value.swap); setSortedIdx(value.sorted); setPivotIdx(value.pivot); setStats(prev => ({ comparisons: prev.comparisons + (value.compare.length > 0 ? 1 : 0), swaps: prev.swaps + (value.swap.length > 0 ? 1 : 0) })); setProgress(p => p + 1); } }, []); useEffect(() => { if (isPlaying) { const loop = (timestamp: number) => { if (timestamp - lastFrameTime.current >= speed) { step(); lastFrameTime.current = timestamp; } timerRef.current = requestAnimationFrame(loop); }; timerRef.current = requestAnimationFrame(loop); } else { stopLoop(); } return () => stopLoop(); }, [isPlaying, speed, step]); // -- Helpers -- const togglePlay = () => setIsPlaying(!isPlaying); // Calculate bar positions const totalWidth = ARRAY_SIZE * (BAR_WIDTH + GAP) - GAP; const startX = (WIDTH - totalWidth) / 2; // -- Styles -- const containerStyle: React.CSSProperties = { width: WIDTH, height: HEIGHT, position: 'relative', backgroundColor: COLOR_BG, color: '#fff', fontFamily: '"JetBrains Mono", "Segoe UI", monospace', overflow: 'hidden', userSelect: 'none', display: 'flex', flexDirection: 'column', }; const controlBarStyle: React.CSSProperties = { position: 'absolute', bottom: 0, left: 0, width: '100%', height: '80px', background: 'rgba(15, 23, 42, 0.9)', backdropFilter: 'blur(10px)', borderTop: '1px solid #334155', display: 'flex', alignItems: 'center', justifyContent: 'space-between', padding: '0 40px', zIndex: 20 }; const headerStyle: React.CSSProperties = { position: 'absolute', top: 0, left: 0, width: '100%', height: '80px', display: 'flex', alignItems: 'center', justifyContent: 'space-between', padding: '0 30px', zIndex: 20, background: 'linear-gradient(to bottom, rgba(15,23,42,1), rgba(15,23,42,0))' }; const btnStyle = (active: boolean): React.CSSProperties => ({ background: active ? COLOR_PRIMARY : 'rgba(255,255,255,0.05)', border: `1px solid ${active ? COLOR_PRIMARY : 'rgba(255,255,255,0.1)'}`, color: active ? '#fff' : '#94a3b8', padding: '6px 12px', borderRadius: '6px', cursor: 'pointer', fontSize: '12px', fontWeight: 600, marginLeft: '8px', transition: 'all 0.2s', outline: 'none', display: 'flex', alignItems: 'center', gap: '6px' }); const iconBtnStyle: React.CSSProperties = { background: 'transparent', border: '1px solid rgba(255,255,255,0.2)', color: '#fff', width: '40px', height: '40px', borderRadius: '8px', cursor: 'pointer', display: 'flex', alignItems: 'center', justifyContent: 'center', transition: 'all 0.2s' }; const statItemStyle: React.CSSProperties = { display: 'flex', flexDirection: 'column', alignItems: 'flex-start', marginRight: '24px' }; const statLabelStyle: React.CSSProperties = { fontSize: '10px', color: '#94a3b8', textTransform: 'uppercase', letterSpacing: '1px' }; const statValueStyle: React.CSSProperties = { fontSize: '18px', fontWeight: 700, color: '#f8fafc', fontVariantNumeric: 'tabular-nums' }; return (

{/* Background Grid SVG */} {/* Header */}

AlgoViz // 算法可视化

{(Object.keys(ALGO_INFO) as AlgoType[]).map((key) => ( ))}

{/* Main Visualization Area */}

{/* Info Overlay */}

{ALGO_INFO[activeTab].name}

{ALGO_INFO[activeTab].desc}

时间复杂度: {ALGO_INFO[activeTab].complexity}

{/* Legend */}

{[ { l: '未排序', c: COLOR_PRIMARY }, { l: '比较中', c: COLOR_COMPARE }, { l: '交换/写', c: COLOR_SWAP }, { l: '已排序', c: COLOR_SORTED }, { l: '基准/堆顶', c: COLOR_PIVOT } ].map(item => (

{item.l}

))}

{/* SVG Bars */}

{/* Control Bar */}

比较次数 {stats.comparisons}

交换次数 {stats.swaps}

{/* Speed Control */}

速度 setSpeed(201 - parseInt(e.target.value))} style={{ width: '100px', cursor: 'pointer', accentColor: COLOR_PRIMARY }} />

); }