快速排序（js版本）

浏览数：32 / 时间：2015年06月09日

快速排序的时间复杂度为：O(n*log₂n)，相比较其他O(n²)的排序算法，还是比较有优势的。原文参考在此处，因为本人对原文的一小段代码有点不理解，所以进行了小的修改。

1.基本思想：在数组的第一个或最后一个元素里选择一个，作为基准元素，也称中轴。通过排序，让中轴把数组分为俩部分，一部分比中轴小，一部分大。再用递归法同样的排序俩部分。

2.实例：

3.js代码

var arrayQuick = [7,9,4,8,2,24,54,12,32,11,2];
quick(arrayQuick,0,arrayQuick.length-1);       //后俩个参数决定了对数组的某本分进行快速排序，这里是对整个数组
function quick(list,low,high){
    if(low<high)
    {
        var middle = getMiddle(list,low,high);      //将list数组进行一分为二
        quick(list,low,middle-1);                   //对低字表进行递归排序
        quick(list,middle+1,high);                  //对高字表进行递归排序
    }
}

function getMiddle(list,low,high){
    var tmp = list[low];                    //数组的第一个作为基准元素，即中轴
    while(low<high)
    {
        while(low<high&&list[high]>=tmp)    //从高端向中轴依次寻找比中轴低的数据
        {
            high--;
        }
        //在高端找到比中轴低的数据，然后交换位置
        list[low]=list[high];
        list[high]=tmp;
        while(low<high&&list[low]<=tmp)    //从低端向中轴依次寻找比中轴高的数据
        {
            low++;
        }
        //在低端找到比中轴高的数据，然后交换位置
        list[high]=list[low];
        list[low]=tmp;
    }
    return low;                   //返回中轴的位置
}

for(var i=0; i<arrayQuick.length; i++)
{
    cc.log(arrayQuick[i]);
}