希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。 如下圖所示： 代碼如下： 1 <!DOCTYPE html> 2 <html> 3 <head> 4 <title>The eleven html page</title> 5 <styl ...
希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。
如下圖所示：
代碼如下：
1 <!DOCTYPE html> 2 <html> 3 <head> 4 <title>The eleven html page</title> 5 <style type="text/css"> 6 ul li 7 { 8 list-style-type:georgian; 9 text-align:left; 10 } 11 .mark 12 { 13 width:140px; 14 height:40px; 15 color:Olive; 16 text-align:center; 17 line-height:40px; 18 margin:5px; 19 float:left; 20 } 21 .redball 22 { 23 width:40px; 24 height:40px; 25 border-radius:20px; 26 background-color:Red; 27 text-align:center; 28 line-height:40px; 29 margin:5px; 30 float:left; 31 } 32 .ball 33 { 34 width:40px; 35 height:40px; 36 border-radius:20px; 37 background-color:Aqua; 38 text-align:center; 39 line-height:40px; 40 margin:5px; 41 float:left; 42 } 43 .line 44 { 45 clear:left; 46 } 47 header 48 { 49 height:80px; 50 border:1px solid gray; 51 } 52 .left 53 { 54 border:1px solid gray; 55 float:left; 56 width:30%; 57 height:480px; 58 margin-left:0px; 59 margin-right:0px; 60 61 } 62 aside 63 { 64 text-align:center; 65 } 66 section 67 { 68 width:69.5%; 69 float:left; 70 height:480px; 71 border:1px solid gray; 72 margin-left:0px; 73 margin-right:0px; 74 } 75 footer 76 { 77 clear:left; 78 height:60px; 79 border:1px solid gray; 80 } 81 input[type="button"] 82 { 83 width:80px; 84 text-align:center; 85 margin-top:10px; 86 } 87 </style> 88 <script type="text/javascript"> 89 function initDiv() { 90 var mainArea = document.getElementById("mainArea"); 91 for (var i = 0; i < 8; i++) { 92 var newDivLine = document.createElement("div"); 93 newDivLine.setAttribute("class", "line"); 94 mainArea.appendChild(newDivLine); 95 for (var j = 0; j < 9; j++) { 96 var newDiv = document.createElement("div"); 97 var id = i.toString() + j.toString(); 98 newDiv.setAttribute("id", id); 99 if (j < 8) { 100 newDiv.setAttribute("class", "ball"); 101 } else { 102 newDiv.setAttribute("class", "mark"); 103 } 104 newDivLine.appendChild(newDiv); 105 } 106 } 107 } 108 109 //初始元素賦值 110 var arrTmp = [4, 6, 8, 7, 9, 2, 10, 1]; 111 function setElementsValue() { 112 for (var i = 0; i < arrTmp.length; i++) { 113 document.getElementById("0" + i.toString()).innerText = arrTmp[i]; 114 } 115 document.getElementById("08").innerText = "原始數據"; 116 } 117 118 //希爾排序 119 function setShellSortValue() { 120 var m = 0;//表示第幾趟排序 121 //d的值，4,2,1，表示增量 122 for (var d = Math.floor(arrTmp.length / 2); d > 0; d = Math.floor(d / 2)) { 123 //第一次，d=4,迴圈次數，依次比較0,4/1,5/2,6/3,7 124 var atmp = new Array(); 125 var n=0; 126 for (var i = d; i < arrTmp.length; i++) { 127 //如果第i個元素，小於第i-d個元素，則需要移動，否則不需要移動 128 if (arrTmp[i]<arrTmp[i - d] ) { 129 var j = i - d; //依次比較j和d+j個元素的大小 130 while (j >= 0) { 131 if (arrTmp[j] > arrTmp[d + j]) { 132 var temp = arrTmp[j]; 133 arrTmp[j] = arrTmp[d + j]; 134 arrTmp[d + j] = temp; 135 atmp[n]=(d + j); 136 n=n+1; 137 } 138 j -= d; 139 } 140 } 141 } 142 m = m + 1; 143 //顯示出來 144 for (var k = 0; k < arrTmp.length; k++) { 145 document.getElementById((m).toString() + k.toString()).innerText = arrTmp[k]; 146 for(var n=0;n<atmp.length;n++){ 147 if(atmp[n] ==k){ 148 document.getElementById((m).toString() + (atmp[n]).toString()).setAttribute("class", "redball"); 149 } 150 } 151 } 152 document.getElementById((m).toString() + "8").innerText = "第 " + (m).toString() + " 趟排序（d="+d+"）"; 153 154 } 155 } 156 157 </script> 158 </head> 159 <body> 160 <header> 161 <h1>希爾排序(Shell Sort)Demo</h1> 162 </header> 163 <aside class="left"> 164 165 <input type="button" id="btnInit" value="Init" onclick="initDiv();" /> 166 <br /> 167 <input type="button" id="btnSetValue" value="SetValue" onclick="setElementsValue();" /> 168 <br /> 169 <input type="button" id="btnSort" value="Shell Sort" onclick="setShellSortValue();" /> 170 <br /> 171 <h3>希爾排序(Shell Sort)</h3> 172 <ul> 173 <li>希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序演算法的一種更高效的改進版本。</li> 174 <li>希爾排序是<mark>非穩定</mark>排序演算法。</li> 175 <li>希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，演算法便終止。</li> 176 <li>一般的初次取序列的一半為增量，以後每次減半，直到增量為1。</li> 177 <li>最後一個增量必須為1；</li> 178 <li>時間複雜度和增量的設定有關介於O(nLogn)與O(n<sup>2</sup>)之間，一般O(n<sup>1.3</sup>)</li> 179 </ul> 180 </aside> 181 <section id="mainArea"> 182 183 </section> 184 <footer> 185 這是底部信息 186 </footer> 187 </body> 188 </html>View Code
