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);//递归 };