Java Script 排序算法可视化工具

Question

k = []
len = 100;
time = true

cont = document.getElementsByClassName("cont")[0];
cont.innerHTML = "";
for (let i = 0; i < len; i++) {
    t = Math.round(Math.random() * 800 ) + 5
    k.push(t);
    cont.innerHTML += "<div class='block' style = 'height:" + t + "px'></div>"
}


function reset(){
    k = []
    cont.innerHTML = "";
    for (let i = 0; i < len; i++) {
        t = Math.round(Math.random() * 800 ) + 5
        k.push(t);
        cont.innerHTML += "<div class='block' style = 'height:" + t + "px'> </div>"
    }

}

function bubble(){
    function iloop(i){
        if(i < len){
        setTimeout(function(){
            function jloop(j){
                if(j < len){
                setTimeout(function(){
                    if (k[j] > k[j + 1]) {
                        let tmp = k[j];
                        k[j] = k[j + 1];
                        k[j + 1] = tmp;
                    }
                    cont.innerHTML = "";
                    for (let p = 0; p < len; p++) {
                        cont.innerHTML += "<div class='block' style = 'height:" + k[p] + "px'></div>"
                    }
                    j++;
                    jloop(j);
                }, 100);
                }
            }
            jloop(0);



            i++;
            iloop(i);
        }, 100);
        }
    }
    iloop(0);
}

.cont {
  width: 100%;
  height: 900px;
  display: block;
  background-color: pink;
  padding: 0px;
  display: -webkit-box;
  display: -ms-flexbox;
  display: flex;
  -webkit-box-pack: center;
  -ms-flex-pack: center;
  justify-content: center;
  -ms-flex-line-pack: center;
  align-content: center; }
  .cont .block {
    display: inline-block;
    width: 10px;
    margin: auto 1px;
    background-color: red;
    font-size: 5px;
    bottom: 0px; }

<button class="reset" onclick="reset()">Reset Array
</button> 
<button class="bubble" onclick="bubble()">Bubble Sort
</button> 
<div class="cont"> 
 </div>

我正在使用这个简单的代码来制作一个用于排序算法的 javascript 可视化工具，但问题是它非常不稳定，即使在 100 毫秒的延迟下运行时也会跳过多个帧。我有 i7 7700hq 和 gtx 1060，所以我知道问题主要不是我的笔记本电脑，而是我的方法，所以我应该采取什么方法

如果您的代码段不起作用，这是一个代码笔版本 https://codepen.io/varunagarwal/pen/gOaQqbG

编辑：有人告诉我让它成为一个可运行的片段，所以你去

Answer 1

你有重叠的setTimeout计时器，并且其中很多都被安排好了。您只想在需要显示更改时返回给浏览器，并且您只想显示给定的更改一次。

由于您使用的是 ES2015+，我可能会使用生成器函数来进行排序，当某些内容发生变化时产生：

function *sortGen() {
    for (let i = 0; i < len; ++i) {
        for (let j = 0; j < len; ++j) {
            if (k[j] > k[j + 1]) {
                let tmp = k[j];
                k[j] = k[j + 1];
                k[j + 1] = tmp;
                yield j; // *** Yield to caller, saying what changed
            }
        }
    }
}

然后调用它的代码将调用它的next方法，进行更新，然后在下一个动画帧之前安排回调通过requestAnimationFrame（除非您想人为地减慢速度，在这种情况下setTimeout很好）。如果浏览器不忙于执行其他操作，则动画帧每秒发生 60 次（大约每 16.666667 毫秒）。这里bubble使用上面函数中的生成器sortGen：

function bubble() {
    const gen = sortGen();
    tick();

    function tick() {
        const result = gen.next();
        if (!result.done) {
            // *** No need to recreate all the elements, just reorder the ones that got swapped
            const el = cont.children[result.value];
            const next = el.nextElementSibling;
            el.parentElement.insertBefore(next, el);
            requestAnimationFrame(tick);
        }
    }
}

（您可以将其设为异步生成器并使用for-await-of循环，但我认为它并没有给您带来太多好处。）

这是一个活生生的例子；我还在代码中添加了一些注释，提出了其他建议：

function *sortGen() {
    for (let i = 0; i < len; ++i) {
        for (let j = 0; j < len; ++j) {
            if (k[j] > k[j + 1]) {
                let tmp = k[j];
                k[j] = k[j + 1];
                k[j + 1] = tmp;
                yield j; // *** Yield to caller, saying what changed
            }
        }
    }
}

function bubble() {
    const gen = sortGen();
    tick();

    function tick() {
        const result = gen.next();
        if (!result.done) {
            // *** No need to recreate all the elements, just reorder the ones that got swapped
            const el = cont.children[result.value];
            const next = el.nextElementSibling;
            el.parentElement.insertBefore(next, el);
            requestAnimationFrame(tick);
        }
    }
}

"use strict"; // *** Use strict mode

// *** Declare your variables (the old code relied on The Horror of Implicit Globals, which
// strict mode fixes)
let k = []; // *** Consistently use semicolons (or consistently rely on ASI)
let len = 100;
let time = true;

const cont = document.getElementsByClassName("cont")[0];
// *** Don't duplicate code, just use `reset`
reset();

function reset(){
    k = [];
    // *** Never use += on `innerHTML`
    let html = "";
    for (let i = 0; i < len; i++) {
        // *** Declare your variables
        const t = Math.round(Math.random() * 800 ) + 5;
        k.push(t);
        html += makeBlock(t);
    }
    cont.innerHTML = html;
}

function makeBlock(value) {
    return "<div class='block' style = 'height:" + value + "px'></div>";
}

function *sortGen() {
    for (let i = 0; i < len; ++i) {
        for (let j = 0; j < len; ++j) {
            if (k[j] > k[j + 1]) {
                let tmp = k[j];
                k[j] = k[j + 1];
                k[j + 1] = tmp;
                yield j; // *** Yield to caller, saying what changed
            }
        }
    }
}

function bubble() {
    const gen = sortGen();
    tick();

    function tick() {
        const result = gen.next();
        if (!result.done) {
            // *** No need to recreate all the elements, just reorder the ones that got swapped
            const el = cont.children[result.value];
            const next = el.nextElementSibling;
            el.parentElement.insertBefore(next, el);
            requestAnimationFrame(tick);
        }
    }
}

也在 CodePen 上。

就其价值而言，异步生成器方法看起来像这样：

const nextFrame = cb => new Promise(resolve => {
    requestAnimationFrame(() => {
        cb();
        resolve();
    });
});

function bubble() {
    (async () => {
        for await (const value of sortGen()) {
            await nextFrame(() => {
                const el = cont.children[value];
                const next = el.nextElementSibling;
                el.parentElement.insertBefore(next, el);
            });
        }
    })()
    .catch(error => {
        // Handle/report error here...
        console.error(error);
    });
}

.cont {
  width: 100%;
  height: 900px;
  display: block;
  background-color: pink;
  padding: 0px;
  display: -webkit-box;
  display: -ms-flexbox;
  display: flex;
  -webkit-box-pack: center;
  -ms-flex-pack: center;
  justify-content: center;
  -ms-flex-line-pack: center;
  align-content: center;
} /* *** Don't hide closing } at the end of a line */
.cont .block {
  display: inline-block;
  width: 10px;
  margin: auto 1px;
  background-color: red;
  font-size: 5px;
  bottom: 0px;
} /* *** Don't hide closing } at the end of a line */

<button class="reset" onclick="reset()">Reset Array
</button> 
<button class="bubble" onclick="bubble()">Bubble Sort
</button> 
<div class="cont"> 
</div>

const nextFrame = cb => new Promise(resolve => {
    requestAnimationFrame(() => {
        cb();
        resolve();
    });
});

function bubble() {
    (async () => {
        for await (const value of sortGen()) {
            await nextFrame(() => {
                const el = cont.children[value];
                const next = el.nextElementSibling;
                el.parentElement.insertBefore(next, el);
            });
        }
    })()
    .catch(error => {
        // Handle/report error here...
        console.error(error);
    });
}

也在 CodePen 上。