python編程實(shí)現(xiàn)歸并排序
因?yàn)樯蟼€星期leetcode的一道題(Median of Two Sorted Arrays)所以想仔細(xì)了解一下歸并排序的實(shí)現(xiàn)。
還是先闡述一下排序思路：
首先歸并排序使用了二分法，歸根到底的思想還是分而治之。拿到一個長數(shù)組，將其不停的分為左邊和右邊兩份，然后以此遞歸分下去。然后再將她們按照兩個有序數(shù)組的樣子合并起來。這樣說起來可能很難理解，于是給出一張我畫的圖。
這里顯示了歸并排序的第一步，將數(shù)組按照middle進(jìn)行遞歸拆分，最后分到最細(xì)之后再將其使用對兩個有序數(shù)組進(jìn)行排序的方法對其進(jìn)行排序。
兩個有序數(shù)組排序的方法則非常簡單，同時對兩個數(shù)組的第一個位置進(jìn)行比大小，將小的放入一個空數(shù)組，然后被放入空數(shù)組的那個位置的指針往后 移一個，然后繼續(xù)和另外一個數(shù)組的上一個位置進(jìn)行比較，以此類推。到最后任何一個數(shù)組先出棧完，就將另外i一個數(shù)組里的所有元素追加到新數(shù)組后面。
由于遞歸拆分的時間復(fù)雜度是logN 然而，進(jìn)行兩個有序數(shù)組排序的方法復(fù)雜度是N該算法的時間復(fù)雜度是N*logN 所以是NlogN。
根據(jù)這波分析，我們可以看看對上圖的一個行為。
當(dāng)最左邊的分到最細(xì)之后無法再劃分左右然后開始進(jìn)行合并。
第一次組合完成[4, 7]的合并
第二次組合完成[4, 7, 8]的合并
第三次組合完成[3, 5]的合并
第四次組合完成[3, 5, 9]的合并
第五次組合完成[3, 4, 5, 7, 8, 9]的合并結(jié)束排序。
下面放上python的代碼
def merge(a, b): c = [] h = j = 0 while j < len(a) and h < len(b): if a[j] < b[h]: c.append(a[j]) j += 1 else: c.append(b[h]) h += 1 if j == len(a): for i in b[h:]: c.append(i) else: for i in a[j:]: c.append(i) return c def merge_sort(lists): if len(lists) <= 1: return lists middle = len(lists)/2 left = merge_sort(lists[:middle]) right = merge_sort(lists[middle:]) return merge(left, right) if __name__ == '__main__': a = [4, 7, 8, 3, 5, 9] print merge_sort(a)
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
- python 實(shí)現(xiàn)歸并排序算法
- Python編程中歸并排序算法的實(shí)現(xiàn)步驟詳解
- python實(shí)現(xiàn)歸并排序算法
- Python實(shí)現(xiàn)的歸并排序算法示例
- python實(shí)現(xiàn)折半查找和歸并排序算法
- Python排序搜索基本算法之歸并排序?qū)嵗治?/a>
- 10個python3常用排序算法詳細(xì)說明與實(shí)例（快速排序，冒泡排序，桶排序，基數(shù)排序，堆排序，希爾排序，歸并排序，計(jì)數(shù)排序）
- golang/python實(shí)現(xiàn)歸并排序?qū)嵗a
- python基本算法之實(shí)現(xiàn)歸并排序(Merge sort)
相關(guān)文章
今天小編就為大家分享一篇解決Python 中英文混輸格式對齊的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
一般查詢都是單條件查詢，F(xiàn)和Q是組合條件查詢，本文主要介紹了django中F與Q查詢的使用，感興趣的可以了解一下2021-06-06
Python中注釋（多行注釋和單行注釋）的用法實(shí)例
這篇文章主要給大家介紹了關(guān)于Python中注釋（多行注釋和單行注釋）用法的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用Python具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
這篇文章主要介紹了python 定時修改數(shù)據(jù)庫的示例代碼，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-04-04
教你漂亮打印Pandas DataFrames和Series
在今天的文章中,我們將探討如何配置所需的pandas選項(xiàng),這些選項(xiàng)將使我們能夠“漂亮地打印” pandas DataFrames,需要的朋友可以參考下2021-05-05
在本篇文章里小編給大家分享的是關(guān)于python編寫win程序的實(shí)例內(nèi)容，有需要的朋友們可以學(xué)習(xí)下。2020-06-06
這篇文章主要介紹了python logging日志打印過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-10-10
Python OpenCV高斯金字塔與拉普拉斯金字塔的實(shí)現(xiàn)
這篇文章主要介紹了Python OpenCV高斯金字塔與拉普拉斯金字塔的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-03-03
Python numpy 數(shù)組的向量化運(yùn)算操作方法
這篇文章主要介紹了Python numpy數(shù)組的向量化運(yùn)算操作方法，本文通過示例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-06-06
Python with關(guān)鍵字，上下文管理器，@contextmanager文件操作示例
這篇文章主要介紹了Python with關(guān)鍵字，上下文管理器，@contextmanager文件操作,結(jié)合實(shí)例形式分析了Python使用with關(guān)鍵字及上下文管理器、contextmanager進(jìn)行文件打開、讀寫、關(guān)閉等操作的相關(guān)實(shí)現(xiàn)技巧,需要的朋友可以參考下2019-10-10