用Html5實作簡單選擇排序演算法和演示，附程式碼
- PHPz原創
- 2017-03-05 11:31:583100瀏覽
簡單選擇排序，是選擇排序演算法的一種。基本概念：每趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排序的記錄序列末尾，直到全部排序結束為止。由於在每次循環中，會對數值相等的元素改變位置，所以屬於非穩定排序。
-------------------------------------------- --------------------------
如下圖：
#對簡單選擇排序的最佳化方案，是採用二元選擇排序，即將其改進為每個循環確定兩個元素（當前趟最大和最小記錄）的位置,從而減少排序所需的循環次數。改進後將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>
#View Code
關於二元選擇排序的特殊處理：
一般情況下進行簡單的交換即可。
特殊情況出現在當4個數值中有相同時，例如a[i]=a[max],a[len-1-i]=a[min]。
在程式碼裡，我選擇先把最小值min賦給a[i],同時把a[i]的值取出來，之後在程式碼裡分別討論了三種情況
①：當max是數組頭部時，在①條件下又討論了min在不在數組尾部的情況；
②：當min是數組尾部時（且max不在數組頭部）
③：一般情況，同樣適用於【min在數組頭部，max在數組尾部】
更多關於用Html5實現簡單選擇排序演算法和演示的相關文章，請關注php中文網！
陳述：
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn