<!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]+" low="+low+" 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+"该数 low="+low+" 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]+" 找到了！ low="+low+" 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+" 排序个数："+(high+1);
a.QuickSort(low,high);
document.getElementById("sortNum").innerHTML="排序后："+a.sortArray+" 排序次数："+a.count;
//-->
</SCRIPT>
</BODY>
</HTML>
posted on 2006-11-14 09:05
汪杰 阅读(324)
评论(0) 编辑 收藏 引用 所属分类:
javascript