ホームページ >ウェブフロントエンド >H5 チュートリアル >HTML5 を使用して、コードを添付した簡単な選択並べ替えアルゴリズムとデモンストレーションを実装します。

HTML5 を使用して、コードを添付した簡単な選択並べ替えアルゴリズムとデモンストレーションを実装します。

PHPz
PHPzオリジナル
2017-03-05 11:31:583134ブラウズ

単純選択ソートは、選択ソートアルゴリズムの一種です。基本的な考え方: 各パスでは、ソート対象のレコードから最小のキーワードを持つレコードが選択され、すべてのソートが完了するまでソートされたレコード シーケンスの最後に順序が配置されます。ループごとに同じ値を持つ要素の位置が変わるため、不安定なソートとなります。

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

下の図に示すように:

単純な選択ソートの最適化ソリューションは、次のとおりです。バイナリ選択ソート、つまり、ループごとに 2 つの要素 (現在のサイクルの最大レコードと最小レコード) の位置を決定することで、ソートに必要なループの数が削減されます。改善後は、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

二項選択ソートの特殊処理について:

一般的には、単純な交換で十分です。

a[i]=a[max]、a[len-1-i]=a[min] など、4 つの値が同じ場合に特殊なケースが発生します。 コードでは、最初に最小値minをa[i]に代入し、同時にa[i]の値を取り出すことにしました

①:maxが条件①の下で、min が配列の末尾にある場合の状況についても説明しました

②: min が配列の末尾にある場合 (そして max が配列の先頭にない場合)

③: 一般に、[min は配列の先頭、max は配列の末尾] にも同じことが当てはまります

HTML5 を使用した単純な選択ソート アルゴリズムとデモの実装に関するその他の関連記事については、 phpの中国語サイトです!

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。