アルゴリズムの簡単な説明(一)——JavaScript
51298 ワード
入門レベルアルゴリズム-線形検索-時間複雑度O(n)–アルゴリズムの世界におけるハロルドに相当します.
//リニアサーチ(入門ハロルド)
//Aは配列で、xは検索する値です.
//二分検索
//Aは昇順で配列されている行列で、xはクエリーの要素です.
//ターゲット要素の下付き文字を返します.
//発泡体の並べ替え
//並べ替えの選択
//考え方:最小値の下マークを見つけて交換する
//並べ替えの挿入
//現在の元素の前の元素がすでに順番に並んでいると仮定して、まず自分の位置を空にして、
//そして前の方が自分より大きい元素を順に後ろに動かして、穴が一つ空くまで移動します.
//そしてターゲット要素を「ピット」に挿入します.
//文字列反転(例えばABC->CBA)
比較的簡単な並べ替えアルゴリズム、すなわち時間複雑度はO(N^2)の順序付けアルゴリズムに基づいて、一般的には安定した並べ替えであると考えられている.
他の先進的な並べ替えアルゴリズム、例えば、規格化、積み上げ、バケツ並べ替えなど(通常、このようなアルゴリズムの時間複雑度はn*LogNに最適化されてもよい)、一般的には不安定な並べ替えと考えられています.
シングルリスト実現
//リニアサーチ(入門ハロルド)
//Aは配列で、xは検索する値です.
<code class="hljs matlab has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-title" style="box-sizing: border-box;">linearSearch</span><span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(A, x)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (var <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span> = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span> < <span class="hljs-transposed_variable" style="box-sizing: border-box;">A.</span><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">length</span>; <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span>++) <span class="hljs-cell" style="box-sizing: border-box;">{
if (A[i] == x) {
return i;
}</span>
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;
} </code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li></ul>
二分割検索(半値検索ともいう)-並び順の線形構造-時間複雑度O(logN)に適用されます.//二分検索
//Aは昇順で配列されている行列で、xはクエリーの要素です.
//ターゲット要素の下付き文字を返します.
<code class="hljs javascript has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-title" style="box-sizing: border-box;">binarySearch</span><span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(A, x)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> low = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>, high = A.length - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (low <= high) {
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> mid = <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">Math</span>.floor((low + high) / <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">2</span>); <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (x == A[mid]) {
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> mid;
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (x < A[mid]) {
high = mid - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> {
low = mid + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;
}
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;
} </code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li></ul>
泡並べ替え→時間複雑度O(n^2)//発泡体の並べ替え
<code class="hljs javascript has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-title" style="box-sizing: border-box;">bubbleSort</span><span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(A)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; i < A.length; i++) {
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> sorted = <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">true</span>;
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// : </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> j = A.length - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j > i; j--) {
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (A[j] < A[j - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>]) {
swap(A, j, j - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>);
sorted = <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">false</span>;
}
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (sorted) {
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span>;
}
}
} </code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li></ul>
並べ替え→時間複雑度O(n^2)を選択します.//並べ替えの選択
//考え方:最小値の下マークを見つけて交換する
<code class="hljs matlab has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-title" style="box-sizing: border-box;">selectionSort</span><span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(A)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (var <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span> = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span> < <span class="hljs-transposed_variable" style="box-sizing: border-box;">A.</span><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">length</span> - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span>++) <span class="hljs-cell" style="box-sizing: border-box;">{
var k = i;
for (var j = i + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j < A.length; j++) {
if (A[j] < A[k]) {
k = j;
}</span>
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (k != <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span>) <span class="hljs-cell" style="box-sizing: border-box;">{
var t = A[k];
A[k] = A[i];
A[i] = t;
println(A);
}</span>
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> A;
} </code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li><li style="box-sizing: border-box; padding: 0px 5px;">32</li><li style="box-sizing: border-box; padding: 0px 5px;">33</li></ul>
並べ替えの挿入→時間複雑度O(n^2)//並べ替えの挿入
//現在の元素の前の元素がすでに順番に並んでいると仮定して、まず自分の位置を空にして、
//そして前の方が自分より大きい元素を順に後ろに動かして、穴が一つ空くまで移動します.
//そしてターゲット要素を「ピット」に挿入します.
<code class="hljs matlab has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-title" style="box-sizing: border-box;">insertSort</span><span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(A)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (var <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span> = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span> < <span class="hljs-transposed_variable" style="box-sizing: border-box;">A.</span><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">length</span>; <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span>++) <span class="hljs-cell" style="box-sizing: border-box;">{
var x = A[i];
for (var j = i - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j >= <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span> && A[j] > x; j--) {
A[j + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>] = A[j];
}</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (A<span class="hljs-matrix" style="box-sizing: border-box;">[j + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>]</span> != x) <span class="hljs-cell" style="box-sizing: border-box;">{
A[j + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>] = x;
println(A);
}</span>
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> A;
} </code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li></ul>
文字列反転–時間複雑度O(logN)//文字列反転(例えばABC->CBA)
<code class="hljs matlab has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-title" style="box-sizing: border-box;">inverse</span><span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(s)</span> {</span>
var arr = <span class="hljs-transposed_variable" style="box-sizing: border-box;">s.</span>split(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">''</span>);
var <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span> = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>, <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">j</span> = <span class="hljs-transposed_variable" style="box-sizing: border-box;">arr.</span><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">length</span> - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (<span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">i</span> < <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">j</span>) <span class="hljs-cell" style="box-sizing: border-box;">{
var t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i++;
j--;
}</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-transposed_variable" style="box-sizing: border-box;">arr.</span>join(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">''</span>);
} </code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li></ul>
安定性秩序化に関する結論:比較的簡単な並べ替えアルゴリズム、すなわち時間複雑度はO(N^2)の順序付けアルゴリズムに基づいて、一般的には安定した並べ替えであると考えられている.
他の先進的な並べ替えアルゴリズム、例えば、規格化、積み上げ、バケツ並べ替えなど(通常、このようなアルゴリズムの時間複雑度はn*LogNに最適化されてもよい)、一般的には不安定な並べ替えと考えられています.
シングルリスト実現
<code class="hljs xml has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-tag" style="color: rgb(0, 102, 102); box-sizing: border-box;"><<span class="hljs-title" style="box-sizing: border-box; color: rgb(0, 0, 136);">script</span> <span class="hljs-attribute" style="box-sizing: border-box; color: rgb(102, 0, 102);">type</span>=<span class="hljs-value" style="box-sizing: border-box; color: rgb(0, 136, 0);">"text/javascript"</span>></span><span class="javascript" style="box-sizing: border-box;">
<span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-title" style="box-sizing: border-box;">print</span><span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(msg)</span> {</span>
document.write(msg);
}
<span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-title" style="box-sizing: border-box;">println</span><span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(msg)</span> {</span>
print(msg + <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"<br/>"</span>);
}
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> Node = <span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(v)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.data = v; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.next = <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">null</span>; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// </span>
}
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> SingleLink = <span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">()</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.head = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">new</span> Node(<span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">null</span>); <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// , </span>
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.insert = <span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(v)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> p = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.head;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (p.next != <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">null</span>) {
p = p.next;
}
p.next = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">new</span> Node(v);
}
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.removeAt = <span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(n)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (n <= <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>) {
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span>;
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> preNode = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.getNodeByIndex(n - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>);
preNode.next = preNode.next.next;
}
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// N ( 0 )</span>
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//N , </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.getNodeByIndex = <span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(n)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> p = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.head;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (p.next != <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">null</span> && i < n) {
p = p.next;
i++;
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> p;
}
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// V ,</span>
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// ,</span>
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.getNodeByValue = <span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(v)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> p = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.head;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (p.next != <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">null</span>) {
p = p.next;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (p.data == v) {
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> p;
}
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">null</span>;
}
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.print = <span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">()</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> p = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">this</span>.head;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (p.next != <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">null</span>) {
p = p.next;
print(p.data + <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">" "</span>);
}
println(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">""</span>);
}
}
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// L </span>
<span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-title" style="box-sizing: border-box;">hasSameValueNode</span><span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(singleLink)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> i = singleLink.head;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (i.next != <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">null</span>) {
i = i.next;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> j = i;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (j.next != <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">null</span>) {
j = j.next;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (i.data == j.data) {
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">true</span>;
}
}
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">false</span>;
}
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// </span>
<span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">function</span> <span class="hljs-title" style="box-sizing: border-box;">reverseSingleLink</span><span class="hljs-params" style="color: rgb(102, 0, 102); box-sizing: border-box;">(singleLink)</span> {</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> arr = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">new</span> <span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">Array</span>();
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> p = singleLink.head;
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// , </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (p.next != <span class="hljs-literal" style="color: rgb(0, 102, 102); box-sizing: border-box;">null</span>) {
p = p.next;
arr.push(p.data);
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> newLink = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">new</span> SingleLink();
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// , </span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> i = arr.length - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i >= <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; i--) {
newLink.insert(arr[i]);
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> newLink;
}
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> linkTest = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">new</span> SingleLink();
linkTest.insert(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'A'</span>);
linkTest.insert(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'B'</span>);
linkTest.insert(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'C'</span>);
linkTest.insert(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'D'</span>);
linkTest.print();<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//A B C D</span>
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">var</span> newLink = reverseSingleLink(linkTest);
newLink.print();<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//D C B A</span>
</span><span class="hljs-tag" style="color: rgb(0, 102, 102); box-sizing: border-box;"></<span class="hljs-title" style="box-sizing: border-box; color: rgb(0, 0, 136);">script</span>></span> </code>