zhengrenzhe's blog   About

快速排序非递归实现

在排序算法中,快速排序是非常快的一种算法,也是各种面试中会被问到的问题。在学习快排的过程中,大部分网上的资料都是通过递归实现的,这在别的编程语言中或许很方便,但在JS中就不是很好了。因为在ES5中,并没有尾调用优化这个东西,所以递归次数一多,就会导致堆栈溢出。在我的Mac上,也只能排10000个左右的数,再多就堆栈溢出而无法运行。

而递归是可以被改写为循环的,对于使用循环实现的排序算法,自然是不会有堆栈溢出这个问题了,轻松排1000w个数无压力。在我的Mac上, 使用循环实现的快排居然比ES5原生的Array.prototype.sort还快,原生方法排序1000w个数需要3431ms,而循环实现的快排排同样数量的数只要2660ms,又一次见识到了算法的力量。

非递归版本的实现思路与递归版本相同,只不过将递归调用转化为循环调用,并用栈来管理参数。之前写过一篇 递归版本 的,实现思路可以看这篇。下面是具体代码:

function Quick(arr){

    console.time('quick');

    // 设定分区的初始值,这与递归调用版本里的分区默认值作用相同
    var left  = 0,
        right = arr.length - 1,

        // 用数组来模拟栈,push和pop方法JS原生已提供,除此之外,还需实现一个last方法,用来获取栈中的最后一组值。
        stack = [];
        stack.push([left, right]);
        stack.last = function(){
            return stack[stack.length-1];
        }

    // 进行分区操作后,会将生成的要继续进行分区范围push进栈,在下一次分区操作前,pop最后一个栈。当所有分区都排序后,栈里是没有数据的,这时就排序完了。
    while(true){
        if(stack.length === 0){
            break;
        }
        var startrange = stack.last();
        part(arr, startrange[0], startrange[1]);
    }

    function part(arr, left, right){

        stack.pop();

        var index = left,
            pivot = arr[right];

        for(var i = left; i < right; i++){

            if(arr[i] < pivot){

                var tmp = arr[index];
                arr[index] = arr[i];
                arr[i] = tmp;
                index++;

            }
        }

        var tmp = arr[right];
        arr[right] = arr[index];
        arr[index] = tmp;

        // 当生成符合逻辑的分区时,就将他们push到栈里,等待被分区。
        if(left < index - 1){
            stack.push([left, index - 1]);
        }

        if(index + 1 < right){
            stack.push([index + 1, right]);
        }
    }

    console.timeEnd('quick');

    return arr;

}

代码还是很简单的,核心就是要理解快排是如何工作的,以及递归时分区的顺序,不然写循环版本时就会对操作栈有一些困惑。相比之下,递归版本还是好理解一些,但对于ES5来说,排上万的数据时就要用循环版本了。不过ES6加入了尾调用优化,这样递归版本的问题就迎刃而解了。

← Javascript的cloneNode  JavaScript中的this →