Algorithms(三)

//开始我们声明一个主方法来调用递归函数，传递待排序数组，以及索引 0及其最末的位置(因为我们要排整个数组，而不是一个子数组)作为参数。
this.quickSort = function(){
        quick(array,  0, array.length - 1);
};
/*
首先声明index，该变量能帮助我们将子数组分离为较小值数组和较大值数组，
这样，我们就能再次递归的调用quick函数了。
partition函数返回值将赋值给index。
如果数组的长度比1大(因为只有一个元素的数组必然是已排序了的，
我们将对给 定子数组执行partition操作(第一次调用是针对整个数组)以得到index。
如果子 数组存在较小值的元素，则对该数组重复这个过程。
同理，对存在较大值得 子数组也是如此，如果存在子数组存在较大值，我们也将重复快速排序过程。
*/
var quick = function(array, left, right){
        var index; 
        if (array.length > 1) { 
            index = partition(array, left, right); 
        };
        if (left < index - 1) {
            quick(array, left, index - 1);
        }
        if (index < right) {  
            quick(array, index, right);
        } 
}
//划分数组
/*
第一件要做的事情是选择主元(pivot)，有好几种方式。
最简单的一种是选择数组的第一项(最左项)。然而，研究表明对于几乎已排序的数组，这不是一个好的选择，它将导致该算法 的最差表现。
另外一种方式是随机选择一个数组项或是选择中间项。
在本实现中，我们选择中间 项作为主元。
我们初始化两个指针:left，初始化为数组第一个元素; right，初始化为数组最后一个元素。只要left和right指针没有相互交错，就执行划分操作。
首先，移动left指针 直到找到一个元素比主元大。对right指针，我们做同样的事情，移动right指针直 到我们找到一个元素比主元小。
当左指针指向的元素比主元大且右指针指向的元素比主元小，并且此时左指针索引没有右指 针索引大，意思是左项比右项大(值比较)。我们交换它们，然后移动两个指针，并重复此过程。
*/
var partition = function(array, left, right) {
        var pivot = array[Math.floor((right + left) / 2)], 
        i = left,
        j = right;
        while (i <= j) {
            while (array[i] < pivot) {  
                i++; 
            }
            while (array[j] > pivot) {  
                j--;
            }
            if (i <= j) { 
                swapQuickStort(array, i, j); 
                i++;
                j--;
            } 
        }
        return i; 
};
/*
在划分操作结束后，返回左指针的索引，用来在处创建子数组。
swapQuickStort函数和我们在本章开始处实现的swap函数十分相似。
唯一的不同之处是发 生交换值的的数组同样也是函数的参数。    
*/
var swapQuickStort = function(array, index1, index2){
        var aux = array[index1];
        array[index1] = array[index2];
        array[index2] = aux;
};