《算法图解》JavaScrip实现二分查找、选择排序 偏执的太偏执、 2022-02-01 12:55 138阅读 0赞 参考文章: [http://jartto.wang/2018/11/22/algorithm1/][http_jartto.wang_2018_11_22_algorithm1] [http://jartto.wang/2018/11/25/algorithm2/][http_jartto.wang_2018_11_25_algorithm2] 二分查找代码如下: function binarySearch(arr,val){ let start = 0; let end = arr.length -1; let guess; while(start<=end){ //mid是索引 let mid = Math.ceil((start+end)/2); //guess是不断寻找的中间值,mid索引对应的值 guess = arr[mid]; if (guess === val) { //返回值对应索引 return mid; }else if(guess>val){ //如果mid对应索引值大于要找的val,要在左侧找,此时end为mid-1 end = mid-1; }else{ start = mid+1; } } //如果找不到返回-1 return -1; } //测试结果 binarySearch([1, 3, 5, 7, 9], 3); 1 选择排序代码如下: function selectionSort(arr) { //newArr用于存储排列好的数组 let newArr = []; let len = arr.length; for(let i = 0;i<len;i++){ //我们总是假设第一个是最小值,我们要注意到arr长度是不断减少的 let smallest = arr[0]; let smallest_index = 0; //然后拿第一个和剩下的依次比较 for(let j=1;j<len-1;j++){ if(arr[j]<smallest){ smallest = arr[j]; smallest_index = j; } } //splice返回是一个数组 newArr.push(arr.splice(smallest_index,1)[0]) } //循环执行后返回newArr return newArr; } //结果测试 selectionSort([5, 3, 6, 2, 10]); [2, 3, 5, 6, 10] 我们需要注意两点: 1.splice()该方法会改变原始数组,所以arr.splice()后arr长度减少,返回每次除去最小值之后新的数组。 2.splice()返回一个数组,所以有\[0\]。 我们看下面的代码,arr不断变化,返回每次除去最小值之后的数组,所以每次我们就可以设最小值都是arr\[0\],假设第一个是最小值,但是数组arr的length不变,因为i增加的,循环次数就是length,我们通过let len = arr.length;获取len,arr传入时候,len就是一个固定的常量了 function selectionSort(arr) { //newArr用于存储排列好的数组 let newArr = []; let len = arr.length; for(let i = 0;i<len;i++){ //我们假设第一个(i++后是第二个)是最小值 let smallest = arr[0]; let smallest_index = 0; //然后拿第一个和剩下的依次比较 for(let j=1;j<len-1;j++){ if(arr[j]<smallest){ smallest = arr[j]; smallest_index = j; } } //splice返回是一个数组 newArr.push(arr.splice(smallest_index,1)[0]) console.log(arr); console.log(len); } //循环执行后返回newArr return newArr; } 显示结果: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70] 如果没有\[0\]取出数组中第一个数,像下面这样 //splice返回是一个数组 newArr.push(arr.splice(smallest_index,1)) 返回的结果就会像下面一样: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1] [http_jartto.wang_2018_11_22_algorithm1]: http://jartto.wang/2018/11/22/algorithm1/ [http_jartto.wang_2018_11_25_algorithm2]: http://jartto.wang/2018/11/25/algorithm2/ [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70]: /images/20220201/612bad8305f74c5caef7bf5a8caa986b.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ0NjU5MzQ_size_16_color_FFFFFF_t_70 1]: /images/20220201/ea9dc7e52d0c47f692a79f7f34d509fc.png
还没有评论,来说两句吧...