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ù)排序，堆排序，希爾排序，歸并排序，計數(shù)排序）
- golang/python實(shí)現(xiàn)歸并排序?qū)嵗a
- python基本算法之實(shí)現(xiàn)歸并排序(Merge sort)
相關(guān)文章
這篇文章主要介紹了Python3 pandas 操作列表實(shí)例詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-09-09
yolov5的特征提取網(wǎng)絡(luò)兼顧速度與精度,將PAN與PFN深度融合,對不同尺度魯棒性強(qiáng),可以即插即用,后接不同的檢測器,下面這篇文章主要給大家介紹了關(guān)于如何通過底層源碼理解YOLOv5的Backbone的相關(guān)資料,需要的朋友可以參考下2022-05-05
這篇文章主要介紹了Python中使用gzip模塊壓縮文件的簡單教程,本文的例子主要針對類UNIXZ系統(tǒng),需要的朋友可以參考下2015-04-04
這篇文章主要介紹了如何把Python腳本導(dǎo)出為exe程序的方法，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-03-03
今天小編就為大家分享一篇python 分離文件名和路徑以及分離文件名和后綴的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-10-10
Python代碼實(shí)現(xiàn)列表分組計數(shù)
這篇文章主要介紹了Python代碼實(shí)現(xiàn)列表分組計數(shù)，利用Python代碼實(shí)現(xiàn)了使用分組函數(shù)對列表進(jìn)行分組，并計算每組的元素個數(shù)的功能,需要的朋友可以參考一下2021-11-11
這篇文章主要介紹了python捕獲警告的三種方法，幫助大家更好的理解和學(xué)習(xí)使用python，感興趣的朋友可以了解下2021-03-03
基于Python和MoviePy實(shí)現(xiàn)照片管理和視頻合成工具
在這篇博客中,我們將詳細(xì)剖析一個基于 Python 的圖形界面應(yīng)用程序,該程序使用 wxPython 構(gòu)建用戶界面,并結(jié)合 MoviePy、Pillow 和 OpenCV 等庫實(shí)現(xiàn)照片管理和視頻合成功能,通過對代碼的逐部分分析,需要的朋友可以參考下2025-04-04
OpenCV每日函數(shù)之BarcodeDetector類條碼檢測器
OpenCV在V4.5.3版本的contrib包中提供了一個barcode::BarcodeDetector類，用于條形碼的識別，這篇文章主要介紹了OpenCV每日函數(shù)?BarcodeDetector條碼檢測器,需要的朋友可以參考下2022-06-06
Python中POST調(diào)用Restful接口示例
這篇文章主要介紹了Python之POST調(diào)用Restful接口示例，本文結(jié)合示例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2023-02-02