yeyuguo
7/3/2017 - 6:38 AM

快速排序算法

快速排序算法

// 快速遍历

times = 0
function quickSort(array) {
    function sort(prev, numsize) {
        var nonius = prev;
        var j = numsize - 1;
        var flag = array[prev];
        if ((numsize - prev) > 1) {
            while (nonius < j) {
                console.log('foreach time is :',++times);
                for (; nonius < j; j--) {
                    if (array[j] < flag) {
                        array[nonius++] = array[j]; //a[i] = a[j]; i += 1;
                        break;
                    };
                }
                for (; nonius < j; nonius++) {
                    if (array[nonius] > flag) {
                        array[j--] = array[nonius];
                        break;
                    }
                }
            }
            array[nonius] = flag;
            sort(0, nonius);
            sort(nonius + 1, numsize);
        }
    }
    sort(0, array.length);
    console.log(array)
    return array;
}


var quickSort2=function(arr){   
    //如果数组长度小于等于1无需判断直接返回即可  
    if(arr.length<=1){  
        return arr;  
    }  
    var midIndex=Math.floor(arr.length/2);//取基准点  
    var midIndexVal=arr.splice(midIndex,1);//取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数arr[index+1]  
    var left=[];//存放比基准点小的数组  
    var right=[];//存放比基准点大的数组  
    //遍历数组,进行判断分配  
    for(var i=0;i<arr.length;i++){  
        if(arr[i]<midIndexVal){  
            left.push(arr[i]);//比基准点小的放在左边数组  
        }  
        else{  
            right.push(arr[i]);//比基准点大的放在右边数组  
        }  
        console.log("第"+(++times)+"次排序后:"+arr);  
    }  
    //递归执行以上操作,对左右两个数组进行操作,直到数组长度为<=1;  
    return quickSort2(left).concat(midIndexVal,quickSort2(right));  
};  

dataArray = [2,5,4,1,7,3,8,6,9,0];  

// quickSort(dataArray)    // 循环85次,不浪费空间,但是遍历次数多,速度稍慢
console.log(quickSort2(dataArray)) //浪费空间,遍历次数少,速度快;