快速排序(js版本)

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

 

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]);
}

 

快速排序(js版本),古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。