《算法图解》JavaScrip实现二分查找、选择排序

偏执的太偏执、 2022-02-01 12:55 179阅读 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

发表评论取消回复

表情：

评论列表（有 0 条评论，179人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java--冒泡、选择排序，二分查找

一、冒泡排序，选择排序，二分查找 package com.cat.stringbuffer; public class BubbleSort {

╰+哭是因爲堅強的太久メ/ 2023年10月17日 10:59/ 0 赞/ 29 阅读

相关 Java中常见的算法 - 冒泡排序 - 选择排序 - 二分查找

文章目录常见算法选择排序冒泡排序二分查找常见算法选择排序选择排序的

忘是亡心i/ 2023年09月26日 11:38/ 0 赞/ 63 阅读

相关排序算法图解（二）：选择排序

文章目录 1 选择排序简介 2 图解选择排序算法 3 选择排序代码实现写在最后 -------------------- 1 选择排序简介

红太狼/ 2023年09月23日 13:45/ 0 赞/ 119 阅读

相关二分查找，选择排序，快速排序，归并排序，冒泡排序

二分查找平均时间复杂度logn def bianryfind(list,item): low =0; high= len(list)-1

墨蓝/ 2023年01月23日 10:55/ 0 赞/ 21 阅读

相关冒泡排序，选择排序，快速排序，堆排序与二分查找算法

public class Test { public static void main(String[] args) { int arr

拼搏现实的明天。/ 2022年08月18日 00:55/ 0 赞/ 205 阅读

相关 java--冒泡排序、选择排序、二分查找、插入排序

冒泡排序、选择排序、二分查找、插入排序冒泡排序冒泡排序的思想就是两两比较，按从小到大输出的话，两个值相比，较小的放前大的放后，那么第一次两两比较结束后，最大

桃扇骨/ 2022年05月15日 17:39/ 0 赞/ 257 阅读

相关 JAVA实现三种排序算法+二分查找算法

冒泡排序 > 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。 > 其核心思想是： > 对于一组需要排序的数字，依次将个位置上的数字与

女爷i/ 2022年05月15日 10:21/ 0 赞/ 208 阅读

相关图解排序算法及实现——选择排序（Selection sort）

选择排序（Selection sort）是一种简单直观的排序算法，也叫直接选择排序。思路设左边为有序区，右边乱序区。从右边剩下的乱序数字中找最小，放到左边。（反过

柔情只为你懂/ 2022年05月14日 05:15/ 0 赞/ 220 阅读

相关《算法图解》JavaScrip实现二分查找、选择排序

参考文章： [http://jartto.wang/2018/11/22/algorithm1/][http_jartto.wang_2018_11_22_algorith

偏执的太偏执、/ 2022年02月01日 12:55/ 0 赞/ 180 阅读

相关 JAVA实现三种排序算法+二分查找算法

冒泡排序冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。其核心思想是：对于一组需要排序的数字，依次将个位置上的数字与逐一与其之

忘是亡心i/ 2021年12月12日 13:45/ 0 赞/ 268 阅读