首页 > 代码库 > 快速排序（js版本）

快速排序（js版本）

2024-07-08 16:40:36   216人阅读

快速排序的时间复杂度为：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]);}

 


联系
我们