asfman
android developer
posts - 90,  comments - 213,  trackbacks - 0

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
<TITLE>  (快速排序与二分查找)</TITLE>
<META NAME="Generator" CONTENT="EditPlus">
<META NAME="Author" CONTENT="dolphin">
<META NAME="Keywords" CONTENT="">
<META NAME="Description" CONTENT="">
</HEAD>

<BODY>
<div id="sourceNum"></div>
<div id="sortNum"></div>
<div id="findProcess"></div>
<INPUT TYPE="text" NAME="FindNum" id="FindNum" size="10"><button onclick='javascript: if (/^\d+$/.test(document.getElementById("FindNum").value)){ a.HalfFind(a.sortArray,document.getElementById("FindNum").value)}else{alert("请输入正整数!");document.getElementById("FindNum").value="";document.getElementById("FindNum").focus()}'>Find</button>
<SCRIPT LANGUAGE="JavaScript">
<!--
function Half(sAry)
{
 this.sortArray = sAry;
 this.count = 0;

 this.swap = function(i,j)
 {
  var tmp = this.sortArray[i];this.sortArray[i] = this.sortArray[j];this.sortArray[j] = tmp;
  this.count++;
 }
 this.partition = function(low,high)
 {
  var pivot,pos,tmp,i,j;
  pos = low;
  pivot = this.sortArray[pos];
  for(i=low+1;i<=high;i++)
  {
   if (this.sortArray[i]<pivot)
   {
    pos++;
    this.swap(pos,i);
   }
  }
  this.swap(low,pos);
  return pos;
 }
 this.QuickSort = function(low,high)
 {
  var pivot;
  if (low<high)
  {
   pivot = this.partition(low,high);
   this.QuickSort(low,pivot-1);
   this.QuickSort(pivot+1,high);
  }
 }
 this.HalfFind = function(sArray,fNum)
 {
  var low,high,i,t;
  low = 0;
  i = 1;
  high = sArray.length-1;
  t = Math.floor((high+low) / 2);
  document.getElementById("findProcess").innerHTML="";
  while ((sArray[t]!=fNum) && (sArray[low]!=fNum) && (sArray[high]!=fNum) && (low < high))
  {
   document.getElementById("findProcess").innerHTML+="第"+i+"次查找 -> "+t+"的位置:"+sArray[t]+"&nbsp;&nbsp;&nbsp;&nbsp;low="+low+"&nbsp;high="+high+"<br>";
   
   if (fNum>sArray[t])
   {
    low = t+1;
    t = Math.floor((high+low) / 2);
   }
   else
   {
    high = t-1;
    t = Math.floor((high+low) / 2);
   }
   i++
  }
  if ((sArray[t]!=fNum) && (sArray[low]!=fNum) && (sArray[high]!=fNum) && low >= high)
  {
   document.getElementById("findProcess").innerHTML+="第"+i+"次查找 -> "+t+"的位置:失败 此队列没有"+fNum+"该数&nbsp;&nbsp;&nbsp;&nbsp;low="+low+"&nbsp;high="+high+"<br>";
  }
  else
  {
   if(sArray[t]==fNum)
    tt = t;
   else if(sArray[low]==fNum)
    tt = low;
   else
    tt = high;
   
   document.getElementById("findProcess").innerHTML+="第"+i+"次查找 -> "+tt+"的位置:"+sArray[tt]+" 找到了!&nbsp;&nbsp;&nbsp;&nbsp;low="+low+"&nbsp;high="+high+"<br>";
  }
  return t;
 }
}
var randLen = Math.floor(Math.random()*100);
var stAry = new Array(randLen);
var i,low,high;
for(i=0;i<randLen;i++)
 stAry[i] = Math.floor(Math.random()*100);
var a = new Half(stAry);
low = 0;
high = stAry.length-1;
document.getElementById("sourceNum").innerHTML="排序前:"+a.sortArray+"&nbsp;&nbsp;排序个数:"+(high+1);
a.QuickSort(low,high);
document.getElementById("sortNum").innerHTML="排序后:"+a.sortArray+"&nbsp;&nbsp;排序次数:"+a.count;
//-->
</SCRIPT>
</BODY>
</HTML>

posted on 2006-11-14 09:05 汪杰 阅读(266) 评论(0)  编辑 收藏 引用 所属分类: javascript
只有注册用户登录后才能发表评论。

<2019年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(15)

随笔分类(1)

随笔档案(90)

文章分类(727)

文章档案(712)

相册

收藏夹

http://blog.csdn.net/prodigynonsense

友情链接

最新随笔

搜索

  •  

积分与排名

  • 积分 - 384824
  • 排名 - 6

最新随笔

最新评论

阅读排行榜

评论排行榜