用js写了个快排，还有优化的余地

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

看了一天别人的代码，换换思路，写个快排。

直接上代码，低估了，原理一直记得，本以为10分钟能搞定，但出现很多小bug，整了20多分钟。

/**
 * Created by cdpmac on 15/5/15.
 */

var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
quickSort(arr,0,arr.length-1);


console.log(arr);
function quickSort(arr,left,right){
    if( left>=right){
        return;
    }
    var index=left;  //基础标识位 第一次为0
    var hight=right;
    //退出条件，左指针和右指针重合
    for(;left<right;){
        //从右向左找
        for(var i=right;i>left;i--){
//        如果找到，则交换两项的值。
            if(arr[i]<arr[index]){
                swap(arr,index,i);
                //交换之后
                //第一次 右-》左 为 [2, 3, 7, 4, 1, 9, 8, 6, 5] index 设i为(8);
                index=i;
                break;
            }
            right--;
        }
        for(var i=left+1;i<right;i++){
            if(arr[i]>arr[index]){
                swap(arr,index,i);
                //交换之后
                //第一次 左-》右 为 [2, 3, 5, 4, 1, 9, 8, 6, 7] index 设i为(2) ;
                index=i;
                break;
            }
            left++;
        }
    }
    //第一遍完事后，原来的基准值，也就是key(0)-value(5)到了index的位置。
    //该例结果是 [ 2, 3, 1, 4, 5, 9, 8, 6, 7 ],index为5
    //再以这个index为分割点，分别对左侧和右侧 递归执行该方法
    //原index已经在正中间，不用再比较index所处位置的值，两侧分别以-1为上限 +1为下限。
    quickSort(arr,0,index-1);//这么写 当index为0时 出无限递归了
//    left:0->right:0   [ 1, 2, 3, 4, 5, 9, 8, 6, 7 ]
//    left:0->right:-1  [ 1, 2, 3, 4, 5, 9, 8, 6, 7 ]
    quickSort(arr,index+1,hight);//也有可能出递归
//    在最上方加判断 left<right  修正


}
function swap(arr,lIndex,rIndex){
    var temp = arr[lIndex];
    arr[lIndex] = arr[rIndex];
    arr[rIndex] = temp;
}