基于JavaScript實現的順序查找算法示例

2019-11-19 16:49:45

字體：大中小

來源：轉載

供稿：網友

本文實例講述了基于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);//如果找到則將查找的值和前一個值交換位置   }   return true;  } } return false;}function swap(arr,i,j){//交換位置 temp=arr[i]; arr[i]=arr[j]; arr[j]=temp;}

那有沒有更加好的方法呢？在查找的世界中，有一個“80-20原則”，指的是對某一數據集執行的80%的查找操作都是對其中20%的數據元素進行查找。所以我們可以將查找到且處于后80%的元素放在起始位置，而前20%則不需要改變，代碼如下：

function bestSearch(arr,data){//更好的自組織查找，將排名后80%的查找結果調到第一位 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%就不移動了  } } return false;}

三種查找的實驗代碼如下：

//進行試驗var nums=[3,1,4,6,2,9,8,0,5,7];//普通查找var bool=generalSearch(nums,3);document.write(bool+'<br>');//truevar bool=generalSearch(nums,11);document.write(bool+'<br>');//false//自組織查找showNums(nums);//3 1 4 6 2 9 8 0 5 7betterSearch(nums,2);showNums(nums);//3 1 4 2 6 9 8 0 5 7betterSearch(nums,2);showNums(nums);//3 1 2 4 6 9 8 0 5 7betterSearch(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 7bestSearch(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);//如果找到則將查找的值和前一個值交換位置    }    return true;   }  }  return false; } function swap(arr,i,j){//交換位置  temp=arr[i];  arr[i]=arr[j];  arr[j]=temp; } function bestSearch(arr,data){//更好的自組織查找，將排名后80%的查找結果調到第一位  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%就不移動了   }  }  return false; } function showNums(arr){  for(var i=0;i<arr.length;i++){   document.write(arr[i]+' ');  }  document.write("<br>"); } //進行試驗 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>

運行效果如下圖：