快捷導(dǎo)航

基于JavaScript實現(xiàn)的順序查找算法示例

更新時間：2017年04月14日 08:53:02 作者：布瑞澤的童話

這篇文章主要介紹了基于JavaScript實現(xiàn)的順序查找算法,結(jié)合實例形式分析了javascript順序查找的原理、實現(xiàn)技巧與相關(guān)注意事項,需要的朋友可以參考下

本文實例講述了基于JavaScript實現(xiàn)的順序查找算法。分享給大家供大家參考，具體如下：

對于查找數(shù)據(jù)來說，最簡單的方法就是從列表的第一個元素開始對列表元素逐個進(jìn)行判斷，直到找到了想要的結(jié)果。這個方法叫做順序查找，有時候也被叫做線性查找。它屬于暴力查找技巧的一種。

順序查找實現(xiàn)起來非常簡單，代碼如下：

function generalSearch(arr,data){//普通的順序查找，就是遍歷一遍看是否找到
 for(var i=0;i<arr.length;i++){
  if(arr[i]==data){
   return true;
  }
 }
 return false;
}

那么這樣會不會效率很低呢？對于未排序的數(shù)據(jù)集來說，當(dāng)被查到的數(shù)據(jù)位于數(shù)據(jù)集的起始位置時，查找是最快、最成功的。通過將成功找到的元素置于數(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);//如果找到則將查找的值和前一個值交換位置
   }
   return true;
  }
 }
 return false;
}
function swap(arr,i,j){//交換位置
 temp=arr[i];
 arr[i]=arr[j];
 arr[j]=temp;
}

那有沒有更加好的方法呢？在查找的世界中，有一個“80-20原則”，指的是對某一數(shù)據(jù)集執(zhí)行的80%的查找操作都是對其中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%就不移動了
  }
 }
 return false;
}

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

//進(jì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);//如果找到則將查找的值和前一個值交換位置
    }
    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%就不移動了
   }
  }
  return false;
 }
 function showNums(arr){
  for(var i=0;i<arr.length;i++){
   document.write(arr[i]+' ');
  }
  document.write("<br>");
 }
 //進(jì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>

運行效果如下圖：