在排序函数执行过程中迫使重绘以使步骤动画

我一直在尝试在JS中进行动画气泡排序，但是每次我运行代码时，它都会从随机顺序到即时分类。每次在颜色代码中交换两件事之后，我如何使其重新插入一定的时间。

<html>
<body>
<canvas id="myCanvas"   width="300" height="700" style="border:1px solid #d3d3d3;">
</canvas>
<script>
function swap(nums, pos1,pos2) {
	var a = nums[pos1];
	nums[pos1] = nums[pos2];
	nums[pos2] = a;
}
function shuffle(nums) {
	for (var i = 0; i < 1000; i++) {
		var num1 = Math.floor((Math.random())*26);
		var num2 = Math.floor((Math.random())*26);
		swap(nums,num1,num2);
	}
}
function sleep(seconds) 
{
  var e = new Date().getTime() + (seconds * 1000);
  while (new Date().getTime() <= e) {}
}
function drawIt(nums) {
	var c = document.getElementById("myCanvas");
	var ctx = c.getContext("2d");
	for (var i = 0; i < nums.length; i++) {
		var c = document.getElementById("myCanvas");
		var ctx = c.getContext("2d");	
		ctx.beginPath();
		ctx.rect(10, i * 20 + 10, 50, 20);
		ctx.stroke();
		ctx.fillStyle = "rgba(" + nums[i] + ", " + nums[i] + ", " + nums[i] + ", 1)";
		ctx.fill();
	}
}
var nums = new Array();
for (var i = 0; i<=250; i+=10) {
	nums[i/10] = i;
}
shuffle(nums);
drawIt(nums);
for (var i = 0; i < nums.length-1; i++) {
	for (var j = i+1; j < nums.length; j++) {
		if (nums[i] > nums[j]) {
			swap(nums, i,j);
			drawIt(nums);
		}
	}
} 
</script>
</body>
</html>

我尝试使用settimeout((，但没有任何效果。

编辑：

这是您的意思，因为这仍然不起作用。

<html>
<body>
<canvas id="myCanvas"   width="300" height="800" style="border:1px solid #d3d3d3;">
</canvas>
<script>
function swap(nums, pos1,pos2) {
	var a = nums[pos1];
	nums[pos1] = nums[pos2];
	nums[pos2] = a;
}
function shuffle(nums) {
	for (var i = 0; i < 1000; i++) {
		var num1 = Math.floor((Math.random())*26);
		var num2 = Math.floor((Math.random())*26);
		swap(nums,num1,num2);
	}
}
var counter1 = 0;
var counter2 = 1;
function drawIt(nums) {
	if (nums[counter1] > nums[counter2]) {
		swap(nums, counter1,counter2);
	}
	var c = document.getElementById("myCanvas");
	var ctx = c.getContext("2d");
	for (var i = 0; i < nums.length; i++) {
		var c = document.getElementById("myCanvas");
		var ctx = c.getContext("2d");
		ctx.beginPath();
		ctx.lineWidth = "1";
		ctx.strokeStyle = "rgba(" + nums[i] + ", " + nums[i] + ", " + nums[i] + ", 1)";
		ctx.rect(10, i * 15 + 10, 50, 15);
		ctx.stroke();
		ctx.beginPath();
		ctx.rect(10, i * 15 + 10, 50, 15);
		ctx.stroke();
		ctx.fillStyle = "rgba(" + nums[i] + ", " + nums[i] + ", " + nums[i] + ", 1)";
		ctx.fill();
	}
	if (counter2 < nums.length) {
		counter2++;
	}
	else {
		counter1++;
		counter2 = counter1+1;
	}
}
var nums = new Array();
for (var i = 0; i<=250; i+=5) {
	nums[i/5] = i;
}
shuffle(nums);
drawIt(nums);
for (var i = 0; i < (nums.length*(nums.length-1)) / 2; i++) {
	setTimeout(drawIt(nums), 2000);
}
</script>
</body>
</html>

不幸的是，在线程仍在运行时，无法强制绘制或DOM更新。解决此问题的方法是使您的排序算法重新进入，以便可以从计时器或通过SetteMeTimeout调用。每次触发计时器时，您都会执行一个迭代，然后绘制结果。

通过可视化算法在研究算法时，这有点烦人，因为在不修改算法的情况下无法实现步骤可视化。

编辑：添加了实现" recentrant"排序的工作代码段。

<html>
<body>
<canvas id="myCanvas"   width="300" height="700" style="border:1px solid #d3d3d3;">
</canvas>
<script>
function swap(nums, pos1,pos2) {
	var a = nums[pos1];
	nums[pos1] = nums[pos2];
	nums[pos2] = a;
}
function shuffle(nums) {
	for (var i = 0; i < 1000; i++) {
		var num1 = Math.floor((Math.random())*26);
		var num2 = Math.floor((Math.random())*26);
		swap(nums,num1,num2);
	}
}
function sleep(seconds) 
{
  var e = new Date().getTime() + (seconds * 1000);
  while (new Date().getTime() <= e) {}
}
function drawIt(nums) {
	var c = document.getElementById("myCanvas");
	var ctx = c.getContext("2d");
	for (var i = 0; i < nums.length; i++) {
		var c = document.getElementById("myCanvas");
		var ctx = c.getContext("2d");	
		ctx.beginPath();
		ctx.rect(10, i * 20 + 10, 50, 20);
		ctx.stroke();
		ctx.fillStyle = "rgba(" + nums[i] + ", " + nums[i] + ", " + nums[i] + ", 1)";
		ctx.fill();
	}
}
var nums = new Array();
for (var i = 0; i<=250; i+=10) {
	nums[i/10] = i;
}
shuffle(nums);
function sort()
{    
    var i=0;
    var j=0;
    var sortComplete=false;
    var reentrantSort = function()
    {
        if (nums[i] > nums[j]){
            swap(nums, i, j);
            drawIt(nums)
        }
        j++;
        if (j == nums.length){
            j=0;i++;
            if (i == nums.length ) {
                i=0;j=0;
                sortComplete=true; //Sorting is done
            }
        }
        if (!sortComplete){ // If sort still not complete
            setTimeout(reentrantSort,40); // Run next iteration in 40 ms.
        }
    };
    reentrantSort();
}
sort();
</script>
</body>
</html>

理想情况下，您想分开关注点 - 即在给定点上对数组进行排序并渲染其状态是不同的问题 - 您可以使用ES2015生成器来实现此目标。在下面的示例中，我采用了通用的气泡排序功能，并添加了function*签名和yield语句 - 在没有修改算法的情况下，这可以有效地允许您按顺序逐步介绍每次迭代。

function* bubbleSequence(arr){
    for(let i = 0; i < arr.length; ++i)
        for(let j = 0, end = arr.length - i; j < end; ++j)
            if(arr[j] > arr[j+1]){
                let temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                yield j+1; // <--- pauses execution
            }
}
function draw(arr, swapIdx){
    let ctx = document.getElementById('my-canvas').getContext('2d');
    arr.forEach((n, i) => {
        ctx.beginPath();
        ctx.rect(i * 11 + 10, 10, 10, 40);
        ctx.fillStyle = `rgba(${n},${n},${n},1)`;
        ctx.fill();
        ctx.beginPath();
        ctx.moveTo(i * 11 + 10, 53);
        ctx.lineTo(i * 11 + 20, 53);
        ctx.lineWidth = 2;
        ctx.strokeStyle = i === swapIdx || (i+1) === swapIdx ? '#f00' : '#333';
        ctx.stroke();
    });
}
var nums = [...Array(51)].map((_, i) => i * 5)
    .sort(_ => (Math.random() * 3 | 0) - 1);
var sorter = bubbleSequence(nums);
var interval = setInterval(_ => {
    let next = sorter.next();
    if(next.done) clearInterval(interval);
    window.requestAnimationFrame(_ => draw(nums, next.value));
}, 80);

<canvas id="my-canvas" width=600 height=180></canvas>

相关内容

最新更新

热门标签：