2013年4月20日 星期六

謝爾排序式

無標題文件
謝爾排序法
隨機產生 手動輸入
 

主要運作模式:

首先將欲排序數字以陣列表示,並將初始組距設為陣列大小的一半,而組距亦為間隔的意思,假設說陣列大小為10,初始組距則為5,因此一開始的排序因子就為0、5,將這兩個陣列位置的元素進行插入排序,接下來組距則/2直到1為止,過程都如此運算,最後即完成排序,謝爾排序式可為改良式的插入排序,只是不同在於謝爾是以組為概念,加快了排序速度。

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>無標題文件</title>
</head>
<script language="javascript">
function loadEvent(){
appear.style.visibility = "hidden";
}
function inputSelect()
{
document.getElementById("inputText").select();
}
function radioClick(){
appear.style.visibility = "visible";
if (randomClick.checked) {
create.value="排序";
inputLabel.innerHTML = "輸入欲產生多少數字排序:";
}else
{
create.value = "開始排序";
inputLabel.innerHTML = "輸入數字並以逗號隔開:";
}
document.getElementById("inputText").focus();
}
function printTarget(iArray,preview,target,d)
{
var sText = "(";
for (var i = 0;i < iArray.length;i++)
{
if (i == target) {sText += "[" + iArray[i] + "]";preview = i;}
else if (i == preview || i - preview == d) { sText += iArray[i] + " ";preview = i;}
else sText += "* "
}
sText += "}</br>"
return sText;
}
function printArray(iArray)
{
var sText = "";
for (var i = 0;i < iArray.length;i++) sText += iArray[i] + " ";
return sText + "</br>";
}
function shell_sort()
{
var iArray = (randomClick.checked)?getArray(0):getArray(1);
var d = parseInt(iArray.length/2),k = 0;
var sText = "";
while (d > 0)
{
sText += "<font color=\"red\">===========當組距為" + d + "時===========</font></br>"
for (var i = 0;i < d;i++)//根據d決定幾組
{
sText+="<font color=\"blue\">=============[第" + (i+1) + "組]=============</font></br>";
for (var j = i+d;j < iArray.length;j += d){//每一組的插入排序
k = j;
sText += "<font color = \"orange\">" + printTarget(iArray,i,j,d) + "</font>";
while (k > i && iArray[k-d] > iArray[k])//向前插入,但以組距為單位
{
var tmp = iArray[k-d];
iArray[k-d] = iArray[k];
iArray[k] = tmp;
k -= d;
}
sText += "<font color=\"green\">插入排序後:</font></br>";
sText += printArray(iArray);
}
}
d = parseInt(d/2);
}
outputLabel.innerHTML = sText;
inputSelect();
}
function getArray(index)
{
var iArray;
if (index)
{
var sArray = inputText.value.split(",");
iArray = new Array(sArray.length);
for (var i = 0;i < iArray.length;i++) iArray[i] = parseInt(sArray[i]);
}
else
{
var n = parseInt(inputText.value);
iArray = new Array(n);
for (var i = 0;i < n;i++) {
iArray[i] = Math.floor(Math.random()*(n*10));//Random
}
}
return iArray;
}
</script>
<body onload="loadEvent()">
<table width="100%" border="0" cellspacing="0" cellpadding="0">
<tr>
<td style="background-repeat: repeat-x; background-color: #6FF; color: #069; font-weight: bold; font-size: 24px; font-family: '標楷體'; text-align: center;">謝爾排序法</td>
</tr>
</table>
<table width="100%" border="0" align="center" cellpadding="0" cellspacing="0">
<tr>
<td><input type="radio" name="RadioGroup1" value="隨機產生" id="randomClick" onclick="radioClick()"/> 隨機產生</td>
<td><input type="radio" name="RadioGroup1" value="手動輸入" id="inputClick" onclick="radioClick()"/>手動輸入</td>
</tr>
<tr>
<td colspan="2">
<span id="inputLabel"></span>
<span id='appear'>
<input type="text" name="inputText" id="inputText" onkeydown="if(window.event.keyCode==13)shell_sort()" onclick=" inputSelect();"/>
<input type="button" name="create" id="create" value="產生" onclick="shell_sort()"/>
</span>
</tr>
<tr>
<td colspan="2">&nbsp;</td>
</tr>
</table><span id="outputLabel"></span>
</body>
</html>

沒有留言:

張貼留言