基于JavaScript實(shí)現(xiàn)的順序查找算法示例
本文實(shí)例講述了基于JavaScript實(shí)現(xiàn)的順序查找算法。分享給大家供大家參考,具體如下:
對(duì)于查找數(shù)據(jù)來說,最簡單的方法就是從列表的第一個(gè)元素開始對(duì)列表元素逐個(gè)進(jìn)行判斷,直到找到了想要的結(jié)果。這個(gè)方法叫做順序查找,有時(shí)候也被叫做線性查找。它屬于暴力查找技巧的一種。
順序查找實(shí)現(xiàn)起來非常簡單,代碼如下:
function generalSearch(arr,data){//普通的順序查找,就是遍歷一遍看是否找到 for(var i=0;i<arr.length;i++){ if(arr[i]==data){ return true; } } return false; }
那么這樣會(huì)不會(huì)效率很低呢?對(duì)于未排序的數(shù)據(jù)集來說,當(dāng)被查到的數(shù)據(jù)位于數(shù)據(jù)集的起始位置時(shí),查找是最快、最成功的。通過將成功找到的元素置于數(shù)據(jù)集的起始位置,可以保證在以后的操作中元素能被更快的查找到,代碼如下:
function betterSearch(arr,data){//自組織查找,將查找率高的依次往前移 for(var i=0;i<arr.length;i++){ if(arr[i]==data){ if(i>0){ swap(arr,i,i-1);//如果找到則將查找的值和前一個(gè)值交換位置 } return true; } } return false; } function swap(arr,i,j){//交換位置 temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; }
那有沒有更加好的方法呢?在查找的世界中,有一個(gè)“80-20原則”,指的是對(duì)某一數(shù)據(jù)集執(zhí)行的80%的查找操作都是對(duì)其中20%的數(shù)據(jù)元素進(jìn)行查找。所以我們可以將查找到且處于后80%的元素放在起始位置,而前20%則不需要改變,代碼如下:
function bestSearch(arr,data){//更好的自組織查找,將排名后80%的查找結(jié)果調(diào)到第一位 for(var i=0;i<arr.length;i++){ if(arr[i]==data&&i>(arr.length*0.2)){//如果是后80% swap(arr,i,0); return true; }else if(arr[i]==data){ return true;//前20%就不移動(dòng)了 } } return false; }
三種查找的實(shí)驗(yàn)代碼如下:
//進(jìn)行試驗(yàn) var nums=[3,1,4,6,2,9,8,0,5,7]; //普通查找 var bool=generalSearch(nums,3); document.write(bool+'<br>');//true var bool=generalSearch(nums,11); document.write(bool+'<br>');//false //自組織查找 showNums(nums);//3 1 4 6 2 9 8 0 5 7 betterSearch(nums,2); showNums(nums);//3 1 4 2 6 9 8 0 5 7 betterSearch(nums,2); showNums(nums);//3 1 2 4 6 9 8 0 5 7 betterSearch(nums,2); showNums(nums);//3 2 1 4 6 9 8 0 5 7 //更好的自組織查找 document.write("更好的自組織查找<br>"); bestSearch(nums,5); showNums(nums);//5 2 1 4 6 9 8 0 3 7 bestSearch(nums,2); showNums(nums);//5 2 1 4 6 9 8 0 3 7
順序查找的完整代碼:
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> </head> <body> <script type="text/javascript"> function generalSearch(arr,data){//普通的順序查找,就是遍歷一遍看是否找到 for(var i=0;i<arr.length;i++){ if(arr[i]==data){ return true; } } return false; } function betterSearch(arr,data){//自組織查找,將查找率高的依次往前移 for(var i=0;i<arr.length;i++){ if(arr[i]==data){ if(i>0){ swap(arr,i,i-1);//如果找到則將查找的值和前一個(gè)值交換位置 } return true; } } return false; } function swap(arr,i,j){//交換位置 temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } function bestSearch(arr,data){//更好的自組織查找,將排名后80%的查找結(jié)果調(diào)到第一位 for(var i=0;i<arr.length;i++){ if(arr[i]==data&&i>(arr.length*0.2)){//如果是后80% swap(arr,i,0); return true; }else if(arr[i]==data){ return true;//前20%就不移動(dòng)了 } } return false; } function showNums(arr){ for(var i=0;i<arr.length;i++){ document.write(arr[i]+' '); } document.write("<br>"); } //進(jìn)行試驗(yàn) var nums=[3,1,4,6,2,9,8,0,5,7]; //普通查找 var bool=generalSearch(nums,3); document.write(bool+'<br>');//true var bool=generalSearch(nums,11); document.write(bool+'<br>');//false //自組織查找 showNums(nums);//3 1 4 6 2 9 8 0 5 7 betterSearch(nums,2); showNums(nums);//3 1 4 2 6 9 8 0 5 7 betterSearch(nums,2); showNums(nums);//3 1 2 4 6 9 8 0 5 7 betterSearch(nums,2); showNums(nums);//3 2 1 4 6 9 8 0 5 7 //更好的自組織查找 document.write("更好的自組織查找<br>"); bestSearch(nums,5); showNums(nums);//5 2 1 4 6 9 8 0 3 7 bestSearch(nums,2); showNums(nums);//5 2 1 4 6 9 8 0 3 7 </script> </body> </html>
運(yùn)行效果如下圖:
更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》
希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。
相關(guān)文章
深入了解Hybrid App技術(shù)的相關(guān)知識(shí)
這篇文章主要介紹了深入了解Hybrid App技術(shù)的相關(guān)知識(shí),Hybrid App(混合模式移動(dòng)應(yīng)用)是指介于web-app、native-app這兩者之間的app,兼具" Native App良好用戶交互體驗(yàn)的優(yōu)勢(shì) "和" Web App跨平臺(tái)開發(fā)的優(yōu)勢(shì) ",需要的朋友可以參考下2019-07-07JavaScript實(shí)現(xiàn)數(shù)據(jù)可視化圖表的示例代碼
這篇文章主要介紹了如何使用JavaScript創(chuàng)建實(shí)時(shí)數(shù)據(jù)可視化圖表,我們將使用流行的圖表庫,如Chart.js,來展示如何將實(shí)時(shí)數(shù)據(jù)動(dòng)態(tài)呈現(xiàn)在圖表中,感興趣的可以了解下2024-01-01js時(shí)間轉(zhuǎn)換毫秒的實(shí)例代碼
在本篇文章里小編給大家整理的是關(guān)于js時(shí)間轉(zhuǎn)換毫秒的實(shí)例代碼以及相關(guān)知識(shí)點(diǎn),需要的朋友們可以學(xué)習(xí)下。2019-08-08JavaScript實(shí)現(xiàn)各種排序的代碼詳解
這篇文章給大家介紹了js實(shí)現(xiàn)各種排序功能,包括冒泡排序,選擇排序和插入排序,代碼簡單易懂,非常不錯(cuò),具有參考借鑒價(jià)值,需要的的朋友參考下吧2017-08-08JavaScript實(shí)現(xiàn)表單驗(yàn)證示例
這篇文章主要為大家詳細(xì)介紹了JavaScript實(shí)現(xiàn)表單驗(yàn)證示例,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-06-06