javascript实现快速排序和二分法查找

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

1.快速排序：

思路：找到数组中间的元素，把它单拎出来，然后从0开始判断数组中的元素比该基准元素大还是小，小的存左边，大的存右边，然后如此反复递归，得出结果。

function quickSort(arr) {
        if (arr.length <= 1) { return arr; }//如果输入数组长度小于等于1，直接返回数组。这也是递归算法的终结部分
        var base = Math.floor(arr.length / 2);//找到中间的基准元素位置
        var baseEle = arr.splice(base, 1)[0];//把基准元素从arr中摘除
        var left = [];
        var right = [];
        for (var i = 0; i < arr.length; i++) {
            if (arr[i] < baseEle) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return quickSort(left).concat([baseEle ], quickSort(right));
        //返回递归左右两个部分concat中间元素，这就是结果
    };

2.二分查找法

思路：从有序的数列中折半查找，看过幸运52吧？猜价格拿大奖的时候怎么猜最好？傻子都知道。

var erfen = function (val, arr) {
        if (arr.length < 1||val<arr[0]||val>arr[arr.length-1]) { 
          return false; 
        }//如果这个数字没在其中直接返回false
        else if (val == arr[0]||val==arr[arr.length-1]) {
            return true;
        }//如果找到了就返回true
        else if (arr.length == 1) {
            return false;
        }//如果不能再缩小了而且没查到返回false
        var res = [];
        var base = Math.floor(arr.length / 2);
        if (val > arr[base]) {
           res = arr.splice(base + 1, arr.length - 1);
        }//如果大于中间的从右边开始找
       else if (val = arr[base]) {
            return true;
        }//恰巧等于中间的就返回true
        else {
           res = arr.splic(0, base - 1);
        }//如果小于中间的就从右边找
        return erfen(val,res);//递归
    };