3

大家好，我为快速排序程序尝试了这个逻辑。但是我需要将此代码转换为设置间隔模式，并且需要逐步覆盖整个过程。请帮助我将此逻辑改进为 setinterval Program 。我认为目前它处于递归模式。

function quicksort(arr)
{
    if (arr.length == 0)
        return [];

    var left = new Array();
    var right = new Array();
    var pivot = arr[0];

    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) {
           left.push(arr[i]);
        } else {
           right.push(arr[i]);
        }
    }

    return quicksort(left).concat(pivot, quicksort(right));
}
4

1 回答 1

1

您可以先将快速排序转换为非递归格式（迭代快速排序），然后使用 setInterval 替换 for 循环，从而将原始快速排序转换为“setInterval 模式”。

这是来自Stoimen 博客的迭代快速排序（我相信您原来的递归快速排序来自同一来源）。请注意，我对其进行了轻微修改，以便它使用延续传递样式的回调，而不是return：

function qsort(arr, ret)
{
    var stack = [arr];
    var sorted = [];

    while (stack.length) {

        var temp = stack.pop(), tl = temp.length;

        if (tl == 1) {
            sorted.push(temp[0]);
            continue;
        }
        var pivot = temp[0];
        var left = [], right = [];

        for (var i = 1; i < tl; i++) {
            if (temp[i] < pivot) {
                left.push(temp[i]);
            } else {
                right.push(temp[i]);
            }
        }

        left.push(pivot);

        if (right.length)
            stack.push(right);
        if (left.length)
            stack.push(left);

    }

    ret(sorted);
}

您可以通过这种方式调用该函数（例如）：

qsort([3,7,1,4,2,5], function(sortedarray) { console.log(sortedarray); });

现在要将这个迭代快速排序转换为“setInterval 模式”，您可以将函数中的 for 循环替换为对 setInterval 的调用（类似于此 Stackoverflow 帖子）。

这是使用的快速排序的最终版本setInterval：

function qsort(arr, ret)
{
    var stack = [arr];
    var sorted = [];
    var intervalId = 0;

    intervalId = setInterval(function() {
        if (stack.length) { 
            var temp = stack.pop(), tl = temp.length;

            if (tl == 1) {
                sorted.push(temp[0]);
                return;
            }
            var pivot = temp[0];
            var left = [], right = [];

            for (var i = 1; i < tl; i++) {
                if (temp[i] < pivot) {
                    left.push(temp[i]);
                } else {
                    right.push(temp[i]);
                }
            }

            left.push(pivot);

            if (right.length)
                stack.push(right);
            if (left.length)
                stack.push(left);           
        } 
        else if (sorted.length == arr.length) {
            clearInterval(intervalId);
            ret(sorted);
        }
    }, 0);      
}

这里发生的是原始数组的片段被添加到堆栈中（这是分区步骤），然后单独排序。在每次setInterval调用时，您都在对数组的不同部分进行排序（在原始递归快速排序中，每个快速排序调用都在处理数组的不同部分）。setInterval请注意，一旦排序后的数组与原始数组大小相同，我们就会停止排序（也就是说，我们告诉停止调用）。那是我们调用ret回调的时候。

于 2012-10-27T08:05:27.623 回答