javascript - 这个 QuickSort 实现有什么问题？

Question

我有以下内容:

function quickSort(array, low, high) {
    var len = array.length,
        l = low || 0,
        r = high || len - 1,
        m = Math.round((l + r) / 2),
        t;

    do {
        while (array[l] < array[m]) {
            l += 1;
        }
        while (array[r] > array[m]) {
            r -= 1;
        }

        if (l <= r) {
            if (l < r) {
                t = array[r];
                array[r] = array[l];
                array[l] = t;

                console.log('Swapped ' + array[r] + ' with ' +
                                         array[l] + '. ' +
                                         array);
            }

            l += 1;
            r -= 1;
        }
    } while (l <= r);

    if (r > 0) quickSort(array, 0, r);  
    if (l < len - 1) quickSort(array, l, len - 1);
}

使用方法如下:

var initial = [1, 8, 9, 0, 2, 5, 6, 7, 3, 4, 10], // Duplicate, just to compare
    sorted  = [1, 8, 9, 0, 2, 5, 6, 7, 3, 4, 10];

quickSort(sorted);

console.log('Initial: ' + initial + '\nSorted:  ' + sorted);

令人惊讶的是，代码在数组排序后抛出 stack_overflow。我想我错过了递归退出条件，但我不知道在哪里。

Answer 1

编辑(替换之前的答案):我认为这里的问题是您设置 len 变量的方式。对于就地排序，len 应该只是被排序的数组部分的长度，而不是整个数组，否则最后的比较永远不会计算为 false。所以不是:

var len = array.length,
    l = low || 0,
    r = high || len - 1;

需要根据l和r设置len:

var l = low || 0,
    r = high || array.length - 1,
    len = r-l;

您可以在此处查看工作中的 jsFiddle:http://jsfiddle.net/nrabinowitz/PPeh9/6/ - 我用随机数组替换了你的测试数据进行测试。