【花雕动手做】基于 Kitronik 可编程开发板之排序算法
Kitronik ARCADE 是一款由英国教育科技公司 Kitronik 精心打造的可编程游戏机开发板，专为编程教学与创客实践而设计。该设备原生支持微软的 MakeCode Arcade 平台，用户可通过图形化或 JavaScript 编程方式，轻松创建、下载并运行复古风格的街机游戏。它集成了彩色 LCD 显示屏、方向控制键、功能按键、蜂鸣器和震动马达等交互组件，提供完整的游戏输入输出体验。无论是初学者进行编程启蒙，还是创客群体开发交互式作品，Kitronik ARCADE 都能作为理想的硬件载体，助力创意实现。
凭借其开源友好、易于上手、兼容性强等特点，该开发板广泛应用于中小学编程课程、创客工作坊、游戏开发教学以及个人项目原型设计，深受教育者与技术爱好者的喜爱。
【花雕动手做】基于 Kitronik 可编程开发板之排序算法
作为学习、练习与尝试，这里创建一个排序算法的小游戏。打开网页版：https://arcade.makecode.com/，设置项目名称：排序算法
JavaScript 实验代码
const pauseDuration = 10;
interface SortingAlgorithm {
title: string;
algorithm: (values: number[]) => number[];
a?: number[];
place?: string;
}
let currCount = 26;
let currentRun = 0;
let ySegment: number;
let currentPlace: number;
let running: SortingAlgorithm[] = [];
let notRunning: SortingAlgorithm[] = [];
addExample("selection sort", sorts.selectionSort);
addExample("insertion sort", sorts.insertionSort);
addExample("bubble sort", sorts.bubbleSort);
addExample("shell sort", sorts.shellSort);
addExample("heap sort", sorts.heapSort);
addExample("quick sort", sorts.quickSort);
addExample("merge sort", sorts.mergeSort);
// Start off with two random algorithms running
for (let i = 0; i < 2; i++) {
moveRandom(notRunning, running);
}
start();
game.onPaint(() => {
running.forEach(function (value: SortingAlgorithm, index: number) {
drawCurrentState(value, currCount, ySegment, index * ySegment);
});
});
// start over with a new seed
controller.A.onEvent(ControllerButtonEvent.Pressed, () => {
start();
});
// remove a sorting algorithm from the group of running sorts
controller.left.onEvent(ControllerButtonEvent.Pressed, () => {
if (running.length > 1) {
moveRandom(running, notRunning)
start();
}
});
// display a new sorting algorithm if possible
controller.right.onEvent(ControllerButtonEvent.Pressed, () => {
if (notRunning.length > 0) {
moveRandom(notRunning, running)
start();
}
});
// increase the number of elements to sort if possible
controller.up.onEvent(ControllerButtonEvent.Pressed, function () {
if (currCount + 6 < screen.width / 2) {
currCount += 6;
start();
}
});
// decrease the number of elements to sort if possible
controller.down.onEvent(ControllerButtonEvent.Pressed, function () {
if (currCount > 6) {
currCount -= 6;
start();
}
})
function moveRandom<T>(a: T[], b: T[]) {
if (a.length > 0) {
const i = randint(0, a.length - 1);
b.push(a.removeAt(i));
}
}
function addExample(title: string, sortAlgorithm: (values: number[]) => number[]) {
let output: SortingAlgorithm = {
title: title,
algorithm: sortAlgorithm
}
notRunning.push(output);
}
function start() {
const r = new Math.FastRandom();
++currentRun;
currentPlace = 1;
ySegment = Math.floor(screen.height / running.length);
// clear old arrays to quickly cull other threads as much as possible;
// only merge sort will survive as it is not in place
running.forEach(v => {
while (v.a && v.a.length != 0)
v.a.pop();
});
// create a new starting array for each of the algorithms
running.forEach(v => v.a = fillWithDefault(r, currCount, ySegment - (image.font5.charHeight + 2)));
// run the comparison
running.forEach(v => control.runInParallel(() => {
const run = currentRun;
v.place = undefined;
v.algorithm(v.a);
if (run === currentRun) {
const place = currentPlace++;
if (place === 1)
music.powerUp.play();
else if (place === running.length)
music.wawawawaa.play();
// ordinal indicator is 'st', 'nd', 'rd', or 'th'
v.place = place + ordinalIndicator(place);
}
}));
}
function fillWithDefault(r: Math.FastRandom, count: number, maxHeight: number): number[] {
// reset seed so that output is consistent
r.reset();
let output: number[] = [];
for (let i = 0; i < count; ++i) {
output.push(r.randomRange(0, maxHeight));
}
return output;
}
function drawCurrentState(s: SortingAlgorithm, count: number, height: number, yOffset: number) {
const a = s.a
const title = s.title;
const lineWidth = Math.floor(screen.width / count) - 1;
const borderWidth = (screen.width - (count * (lineWidth + 1))) / 2;
for (let i = 0; i < a.length; ++i) {
if (a > 0) {
const maxValue = ySegment - (image.font5.charHeight + 2);
// pick color between 0x1 and 0xE based on value
let c = Math.clamp(0x1, 0xE, Math.floor(a * 14 / maxValue));
screen.fillRect(borderWidth + i * (lineWidth + 1), height + yOffset - a, lineWidth, a, c);
}
}
screen.print(title, borderWidth, yOffset + 1, 0x2, image.font5);
if (s.place)
screen.print(s.place, borderWidth, yOffset + 3 + image.font5.charHeight, 0x2, image.font5);
}
function ordinalIndicator(input: number) {
const lastDigit = input % 10;
if (lastDigit === 1)
return "st";
else if (lastDigit === 2)
return "nd";
else if (lastDigit === 3)
return "rd";
else
return "th";
}
/**
* Sorting Algorithm Implementations
*/
namespace sorts {
function swap(a: number[], i: number, j: number) {
let tmp = a;
a = a;
a = tmp;
pause(pauseDuration);
}
function compare(a: number, b: number) {
pause(pauseDuration)
return a < b;
}
export function insertionSort(a: number[]) {
for (let i = 0; i < a.length; i++) {
let value = a
let j: number;
for (j = i - 1; j > -1 && compare(value, a); --j) {
a = a;
pause(pauseDuration);
}
a = value;
}
return a;
}
export function selectionSort(a: number[]) {
for (let i = 0; i < a.length; i++) {
let min = i;
for (let j = i + 1; j < a.length; j++) {
if (compare(a, a)) {
min = j;
pause(pauseDuration);
}
}
if (i !== min) {
swap(a, i, min);
}
}
return a;
}
export function bubbleSort(a: number[]) {
for (let i = 0; i < a.length; ++i) {
for (let j = 0; j < i; ++j) {
if (compare(a, a)) {
swap(a, i, j);
}
}
}
return a;
}
export function shellSort(a: number[]) {
let increment = a.length / 2;
while (increment > 0) {
for (let i = increment; i < a.length; ++i) {
let j = i;
let t = a;
while (j >= increment && compare(t, a)) {
a = a;
j = j - increment;
pause(pauseDuration);
}
a = t;
}
if (increment == 2) {
increment = 1;
} else {
increment = Math.floor(increment * 5 / 11);
}
}
return a;
}
export function quickSort(a: number[]) {
qsort(a, 0, a.length - 1);
return a;
function qsort(a: number[], lo: number, hi: number) {
if (lo < hi) {
let p = partition(a, lo, hi);
qsort(a, lo, p - 1);
qsort(a, p + 1, hi);
}
}
function partition(a: number[], lo: number, hi: number) {
let pivot = a;
let i = lo - 1;
for (let j = lo; compare(j, hi); ++j) {
if (a < pivot) {
i++;
swap(a, i, j);
}
}
swap(a, i + 1, hi);
return i + 1;
}
}
export function heapSort(a: number[]) {
function buildMaxHeap(a: number[]) {
let i = Math.floor(a.length / 2 - 1);
while (i >= 0) {
heapify(a, i, a.length);
i -= 1;
}
}
function heapify(heap: number[], i: number, max: number) {
while (i < max) {
const left = 2 * i + 1;
const right = left + 1;
let curr = i;
if (left < max && compare(heap, heap)) {
curr = left;
}
if (right < max && compare(heap, heap)) {
curr = right;
}
if (curr == i) return;
swap(heap, i, curr);
i = curr;
}
}
buildMaxHeap(a);
for (let i = a.length - 1; i > 0; --i) {
swap(a, 0, i);
heapify(a, 0, i);
}
return a;
}
export function mergeSort(a: number[]) {
// Typically, you wouldn't keep an 'offset' or a link to the 'original' array,
// as the sort works by returning a new, sorted array as output - not by modifying
// the one passed as input. Here, though, it is needed so that the preview on the
// screen can be updated
function msort(a: number[], offset: number, original: number[]): number[] {
if (a.length < 2) {
return a;
}
const middle = Math.floor(a.length / 2);
let left = a.slice(0, middle);
let right = a.slice(middle, a.length);
left = msort(left, offset, original);
right = msort(right, offset + middle, original);
const merged = merge(left, right);
// Update preview on screen
merged.forEach(function (value: number, index: number) {
original = value;
pause(pauseDuration);
});
return merged;
}
function merge(left: number[], right: number[]) {
let result = [];
let lIndex = 0;
let rIndex = 0;
while (lIndex < left.length && rIndex < right.length) {
if (compare(left, right)) {
result.push(left);
++lIndex;
} else {
result.push(right);
++rIndex;
}
}
while (lIndex < left.length) {
result.push(left);
++lIndex;
}
while (rIndex < right.length) {
result.push(right);
++rIndex;
}
return result;
}
return msort(a, 0, a);
}
export function isSorted(a: number[]) {
for (let i = 1; i < a.length; ++i) {
if (a > a) {
return false;
}
}
return true;
};
}
【花雕动手做】基于 Kitronik 可编程开发板之排序算法
ARCADE MakeCode 排序算法可视化工具代码解读这是一个基于ARCADE MakeCode的排序算法可视化工具，可以同时比较多种排序算法的性能。
1. 基本设置和数据结构
javascript
const pauseDuration = 10;// 每次操作后的暂停时间，用于可视化
interface SortingAlgorithm {
title: string; // 算法名称
algorithm: (values: number[]) => number[];// 排序函数
a?: number[]; // 待排序的数组
place?: string; // 排名（如"1st"）
}
let currCount = 26; // 当前数组元素数量
let currentRun = 0; // 当前运行次数标识
let ySegment: number; // 每个算法在屏幕上的垂直分段高度
let currentPlace: number; // 当前排名
let running: SortingAlgorithm[] = []; // 正在运行的算法
let notRunning: SortingAlgorithm[] = []; // 未运行的算法
2. 添加排序算法示例
javascript
addExample("selection sort", sorts.selectionSort);
addExample("insertion sort", sorts.insertionSort);
addExample("bubble sort", sorts.bubbleSort);
addExample("shell sort", sorts.shellSort);
addExample("heap sort", sorts.heapSort);
addExample("quick sort", sorts.quickSort);
addExample("merge sort", sorts.mergeSort);
3. 初始化运行算法
javascript
// 开始时随机选择两个算法运行
for (let i = 0; i < 2; i++) {
moveRandom(notRunning, running);
}
4. 绘制函数
javascript
game.onPaint(() => {
running.forEach(function (value: SortingAlgorithm, index: number) {
drawCurrentState(value, currCount, ySegment, index * ySegment);
});
});
5. 控制器事件处理
javascript
// A按钮：重新开始
controller.A.onEvent(ControllerButtonEvent.Pressed, () => {
start();
});
// 左键：移除一个排序算法
controller.left.onEvent(ControllerButtonEvent.Pressed, () => {
if (running.length > 1) {
moveRandom(running, notRunning)
start();
}
});
// 右键：添加一个排序算法
controller.right.onEvent(ControllerButtonEvent.Pressed, () => {
if (notRunning.length > 0) {
moveRandom(notRunning, running)
start();
}
});
// 上键：增加元素数量
controller.up.onEvent(ControllerButtonEvent.Pressed, function () {
if (currCount + 6 < screen.width / 2) {
currCount += 6;
start();
}
});
// 下键：减少元素数量
controller.down.onEvent(ControllerButtonEvent.Pressed, function () {
if (currCount > 6) {
currCount -= 6;
start();
}
})
6. 核心函数
移动随机元素函数
javascript
function moveRandom<T>(a: T[], b: T[]) {
if (a.length > 0) {
const i = randint(0, a.length - 1);
b.push(a.removeAt(i));
}
}
添加示例函数
javascript
<span style="background-color: rgb(255, 255, 255);">f</span>unction addExample(title: string, sortAlgorithm: (values: number[]) => number[]) {
let output: SortingAlgorithm = {
title: title,
algorithm: sortAlgorithm
}
notRunning.push(output);
}
启动函数
javascript
function start() {
const r = new Math.FastRandom();
++currentRun;// 增加运行次数标识
currentPlace = 1;
ySegment = Math.floor(screen.height / running.length);
// 清除旧数组
running.forEach(v => {
while (v.a && v.a.length != 0)
v.a.pop();
});
// 创建新数组
running.forEach(v => v.a = fillWithDefault(r, currCount, ySegment - (image.font5.charHeight + 2)));
// 并行运行所有算法
running.forEach(v => control.runInParallel(() => {
const run = currentRun;
v.place = undefined;
v.algorithm(v.a);// 执行排序算法
if (run === currentRun) {// 确保是当前运行
const place = currentPlace++;
if (place === 1)
music.powerUp.play();// 第一名音效
else if (place === running.length)
music.wawawawaa.play();// 最后一名音效
v.place = place + ordinalIndicator(place);// 设置排名
}
}));
}
【花雕动手做】基于 Kitronik 可编程开发板之排序算法
排序算法解读1、插入排序 (Insertion Sort)
javascript
export function insertionSort(a: number[]) {
for (let i = 0; i < a.length; i++) {
let value = a
let j: number;
// 将当前元素与已排序部分比较，找到合适位置插入
for (j = i - 1; j > -1 && compare(value, a); --j) {
a = a;// 向后移动元素
pause(pauseDuration);
}
a = value;// 插入到正确位置
}
return a;
}
工作原理：将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置
时间复杂度：最好O(n)，平均O(n²)，最坏O(n²)
空间复杂度：O(1)
特点：对小规模数据高效，稳定排序算法
2、选择排序 (Selection Sort)
javascript
export function selectionSort(a: number[]) {
for (let i = 0; i < a.length; i++) {
let min = i;// 假设当前位置是最小值
// 在未排序部分寻找最小值
for (let j = i + 1; j < a.length; j++) {
if (compare(a, a)) {
min = j;// 更新最小值位置
pause(pauseDuration);
}
}
if (i !== min) {
swap(a, i, min);// 将最小值放到已排序末尾
}
}
return a;
}
工作原理：每次从未排序部分选择最小元素，放到已排序部分的末尾
时间复杂度：始终为O(n²)
空间复杂度：O(1)
特点：简单但效率低，不稳定排序算法
3、冒泡排序 (Bubble Sort)
javascript
export function bubbleSort(a: number[]) {
for (let i = 0; i < a.length; ++i) {
for (let j = 0; j < i; ++j) {
// 比较相邻元素，如果顺序错误则交换
if (compare(a, a)) {
swap(a, i, j);
}
}
}
return a;
}
工作原理：重复遍历数组，比较相邻元素并交换，直到没有需要交换的元素
时间复杂度：最好O(n)，平均O(n²)，最坏O(n²)
空间复杂度：O(1)
特点：简单但效率低，稳定排序算法
4、希尔排序 (Shell Sort)
javascript
export function shellSort(a: number[]) {
let increment = a.length / 2;// 初始间隔
while (increment > 0) {
// 对各个子数组进行插入排序
for (let i = increment; i < a.length; ++i) {
let j = i;
let t = a;
// 对子数组进行插入排序
while (j >= increment && compare(t, a)) {
a = a;
j = j - increment;
pause(pauseDuration);
}
a = t;
}
// 减小间隔
if (increment == 2) {
increment = 1;
} else {
increment = Math.floor(increment * 5 / 11);// 使用特定序列减少间隔
}
}
return a;
}
工作原理：是插入排序的改进版，通过将数组分成多个子数组进行排序，逐渐减少子数组的间隔
时间复杂度：取决于间隔序列，最好O(n log n)，最坏O(n²)
空间复杂度：O(1)
特点：比插入排序高效，不稳定排序算法
5、快速排序 (Quick Sort)
javascript
export function quickSort(a: number[]) {
qsort(a, 0, a.length - 1);// 递归排序
return a;
function qsort(a: number[], lo: number, hi: number) {
if (lo < hi) {
let p = partition(a, lo, hi);// 分区操作
qsort(a, lo, p - 1);// 递归排序左半部分
qsort(a, p + 1, hi);// 递归排序右半部分
}
}
function partition(a: number[], lo: number, hi: number) {
let pivot = a;// 选择最后一个元素作为基准
let i = lo - 1;
for (let j = lo; compare(j, hi); ++j) {
if (a < pivot) {
i++;
swap(a, i, j);// 将小于基准的元素移到左边
}
}
swap(a, i + 1, hi);// 将基准放到正确位置
return i + 1;
}
}
工作原理：分治算法，选择一个基准元素，将数组分成两部分，一部分小于基准，一部分大于基准，然后递归排序
时间复杂度：最好O(n log n)，平均O(n log n)，最坏O(n²)
空间复杂度：O(log n)
特点：通常是最快的排序算法，但不稳定
6、堆排序 (Heap Sort)
javascript
export function heapSort(a: number[]) {
function buildMaxHeap(a: number[]) {
let i = Math.floor(a.length / 2 - 1);
// 从最后一个非叶子节点开始构建最大堆
while (i >= 0) {
heapify(a, i, a.length);
i -= 1;
}
}
function heapify(heap: number[], i: number, max: number) {
while (i < max) {
const left = 2 * i + 1;// 左子节点
const right = left + 1;// 右子节点
let curr = i;
// 找出当前节点、左子节点、右子节点中的最大值
if (left < max && compare(heap, heap)) {
curr = left;
}
if (right < max && compare(heap, heap)) {
curr = right;
}
if (curr == i) return;// 如果当前节点已经是最大值，则返回
swap(heap, i, curr);// 交换当前节点与最大值节点
i = curr;// 继续向下调整
}
}
buildMaxHeap(a);// 构建最大堆
// 逐个提取最大值并放到数组末尾
for (let i = a.length - 1; i > 0; --i) {
swap(a, 0, i);// 将最大值(堆顶)与末尾元素交换
heapify(a, 0, i);// 调整堆
}
return a;
}
工作原理：利用堆数据结构，首先构建最大堆，然后逐个提取最大值并放到数组末尾
时间复杂度：始终为O(n log n)
空间复杂度：O(1)
特点：时间复杂度稳定，但不稳定排序算法
7、归并排序 (Merge Sort)
javascript
export function mergeSort(a: number[]) {
function msort(a: number[], offset: number, original: number[]): number[] {
if (a.length < 2) {
return a;// 基线条件：数组长度为1或0时已排序
}
const middle = Math.floor(a.length / 2);// 找到中间位置
let left = a.slice(0, middle);// 分割左半部分
let right = a.slice(middle, a.length);// 分割右半部分
left = msort(left, offset, original);// 递归排序左半部分
right = msort(right, offset + middle, original);// 递归排序右半部分
const merged = merge(left, right);// 合并两个已排序数组
// 更新屏幕上的可视化效果
merged.forEach(function (value: number, index: number) {
original = value;
pause(pauseDuration);
});
return merged;
}
function merge(left: number[], right: number[]) {
let result = [];
let lIndex = 0;
let rIndex = 0;
// 比较两个数组的元素，按顺序合并
while (lIndex < left.length && rIndex < right.length) {
if (compare(left, right)) {
result.push(left);
++lIndex;
} else {
result.push(right);
++rIndex;
}
}
// 将剩余元素添加到结果中
while (lIndex < left.length) {
result.push(left);
++lIndex;
}
while (rIndex < right.length) {
result.push(right);
++rIndex;
}
return result;
}
return msort(a, 0, a);
}
工作原理：分治算法，将数组分成两半，递归排序，然后合并两个已排序的子数组
时间复杂度：始终为O(n log n)
空间复杂度：O(n)
特点：稳定排序算法，适合大数据集，但需要额外空间
【花雕动手做】基于 Kitronik 可编程开发板之排序算法
通过模拟器，调试与模拟运行实验场景记录
【花雕动手做】基于 Kitronik 可编程开发板之排序算法
页:
[1]