<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>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 歸并排序 ## 示意圖 ![冒泡排序示意圖](https://raw.githubusercontent.com/liuzhen153/play-algorithm-python/master/images/merge_sort.gif) ## 運作步驟 ### 遞歸法(Top-down) 1. 申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合并后的序列 2. 設定兩個指針,最初位置分別為兩個已經排序序列的起始位置 3. 比較兩個指針所指向的元素,選擇相對小的元素放入到合并空間,并移動指針到下一位置 4. 重復步驟3直到某一指針到達序列尾 5. 將另一序列剩下的所有元素直接復制到合并序列尾 ### 迭代法(Bottom-up) 原理如下(假設序列共有n個元素): 1. 將序列每相鄰兩個數字進行歸并操作,形成 `ceil(n/2)`個序列,排序后每個序列包含兩/一個元素 2. 若此時序列數不是1個則將上述序列再次歸并,形成 `ceil(n/4)`個序列,每個序列包含四/三個元素 3. 重復步驟2,直到所有元素排序完畢,即序列數為1 ## 算法分析 * 最壞時間復雜度 O(nlogn) * 最優時間復雜度 O(nlogn) * 平均時間復雜度 O(nlogn) ## 實現 ```Python def merge_sort(list): '''Python中的普通的歸并排序算法實現 :param list: 需要排序的數字列表 :return: 排序結果 ''' # 將left 和 right 按照大小排序 def merge(left, right): '''merge兩個list :param left: 列表left :param right: 列表right :return: merge結果 ''' result = [] while left and right: result.append(left.pop(0) if left[0] <= right[0] else right.pop(0)) return result + left + right if len(list) <= 1: return list # 只有一個元素時直接返回 mid = len(list) // 2 return merge(merge_sort(list[:mid]), merge_sort(list[mid:])) def merge_sort_fast(list): '''Python中的更快的歸并排序算法實現 :param list: 需要排序的數字列表 :return: 排序結果 ''' left, right = [], [] while len(list) > 1: min_one, max_one = min(list), max(list) left.append(min_one) right.append(max_one) list.remove(min_one) list.remove(max_one) right.reverse() return left + list + right ``` ## 測試 ``` $ python merge_sort.py 歸并排序>>> 請輸入需要排序的數字,用英文半角逗號隔開,直接回車則使用默認數據: 需要排序的數字為: 1,4,2,3.6,-1,0,25,-34,8,9,1,0 merge_sort結果為: -34,-1,0,0,1,1,2,3.6,4,8,9,25 運行一萬次,merge_sort耗時: 0.2273240089416504 merge_sort_fast結果為: -34,-1,0,0,1,1,2,3.6,4,8,9,25 運行一萬次,merge_sort_fast耗時: 0.07656192779541016 此例子中,merge_sort_fast的效率是merge_sort的倍數: 2.0 ``` # 代碼庫地址 [https://github.com/liuzhen153/play-algorithm-python](https://github.com/liuzhen153/play-algorithm-python)
                  <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>

                              哎呀哎呀视频在线观看