希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。
如下图所示:
代码如下:
<!DOCTYPE html> <html> <head> <title>The eleven html page</title> <style type="text/css"> ul li { list-style-type:georgian; text-align:left; } .mark { width:140px; height:40px; color:Olive; text-align:center; line-height:40px; margin:5px; float:left; } .redball { width:40px; height:40px; border-radius:20px; background-color:Red; text-align:center; line-height:40px; margin:5px; float:left; } .ball { width:40px; height:40px; border-radius:20px; background-color:Aqua; text-align:center; line-height:40px; margin:5px; float:left; } .line { clear:left; } header { height:80px; border:1px solid gray; } .left { border:1px solid gray; float:left; width:30%; height:480px; margin-left:0px; margin-right:0px; } aside { text-align:center; } section { width:69.5%; float:left; height:480px; border:1px solid gray; margin-left:0px; margin-right:0px; } footer { clear:left; height:60px; border:1px solid gray; } input[type="button"] { width:80px; text-align:center; margin-top:10px; } </style> <script type="text/javascript"> function initDiv() { var mainArea = document.getElementById("mainArea"); for (var i = 0; i < 8; i++) { var newDivLine = document.createElement("div"); newDivLine.setAttribute("class", "line"); mainArea.appendChild(newDivLine); for (var j = 0; j < 9; j++) { var newDiv = document.createElement("div"); var id = i.toString() + j.toString(); newDiv.setAttribute("id", id); if (j < 8) { newDiv.setAttribute("class", "ball"); } else { newDiv.setAttribute("class", "mark"); } newDivLine.appendChild(newDiv); } } } //初始元素赋值 var arrTmp = [4, 6, 8, 7, 9, 2, 10, 1]; function setElementsValue() { for (var i = 0; i < arrTmp.length; i++) { document.getElementById("0" + i.toString()).innerText = arrTmp[i]; } document.getElementById("08").innerText = "原始数据"; } //希尔排序 function setShellSortValue() { var m = 0;//表示第几趟排序 //d的值,4,2,1,表示增量 for (var d = Math.floor(arrTmp.length / 2); d > 0; d = Math.floor(d / 2)) { //第一次,d=4,循环次数,依次比较0,4/1,5/2,6/3,7 var atmp = new Array(); var n=0; for (var i = d; i < arrTmp.length; i++) { //如果第i个元素,小于第i-d个元素,则需要移动,否则不需要移动 if (arrTmp[i]<arrTmp[i - d] ) { var j = i - d; //依次比较j和d+j个元素的大小 while (j >= 0) { if (arrTmp[j] > arrTmp[d + j]) { var temp = arrTmp[j]; arrTmp[j] = arrTmp[d + j]; arrTmp[d + j] = temp; atmp[n]=(d + j); n=n+1; } j -= d; } } } m = m + 1; //显示出来 for (var k = 0; k < arrTmp.length; k++) { document.getElementById((m).toString() + k.toString()).innerText = arrTmp[k]; for(var n=0;n<atmp.length;n++){ if(atmp[n] ==k){ document.getElementById((m).toString() + (atmp[n]).toString()).setAttribute("class", "redball"); } } } document.getElementById((m).toString() + "8").innerText = "第 " + (m).toString() + " 趟排序(d="+d+")"; } } </script> </head> <body> <header> <h1>希尔排序(Shell Sort)Demo</h1> </header> <aside class="left"> <input type="button" id="btnInit" value="Init" onclick="initDiv();" /> <br /> <input type="button" id="btnSetValue" value="SetValue" onclick="setElementsValue();" /> <br /> <input type="button" id="btnSort" value="Shell Sort" onclick="setShellSortValue();" /> <br /> <h3>希尔排序(Shell Sort)</h3> <ul> <li>希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。</li> <li>希尔排序是<mark>非稳定</mark>排序算法。</li> <li>希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。</li> <li>一般的初次取序列的一半为增量,以后每次减半,直到增量为1。</li> <li>最后一个增量必须为1;</li> <li>时间复杂度和增量的设定有关介于O(nLogn)与O(n<sup>2</sup>)之间,一般O(n<sup>1.3</sup>)</li> </ul> </aside> <section id="mainArea"> </section> <footer> 这是底部信息 </footer> </body> </html>