作者:zhanhailiang 日期:2012-12-16

在描述快速排序前需要以下划分算法，它是快速排序的基础。

1.划分算法 设A[low…high]是n元数组，且x = A[low]。考虑重新安排数组A中元素，使得小于或等于x的元素排在x的前面，随后x又在所有大于它的元素的前面。经过这样的排列后，经过数组中元素改变排列后，对于某个w，low ? x ? high，A[w] = x，称这样的重排列行为为围绕x的拆分或划分，x称为主元或拆分元素。

接下来我们给出的划分算法split。

/****************************************
算法：split
输入：数组A[low...high]
输出：
    1.若有必要，输出按上述描述的重新排列的数组A;
    2.划分元素A[low]的新位置w;
****************************************/
function split(array, low, high) {
    var i = low;
    var x = array[low];
    for(var j = low + 1; j <= high; j++) {
        if(array[j] <= x) {
            i ++;
            if