快排的递归与非递归实现（二）

快排的递归与非递归实现（二）：我们首先将之前快排的代码进行一个拆解，将分段函数独立出来，主要是为了我们可以很方便的理解递归的过程，从而通过堆栈来模拟递归，实现快速排序的非递归实现。
拆解出partition函数：

 function partition(arr, start, end) {
        var flag = arr[start];
        while (start < end) {
            while (start < end && arr[end] >= flag)
                end--;
            arr[start] = arr[end];
            while (start < end && arr[start] <= flag)
                start++;
            arr[end] = arr[start];
        }
        arr[start] = flag; 
        return start;
    }

    function quickSort(arr, start, end) {
        var index;
        if (end > start) {
            index = partition(arr, start, end);
            quickSort(arr, start, index - 1);
            quickSort(arr, index + 1, end);
        }
    }

调用quickSort(arr, 0, arr.length - 1);即可对arr进行排序。
我们发现，递归的过程，其实主要是通过partition对start,index,end进行递归使用。那么，现在我们可以利用堆栈，保存对start、index、end的引用，从而实现递归的效果。

1、定义一个数组，先将end，start入栈（考虑出栈时顺序，end先入）。
2、只要栈不为空（这里即为数组长度不为0），进行出栈操作，即另left = start，right =end，然后调用partition，返回index，有了index我们即可进行分段，然后两段依次入栈。
3、重复上述步骤，即可完成a 的排序。

这里一个需要注意的点，就是入栈出栈的操作顺序，务必要符合我们要求。

贴代码：

 function partition(arr, start, end) {
        var flag = arr[start];
        while (start < end) {
            while (start < end && arr[end] >= flag)
                end--;
            arr[start] = arr[end];
            while (start < end && arr[start] <= flag)
                start++;
            arr[end] = arr[start];
        }
        arr[start] = flag;
        return start;
    }

    function quickSort(arr, start, end) {
        var stack = [],
            left, right;
        if (start < end) {
            stack.push(end);
            stack.push(start);
            while (stack.length != 0) {
                left = stack.pop();
                right = stack.pop();
                index = partition(arr, left, right);
                if (left < index - 1) {
                    stack.push(index - 1);
                    stack.push(left);
                }
                if (right > index + 1) {
                    stack.push(right);
                    stack.push(index + 1);
                }
            }
        }
    }