之前看到别人用js写了一个排序算法的可视化，于是creator版本的出现了。
我们最终想要实现的效果，把一个随机分布的 点数组 整理成 从小到大排序的 点数组。
首先介绍一下极坐标
- O：极点，也就是原点
- ρ：极径
- θ：极径与X轴夹角
- x = ρ * cosθ，因为x / ρ = cosθ
- y = ρ * sinθ，因为y / ρ = sinθ
我们首先模拟一下，我们通过37个元素，来转化成 极坐标中的37个点
const arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
31, 32, 33, 34, 35, 36];
转化公式
-
元素对应的索引index * 10 -> 角度θ (为什么乘于10，因为37个元素需要模拟0°~360°)
-
元素对应的值arr[index] -> 极径ρ
于是我们获取到了转化后的数据
(0 -> θ = 0, ρ = 0)(1 -> θ = 10, ρ = 1)(2 -> θ = 20, ρ = 2)(0 -> θ = 30, ρ = 3)
(4 -> θ = 40, ρ = 4)(5 -> θ = 50, ρ = 5)(6 -> θ = 60, ρ = 6)(7 -> θ = 70, ρ = 7)
(8 -> θ = 80, ρ = 8)(9 -> θ = 90, ρ = 9)(10 -> θ = 100, ρ = 10)(11 -> θ = 110, ρ = 11)
(12 -> θ = 120, ρ = 12)(13 -> θ = 130, ρ = 13)(14 -> θ = 140, ρ = 14)(15 -> θ = 150, ρ = 15)
(16 -> θ = 160, ρ = 16)(17 -> θ = 170, ρ = 17)(18 -> θ = 180, ρ = 18)(19 -> θ = 190, ρ = 19)
(20 -> θ = 200, ρ = 20)(21 -> θ = 210, ρ = 21)(22 -> θ = 220, ρ = 22)(23 -> θ = 230, ρ = 23)
(24 -> θ = 240, ρ = 24)(25 -> θ = 250, ρ = 25)(26 -> θ = 260, ρ = 26)(27 -> θ = 270, ρ = 27)
(28 -> θ = 280, ρ = 28)(29 -> θ = 290, ρ = 29)(30 -> θ = 300, ρ = 30)(31 -> θ = 310, ρ = 31)
(32 -> θ = 320, ρ = 32)(33 -> θ = 330, ρ = 33)(34 -> θ = 340, ρ = 34)(35 -> θ = 350, ρ = 35)
(36 -> θ = 360, ρ = 36)
现在我们把数组打散，比如
const arr = [25, 8, 32, 1, 19, 14, 0, 29, 17, 6, 7,
26, 3, 30, 31, 16, 28, 15, 24, 10, 21,
2, 9, 4, 35, 5, 36, 33, 11, 27, 34,
22, 13, 18, 23, 12, 20];
通过转化后，我们获取到
(25 -> θ = 0, ρ = 25)(8 -> θ = 10, ρ = 8)(32 -> θ = 20, ρ = 32)(1 -> θ = 30, ρ = 1)
(19 -> θ = 40, ρ = 19)(14 -> θ = 50, ρ = 14)(0 -> θ = 60, ρ = 0)(29 -> θ = 70, ρ = 19)
(17 -> θ = 80, ρ = 17)(6 -> θ = 90, ρ = 6)(7 -> θ = 100, ρ = 7)(26 -> θ = 110, ρ = 26)
(3 -> θ = 120, ρ = 3)(30 -> θ = 130, ρ = 30)(31 -> θ = 140, ρ = 31)(16 -> θ = 150, ρ = 16)
(28 -> θ = 160, ρ = 28)(15 -> θ = 170, ρ = 15)(24 -> θ = 180, ρ = 24)(10 -> θ = 190, ρ = 10)
(21 -> θ = 200, ρ = 21)(2 -> θ = 210, ρ = 2)(9 -> θ = 220, ρ = 9)(4 -> θ = 230, ρ = 4)
(35 -> θ = 240, ρ = 35)(5 -> θ = 250, ρ = 5)(36 -> θ = 260, ρ = 36)(33 -> θ = 270, ρ = 33)
(11 -> θ = 280, ρ = 11)(27 -> θ = 290, ρ = 27)(34 -> θ = 300, ρ = 34)(22 -> θ = 310, ρ = 22)
(13 -> θ = 320, ρ = 13)(18 -> θ = 330, ρ = 18)(23 -> θ = 340, ρ = 23)(12 -> θ = 350, ρ = 12)
(20 -> θ = 360, ρ = 20)
整理一下实现效果的思路
- 生成一个乱序数组
- 在Canvas画布上画出乱序数组所有元素对应的 极坐标对应的点
- 对乱序数组进行排序
- 排序过程中，需要不断清空画布并且重画数组所有元素对应的极坐标的点
- 直到排序完成，终止画布操作
有了思路，开始搞起~
生成一个 360 个元素的乱序数组
// 生成乱序数组
generateMassArray () {
let arr = [];
for (let i = 0; i < 360; i++) {
arr.push(i);
}
const res = [];
while (arr.length) {
// 打乱
const randomIndex = Math.random() * arr.length - 1;
res.push(arr.splice(randomIndex, 1)[0]);
}
return res;
}
在Canvas画布上画出乱序数组所有元素对应的 极坐标对应的点，需要通过 x = ρ * cosθ，y = ρ * sinθ来获取点坐标
// 数据转化
doDataConversion (arr: number[]) {
let ret = [];
for (let i = 0; i < arr.length; i++) {
let index = arr[i];
let xita = i;
let p = index;
// 极坐标
// x = ρ * cosθ，因为x / ρ = cosθ
// y = ρ * sinθ，因为y / ρ = sinθ
let r = -Math.PI / 180 * xita;
// 为了效果明显, 扩大 x,y
let x = p * Math.cos(r);
let y = p * Math.sin(r);
// console.log(`(${index} -> θ = ${xita}°, p = ${p})`);
// console.log(`(x = ${x}, y = ${y})`);
let data = {
x: x,
y: y,
xita: xita,
p: p,
}
ret.push(data);
}
return ret;
}
使用graphics组件，把这些点坐标绘制到Canvas画布上，做个简单的接口封装
// 绘制点
drawPoint (x: number, y: number, sc: Color = Color.WHITE, fc: Color = Color.WHITE, pointRadius: number = 2) {
let g = this._graphics;
g.circle(x, y, pointRadius);
g.strokeColor = sc;
g.fillColor = fc;
g.stroke();
g.fill();
}
因为我们需要批量绘制N个点，所以还需要封装一个绘制N个点的接口
// 做一次绘制
doOneDraw (arr: any[]) {
for (let i = 0; i < arr.length; i++) {
let d = arr[i];
let x = d.x;
let y = d.y;
this.drawPoint(x, y);
}
}
但是这边只是批量绘制，不能很好的模拟，动态的排序效果，所以我们使用计时器对每一次排序的结果，做一次批量绘制的操作
// 排序后绘制
doSortDraw (total: any[], time = 0.05) {
for (let i = 0; i < total.length; i++) {
let d1 = total[i];
let ret = this.doDataConversion(d1);
const that = this;
this.scheduleOnce(()=>{
that._graphics.clear();
that.doOneDraw(ret);
}, time * i);
}
}
一切准备就绪，开始你的表演吧 ~
冒泡排序
onBubbleSort (){
let arr = this._pointArray;
let len = arr.length;
let total = [];
for (var i = 0; i < len; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
var temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
let a : number[] = [];
for (let j = 0; j < arr.length; j++) {
a.push(arr[j]);
}
total.push(a);
}
this.doSortDraw(total);
}
选择排序
onSelectionSort (){
let arr = this._pointArray;
let len = arr.length;
let minIndex, temp;
let total = [];
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
let a : number[] = [];
for (let j = 0; j < arr.length; j++) {
a.push(arr[j]);
}
total.push(a);
}
this.doSortDraw(total);
}
插入排序
onInsertionSort (){
let arr = this._pointArray;
let len = arr.length;
let total = [];
for (var i = 1; i < len; i++) {
var key = arr[i];
var j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
let a : number[] = [];
for (let j = 0; j < arr.length; j++) {
a.push(arr[j]);
}
total.push(a);
}
this.doSortDraw(total);
}
堆排序
onHeapSort (){
let arr = this._pointArray;
function heapify(arr: number[], x: number, len: number) {
var l = 2 * x + 1;
var r = 2 * x + 2;
var largest = x, temp;
if (l < len && arr[l] > arr[largest]) {
largest = l;
}
if (r < len && arr[r] > arr[largest]) {
largest = r;
}
if (largest != x) {
temp = arr[x];
arr[x] = arr[largest];
arr[largest] = temp;
heapify(arr, largest, len);
}
}
let total = [];
// 建堆
var heapSize = arr.length, temp;
for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
heapify(arr, i, heapSize);
let a : number[] = [];
for (let j = 0; j < arr.length; j++) {
a.push(arr[j]);
}
total.push(a);
}
this.doSortDraw(total);
// 堆排序
for (var j = heapSize - 1; j >= 1; j--) {
temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
let a : number[] = [];
for (let k = 0; k < arr.length; k++) {
a.push(arr[k]);
}
heapify(arr, 0, --heapSize);
total.push(a);
}
this.doSortDraw(total);
}
快速排序
onQuickSort (){
let nums = this._pointArray;
const that = this;
let total: any[] = [];
function quick(arr: any[], left: number, right: number) {
if (left < right) {
let x = arr[right];
let i = left - 1;
let temp;
for (let j = left; j <= right; j++) {
if (arr[j] <= x) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
let a : number[] = [];
for (let j = 0; j < arr.length; j++) {
a.push(arr[j]);
}
total.push(a);
quick(nums, left, i - 1);
quick(nums, i + 1, right);
} else {
that.doSortDraw(total);
}
}
quick(nums, 0, nums.length - 1);
}
基数排序
onRadixSort (){
let nums = this._pointArray;
const that = this;
function radix (arr: number[]) {
let bucket = new Array(10);
for (let i = 0; i < bucket.length; i++) {
bucket[i] = new Array(arr.length);
}
let buckeElementCounts = new Array(10).fill(0);
let max = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i]
}
}
let maxLength = (max + '').length;
let total = [];
for (let i = 0, n = 1; i < maxLength; i++, n = n * 10) {
for (let j = 0; j < arr.length; j++) {
let digitOfElement = Math.floor(arr[j] / n) % 10;
bucket[digitOfElement][buckeElementCounts[digitOfElement]] = arr[j];
buckeElementCounts[digitOfElement]++;
}
let index = 0;
for (let k = 0; k < buckeElementCounts.length; k++) {
if (buckeElementCounts[k] !== 0) {
for (let l = 0; l < buckeElementCounts[k]; l++) {
arr[index] = bucket[k][l];
index++;
}
let a : number[] = [];
for (let m = 0; m < arr.length; m++) {
a.push(arr[m]);
}
total.push(a);
buckeElementCounts[k] = 0;
}
}
}
that.doSortDraw(total, 0.1);
}
radix(nums);
}
希尔排序
onShellSort (){
let nums = this._pointArray;
const that = this;
function shell (arr: number[]) {
let len = arr.length;
let temp, gap = 1;
let total = [];
while (gap < len / 5) {
gap = gap * 5 + 1;
}
for (gap; gap > 0; gap = Math.floor(gap / 5)) {
for (let i = gap; i < len; i++) {
temp = arr[i];
let j;
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
arr[j + gap] = arr[j];
}
arr[j + gap] = temp;
let a : number[] = [];
for (j = 0; j < arr.length; j++) {
a.push(arr[j]);
}
total.push(a);
}
}
that.doSortDraw(total);
}
shell(nums);
}
最后说一句，上面演示的效果，并不一定代表着排序算法的效率。
项目的DEMO地址
https://gitee.com/yeshao2069/CocosCreatorDemos/tree/v3.0.0/2DDemo/VisualizationAlgorithm
编辑器版本：Cocos Creator 3.0.0