<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                [TOC] ## 算法原理 > 基數排序 (Radix Sort) 是一種非比較型整數排序算法,其原理是將整數按位數切割成不同的數字,然后按每個位數分別比較。基數排序的發明可以追溯到 1887 年[赫爾曼·何樂禮](http://zh.wikipedia.org/wiki/%E8%B5%AB%E7%88%BE%E6%9B%BC%C2%B7%E4%BD%95%E6%A8%82%E7%A6%AE)在[打孔卡片制表機 (Tabulation Machine)](http://zh.wikipedia.org/w/index.php?title=%E6%89%93%E5%AD%94%E5%8D%A1%E7%89%87%E5%88%B6%E8%A1%A8%E6%9C%BA&action=edit&redlink=1)上的貢獻。 排序過程:將所有待比較數值(**正整數**)統一為同樣的數位長度,數位較短的數前面補零。然后,從最低位開始,依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列。 基數排序法會使用到桶 (Bucket),顧名思義,通過將要比較的位(個位、十位、百位…),將要排序的元素分配至 0~9 個桶中,借以達到排序的作用,在某些時候,基數排序法的效率高于其它的比較性排序法。 [Data Structure Visualizations](http://www.cs.usfca.edu/~galles/visualization/RadixSort.html)?提供了一個基數排序的分步動畫演示。 ## 實例分析 基數排序的方式可以采用 LSD (Least sgnificant digital) 或 MSD (Most sgnificant digital),LSD 的排序方式由鍵值的最右邊開始,而 MSD 則相反,由鍵值的最左邊開始。 以 LSD 為例,假設原來有一串數值如下所示: ~~~ 36 9 0 25 1 49 64 16 81 4 ~~~ 首先根據個位數的數值,按照個位置等于桶編號的方式,將它們分配至編號0到9的桶子中: | 編號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | 0 | 1 | | | 64 | 25 | 36 | | | 9 | | | | 81 | | | 4 | | 16 | | | 49 | 然后,將這些數字按照桶以及桶內部的排序連接起來: ~~~ 0 1 81 64 4 25 36 16 9 49 ~~~ 接著按照十位的數值,分別對號入座: | 編號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | 0 | 16 | 25 | 36 | 49 | | 64 | | 81 | | | | 1 | | | | | | | | | | | | 4 | | | | | | | | | | | | 9 | | | | | | | | | | 最后按照次序重現連接,完成排序: ~~~ 0 1 4 9 16 25 36 49 64 81 ~~~ ## JavaScript 語言實現 暴力上代碼: ~~~ function radixSort(array) { var bucket = [], l = array.length, loop, str, i, j, k, t, max = array[0]; for (i = 1; i < l; i++) { if (array[i] > max) { max = array[i] } } loop = (max + '').length; for (i = 0; i < 10; i++) { bucket[i] = []; } for (i = 0; i < loop; i++) { for (j = 0; j < l; j++) { str = array[j] + ''; if (str.length >= i + 1) { k = parseInt(str[str.length - i - 1]); bucket[k].push(array[j]); } else { // 高位為 0 bucket[0].push(array[j]); } } array.splice(0, l); for (j = 0; j < 10; j++) { t = bucket[j].length; for (k = 0; k < t; k++) { array.push(bucket[j][k]); } bucket[j] = []; } } return array; } ~~~ ## 參考文章 * [維基百科,自由的百科全書](http://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F) * [Data Structure Visualizations](http://www.cs.usfca.edu/~galles/visualization/RadixSort.html) * [Algorithm Gossip: 基數排序法](http://openhome.cc/Gossip/AlgorithmGossip/RadixSort.htm) * [Radix Sorting](https://www.cs.auckland.ac.nz/software/AlgAnim/radixsort.html)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看