快速排序法
<script>
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;
}
}
</script>
回复 更多评论