<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] ## 算法原理 設有一組關鍵字{K1, K2,…, Kn};排序開始就認為 K1?是一個有序序列;讓 K2?插入上述表長為 1 的有序序列,使之成為一個表長為 2 的有序序列;然后讓 K3?插入上述表長為 2 的有序序列,使之成為一個表長為 3 的有序序列;依次類推,最后讓 Kn?插入上述表長為 n-1 的有序序列,得一個表長為 n 的有序序列。 具體算法描述如下: 1. 從第一個元素開始,該元素可以認為已經被排序 2. 取出下一個元素,在已經排序的元素序列中從后向前掃描 3. 如果該元素(已排序)大于新元素,將該元素移到下一位置 4. 重復步驟 3,直到找到已排序的元素小于或者等于新元素的位置 5. 將新元素插入到該位置后 6. 重復步驟 2~5 如果比較操作的代價比交換操作大的話,可以采用[二分查找法](http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E6%B3%95)來減少比較操作的數目。該算法可以認為是插入排序的一個變種,稱為**二分查找排序**。 > 二分查找法,是一種在有序數組中查找某一特定元素的搜索算法。搜素過程從數組的中間元素開始,如果中間元素正好是要查找的元素,則搜素過程結束;如果某一特定元素大于或者小于中間元素,則在數組大于或小于中間元素的那一半中查找,而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空,則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。 [![圖片來自維基百科](http://bubkoo.qiniudn.com/Insertion_sort_animation.gif)](https://box.kancloud.cn/2015-07-26_55b457a6cf263.gif "圖片來自維基百科") 圖片來自維基百科 ## 實例分析 現有一組數組 arr = [5, 6, 3, 1, 8, 7, 2, 4],共有八個記錄,排序過程如下: ~~~ [5] 6 3 1 8 7 2 4 ↑ │ └───┘ [5, 6] 3 1 8 7 2 4 ↑ │ └────────┘ [3, 5, 6] 1 8 7 2 4 ↑ │ └──────────┘ [1, 3, 5, 6] 8 7 2 4 ↑ │ └──┘ [1, 3, 5, 6, 8] 7 2 4 ↑ │ └────┘ [1, 3, 5, 6, 7, 8] 2 4 ↑ │ └────────────────┘ [1, 2, 3, 5, 6, 7, 8] 4 ↑ │ └─────────────┘ [1, 2, 3, 4, 5, 6, 7, 8] ~~~ 其中有一點比較有意思的是,在每次比較操作發現新元素小于等于已排序的元素時,可以將已排序的元素移到下一位置,然后再將新元素插入該位置,接著再與前面的已排序的元素進行比較,這樣做交換操作代價比較大。還有一個做法是,將新元素取出,從左到右依次與已排序的元素比較,如果已排序的元素大于新元素,那么將該元素移動到下一個位置,接著再與前面的已排序的元素比較,直到找到已排序的元素小于等于新元素的位置,這時再將新元素插入進去,就像下面這樣: [![圖片來自維基百科](http://bubkoo.qiniudn.com/Insertion-sort-example-300px.gif)](https://box.kancloud.cn/2015-07-26_55b457b1395cd.gif "圖片來自維基百科") 圖片來自維基百科 ## JavaScript 語言實現 直接插入排序 JavaScript 實現代碼: ~~~ function insertionSort(array) { function swap(array, i, j) { var temp = array[i]; array[i] = array[j]; array[j] = temp; } var length = array.length, i, j; for (i = 1; i < length; i++) { for (j = i; j > 0; j--) { if (array[j - 1] > array[j]) { swap(array, j - 1, j); } else { break; } } } return array; } ~~~ 下面這種方式可以減少交換次數: ~~~ function insertionSort(array) { var length = array.length, i, j, temp; for (i = 1; i < length; i++) { temp = array[i]; for (j = i; j >= 0; j--) { if (array[j - 1] > temp) { array[j] = array[j - 1]; } else { array[j] = temp; break; } } } return array; } ~~~ 利用二分查找法實現的插入排序,**二分查找排序**: ~~~ function insertionSort2(array) { function binarySearch(array, start, end, temp) { var middle; while (start <= end) { middle = Math.floor((start + end) / 2); if (array[middle] < temp) { if (temp <= array[middle + 1]) { return middle + 1; } else { start = middle + 1; } } else { if (end === 0) { return 0; } else { end = middle; } } } } function binarySort(array) { var length = array.length, i, j, k, temp; for (i = 1; i < length; i++) { temp = array[i]; if (array[i - 1] <= temp) { k = i; } else { k = binarySearch(array, 0, i - 1, temp); for (j = i; j > k; j--) { array[j] = array[j - 1]; } } array[k] = temp; } return array; } return binarySort(array); } ~~~ ## 參考文章 * [Wikipedia](http://en.wikipedia.org/wiki/Insertion_sort) * [維基百科 - 插入排序](http://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F) * [維基百科 - 二分查找法](http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE%E6%B3%95) * [排序算法—折半插入排序(二分查找排序)](http://hualang.iteye.com/blog/1187110) * [直接插入排序](http://sjjg.js.zwu.edu.cn/SFXX/paixu/paixu6.2.1.html) * [直接插入排序基本思想](http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.2.1.1.htm)
                  <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>

                              哎呀哎呀视频在线观看