查看: 10|回复: 4

[项目] 【花雕动手做】基于 Kitronik 可编程开发板之排序算法

Kitronik ARCADE 是一款由英国教育科技公司 Kitronik 精心打造的可编程游戏机开发板，专为编程教学与创客实践而设计。该设备原生支持微软的 MakeCode Arcade 平台，用户可通过图形化或 JavaScript 编程方式，轻松创建、下载并运行复古风格的街机游戏。

它集成了彩色 LCD 显示屏、方向控制键、功能按键、蜂鸣器和震动马达等交互组件，提供完整的游戏输入输出体验。无论是初学者进行编程启蒙，还是创客群体开发交互式作品，Kitronik ARCADE 都能作为理想的硬件载体，助力创意实现。

凭借其开源友好、易于上手、兼容性强等特点，该开发板广泛应用于中小学编程课程、创客工作坊、游戏开发教学以及个人项目原型设计，深受教育者与技术爱好者的喜爱。

【花雕动手做】基于 Kitronik 可编程开发板之排序算法图1

使用道具举报

精彩评论(4)

驴友花雕 中级技神
楼主|

发表于 2 小时前

【花雕动手做】基于 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[i] > 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[i] * 14 / maxValue));
            screen.fillRect(borderWidth + i * (lineWidth + 1), height + yOffset - a[i], lineWidth, a[i], 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[i];
        a[i] = a[j];
        a[j] = 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[i]
            let j: number;
            for (j = i - 1; j > -1 && compare(value, a[j]); --j) {
                a[j + 1] = a[j];
                pause(pauseDuration);
            }
            a[j + 1] = 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[j], a[min])) {
                    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[i], a[j])) {
                    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[i];

                while (j >= increment && compare(t, a[j - increment])) {
                    a[j] = a[j - increment];
                    j = j - increment;
                    pause(pauseDuration);
                }
                a[j] = 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[hi];
            let i = lo - 1;

            for (let j = lo; compare(j, hi); ++j) {
                if (a[j] < 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[curr], heap[left])) {
                    curr = left;
                }

                if (right < max && compare(heap[curr], heap[right])) {
                    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[offset + index] = 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[lIndex], right[rIndex])) {
                    result.push(left[lIndex]);
                    ++lIndex;
                } else {
                    result.push(right[rIndex]);
                    ++rIndex;
                }
            }
            while (lIndex < left.length) {
                result.push(left[lIndex]);
                ++lIndex;
            }
            while (rIndex < right.length) {
                result.push(right[rIndex]);
                ++rIndex;
            }
            return result;
        }

        return msort(a, 0, a);
    }

    export function isSorted(a: number[]) {
        for (let i = 1; i < a.length; ++i) {
            if (a[i - 1] > a[i]) {
                return false;
            }
        }
        return true;
    };
}
复制代码

使用道具举报

驴友花雕 中级技神
楼主|

发表于 2 小时前

【花雕动手做】基于 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);  // 设置排名
        }
    }));
}
复制代码