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

1.快速排序:

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

javascript实现快速排序和二分法查找
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中间元素,这就是结果 };
javascript实现快速排序和二分法查找


2.二分查找法

思路:从有序的数列中折半查找,看过幸运52吧?猜价格拿大奖的时候怎么猜最好?*都知道。

javascript实现快速排序和二分法查找
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);//递归
    };
javascript实现快速排序和二分法查找

javascript实现快速排序和二分法查找,布布扣,bubuko.com

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

上一篇:<转>十分钟学会javascript


下一篇:ASP.NET之JSONHelper操作