간단 선택 정렬은 선택 정렬 알고리즘의 일종입니다. 기본 아이디어: 각 단계에서 정렬할 레코드 중에서 가장 작은 키워드가 있는 레코드를 선택하고 모든 정렬이 완료될 때까지 정렬된 레코드 순서의 마지막에 순서를 둡니다. 각 루프에서 동일한 값을 가진 요소의 위치가 변경되므로 불안정한 정렬입니다.
------------------------------- ------ -------------
아래와 같습니다:
간단한 선택 정렬을 위한 최적화 솔루션은 이진 선택 정렬을 사용하는 것입니다. 이는 각 사이클에서 두 요소(현재 패스의 최대 및 최소 레코드)의 위치를 결정하여 개수를 줄이도록 개선되었습니다. 정렬에 필요한 주기. 개선 후에는 n개의 데이터를 정렬하려면 최대 [n/2]개의 루프만 필요합니다.
아래 그림과 같습니다.
알고리즘의 원리는 자세히 설명하지 않습니다. Html5를 사용하여 간단한 선택을 구현합니다. 정렬 알고리즘과 데모 코드는 다음과 같습니다:
<!DOCTYPE html> <html> <head> <title>The thirteen html page</title> <style type="text/css"> ul li { list-style-type:georgian; text-align:left; } .mark { width:280px; 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:150px; text-align:center; margin-top:10px; } </style> <script type="text/javascript"> function initDiv() { var mainArea = document.getElementById("mainArea"); var childs = mainArea.childNodes; //添加节点之前先删除,应该从后往前删除,否则节点移动,只能删除一半 for (var i = childs.length - 1; i >= 0; i--) { mainArea.removeChild(childs[i]); } for (var i = 0; i < 8; i++) { var newDivLine = document.createElement("div"); newDivLine.setAttribute("class", "line"); newDivLine.setAttribute("id", i); 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); } } } //初始元素赋值 function setElementsValue() { var arrTmp = [4, 6, 8, 7, 9, 2, 10, 1]; for (var i = 0; i < arrTmp.length; i++) { document.getElementById("0" + i.toString()).innerText = arrTmp[i]; } document.getElementById("08").innerText = "原始数据"; } //简单选择排序 function setSimpleSortValue() { var arrTmp = [4, 6, 8, 7, 9, 2, 10, 1]; var m = 0;//表示要交换的最小坐标 for (var i = 0; i < arrTmp.length-1; i++) { m = i; for (var j = i + 1; j < arrTmp.length; j++) { if (arrTmp[m] > arrTmp[j]) { m = j; } } if (arrTmp[i] > arrTmp[m]) { var tmp = arrTmp[m]; arrTmp[m] = arrTmp[i]; arrTmp[i] = tmp; } //显示出来 for (var k = 0; k < arrTmp.length; k++) { document.getElementById((i+1).toString() + k.toString()).innerText = arrTmp[k]; if (i == k) { document.getElementById((i + 1).toString() + (k).toString()).setAttribute("class", "redball"); } else { document.getElementById((i + 1).toString() + (k).toString()).attributes["class"].nodeValue="ball";; } } document.getElementById((i+1).toString() + "8").innerText = "第 " + (i+1).toString() + " 趟排序(Min=" + arrTmp[i] + ")"; } } //二元选择排序 function setDoubleSelectSort() { var arrTmp = [4, 6, 8, 7, 9, 2, 10, 1]; selectSortB(arrTmp); var len=arrTmp.length; for (var i = (len / 2)+1; i < len; i++) { for (var j = 0; j < 8; j++) { document.getElementById((i).toString() + (j).toString()).innerText = ""; document.getElementById((i).toString() + (j).toString()).className="ball"; } document.getElementById(i.toString() + "8").innerText = ""; } } //二元选择排序(升序) function selectSortB(a) { var len = a.length; var temp, min, max; for (var i = 0; i < len / 2; i++) { min = i; max = i; for (var j = i + 1; j <= len - 1 - i; j++) { max = (a[j] > a[max]) ? j : max;//每一趟取出当前最大和最小的数组下标 min = (a[j] < a[min]) ? j : min; }; temp = a[i];//先放小的 a[i] = a[min]; if (i == max) { //最大数在数组头部 if ((len - i - 1) !== min) {//最大数在头部,最小数在尾部 a[min] = a[len - i - 1]; } a[len - i - 1] = temp; } else if ((len - i - 1) === min) {//最大数不在头部,最小数在尾部 a[len - i - 1] = a[max]; a[max] = temp } else { //如果最大数在尾部,也是成立的,不用特殊讨论 a[min] = temp; temp = a[len - i - 1]; a[len - i - 1] = a[max]; a[max] = temp; } //显示出来 for (var k = 0; k < a.length; k++) { document.getElementById((i + 1).toString() + k.toString()).innerText = a[k]; if (i == k || len - i - 1 == k) { document.getElementById((i + 1).toString() + (k).toString()).setAttribute("class", "redball"); } else { document.getElementById((i + 1).toString() + (k).toString()).className = "ball"; } } document.getElementById((i + 1).toString() + "8").innerText = "第 " + (i + 1).toString() + " 趟排序(Min=" + a[i] + ",Max=" + a[len-i-1] + ")"; } } </script> </head> <body> <header> <h1>简单选择排序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="btnSimpleSort" value="Simple Select Sort" onclick="setSimpleSortValue();" /> <br /> <input type="button" id="btnDoubleSelect" value="Double Select Sort" onclick="setDoubleSelectSort();" /> <br /> <h3>简单选择排序</h3> <ul> <li>设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录(Ri,Ri+1,…,Rn)中找出排序码最小的记录,与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。</li> <li>简单选择排序<mark>非稳定</mark>排序算法。</li> <li>在简单选择排序过程中,所需移动记录的次数比较少。</li> <li>进行比较操作的时间复杂度为O(n<sup>2</sup>),进行移动操作的时间复杂度为O(n)</li> <li>简单选择排序的优化方案是二元选择排序法,将其改进为每趟循环确定两个元素(当前趟最大和最小记录)的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序,最多只需进行[n/2]趟循环</li> </ul> </aside> <section id="mainArea"></section> <footer> 这是底部信息 </footer> </body> </html>
코드 보기
바이너리 선택 정보 정렬의 특수 처리:
일반적으로 간단한 교환이면 충분합니다.
a[i]=a[max], a[len-1-i]=a[min] 등 4개의 값이 동일한 경우 특수한 경우가 발생합니다.
코드에서는 먼저 a[i]에 최소값 min을 할당하고 동시에 a[i]의 값을 꺼내기로 선택한 다음 코드에서 세 가지 상황을 논의했습니다.
①: max가 배열의 선두에 있을 때 min이 배열의 tail에 있는지 여부는 조건 ①에서 논의됩니다.
②: min이 배열의 tail에 있을 때; (그리고 max는 배열의 선두에 있지 않습니다)
3: 일반적으로 [min은 배열의 선두에 있고, max는 배열의 꼬리에 있습니다]
에도 동일하게 적용됩니다. Html5를 사용하여 간단한 선택 정렬 알고리즘 및 데모를 구현하는 방법에 대한 더 많은 관련 기사를 보려면 PHP 중국어 웹사이트를 주목하세요!