首页 > 代码库 > Html5 希尔排序演示

Html5 希尔排序演示

希尔排序(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

 

Html5 希尔排序演示