Html5 直接插入排序

编程爱好者联盟

2016-12-18

关注关注

直接插入排序算法(Straight Insertion Sort)，是排序算法中简单的一种算法，基本思想如下：

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

Html5 直接插入排序

-----------------------------------------------------------------------------------------------------------

具体代码如下：

Html5 直接插入排序

1 <!DOCTYPE html>
  2 <html>
  3 <head>
  4     <title>The tenth 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 setSISortValue() {
120             for (var i = 1; i < arrTmp.length; i++) {
121                 var m = 0;//为了记录插入的位置，方便标记
122                 //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
123                 if (arrTmp[i] < arrTmp[i - 1]) {
124                     var x = arrTmp[i]; //复制为哨兵(临时变量)，即存储待排序元素  
125                     var j = i - 1;
126                     arrTmp[i] = arrTmp[i - 1]; //先后移一个元素 
127 
128                     //循环查找在有序表的插入位置，如果要插入的值小于，则继续查找，并将元素后移。
129                     while (x < arrTmp[j]) {
130                         arrTmp[j + 1] = arrTmp[j];
131                         j--;
132                     }
133                     //查找完毕后，插入到正确位置（即要插入的值大于前面的元素）
134                     arrTmp[j + 1] = x;
135                     m = j + 1;
136                 } else {
137                     m = i;
138                 }
139                 //显示出来
140                 for (var k = 0; k < arrTmp.length; k++) {
141                     document.getElementById((i).toString() + k.toString()).innerText = arrTmp[k];
142                     if (m == k) {
143                         document.getElementById((i).toString() + (k).toString()).setAttribute("class", "redball");
144                     }
145                 }
146                 document.getElementById((i).toString() + "8").innerText = "第 " + (i).toString() + " 趟排序";
147             }
148         }
149 
150     </script>
151 </head>
152 <body>
153 <header>
154     <h1>直接插入排序(Straight Insertion Sort)Demo</h1>
155 </header>
156 <aside class="left">
157 
158 <input type="button" id="btnInit" value="Init" onclick="initDiv();" />
159 <br />
160 <input type="button" id="btnSetValue" value="SetValue" onclick="setElementsValue();" />
161 <br />
162 <input type="button" id="btnSort" value="Sort" onclick="setSISortValue();" />
163 <br />
164 <h3>直接插入排序(Straight Insertion Sort)</h3>
165 <ul>
166     <li>将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。</li>
167     <li>即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。</li>
168     <li>如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变。</li>
169     <li>从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。</li>
170     <li>时间复杂度O(n<sup>2</sup>)</li>
171 </ul>
172 </aside>
173 <section id="mainArea">
174     
175 </section>
176 <footer>
177     这是底部信息
178 </footer>
179 </body>
180 </html>

View Code

直接插入排序排序算法 html5