查看: 26|回复: 5

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

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

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

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

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

使用道具举报

精彩评论(5)

驴友花雕 中级技神
楼主|

发表于昨天 07:05

【花雕动手做】基于 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;
    };
}
复制代码

使用道具举报

驴友花雕 中级技神
楼主|

发表于昨天 07:11

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

使用道具举报

驴友花雕 中级技神
楼主|

发表于昨天 07:17

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

排序算法解读
1、插入排序 (Insertion Sort)
javascript

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;

}
复制代码

工作原理：将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置

时间复杂度：最好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[j], a[min])) {

                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[i], a[j])) {

                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[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;

}
复制代码

工作原理：是插入排序的改进版，通过将数组分成多个子数组进行排序，逐渐减少子数组的间隔

时间复杂度：取决于间隔序列，最好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[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;

    }

}
复制代码

工作原理：分治算法，选择一个基准元素，将数组分成两部分，一部分小于基准，一部分大于基准，然后递归排序

时间复杂度：最好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[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;

}
复制代码

工作原理：利用堆数据结构，首先构建最大堆，然后逐个提取最大值并放到数组末尾

时间复杂度：始终为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[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);

}
复制代码