JS排序算法之快速排序

快速排序和归并排序都是采用二分法的排序算法。都是 Olog N

不过快速排序更复杂一些。

快递排序跟归并排序的区别是顺序，它是先总后分。

不断地从断点分，让左边的数都小于断点，右边都大于断点。然后迭代切分。

var group= [1,9,3,5,0,4,2,8];

function swap (k,y,arr) {
    var aux = arr[k];
    arr[k] = arr[y];
    arr[y]=aux;
        
};

function quickSort(list) {

    return quick(list,0,list.length-1); 

}

function quick(array,left,right) {//主方法用来递归 和传递数组
    if (array.length >1){
            var index = shear(array,left,right);

            if(left<index-1){//返回位置的前面还有未排序的
                quick(array,left,index-1);
                }
            if(right>index){//后面还有未排序的，递归
                quick(array,index,right);
            }

    }
    return array;
};
function shear(array,left,right) {
    var pivot = array[Math.floor((left+right)/2)];
    var nl = left;
    var nr = right;
    while(nl<=nr){
        while( array[nl] < pivot){ //找左边的比pivot更大的值
            nl++;
        }
        while( array[nr] > pivot ){ //找右边的比pivot更小的值
            nr--;
        }
        if(nl <= nr){//如果找到的两个数是左右的顺序，那么交换
            swap(nl,nr,array);
            nl++;
            nr--;
        }

    }
    return nl;//返回用来创建子数组的位置。该位置的左侧都是小于pivot的值，该位置及其右侧都是大于等于pivot的。

}
quickSort(group);