歸併排序的Python程序
已發表: 2023-01-31作為一種多範式編程語言，具有結構化、面向對象的設計方法和簡單整潔的句法和文法，Python 正迅速成為從事各種複雜性和規模項目的程序員的首選語言。
Python 提供了一個預構建算法的模塊化庫，允許其用戶執行各種操作，這些操作可以幫助他們自己完成任務，或者作為實現更大、更複雜目標的一個步驟。 一種更流行的此類算法是啟用合併排序功能的算法。
目錄
什麼是歸併排序？
它是一種通用的排序技術，使用戶能夠從任何來源獲取任何類型的隨機數據集，並將其分成重複的階段，直到最終將其分解為各個組成部分——一種遞歸技術，通常稱為“分而治之”的方法。
然後，該算法將各個組件放在一起——再次重複階段——但在沿途的每個階段將它們分類為預先確定的邏輯序列，使用基本比較和交換，直到整個數據系列按照所需的邏輯序列重新構建.
在 upGrad 查看我們的其他數據科學課程。
分而治之技術
以字母表中字母的隨機數據集為例：N、H、V、B、Q、D、Z、R。
步驟 1 ：原始數據集首先被分成兩組，如下所示：
N, H, V, B Q, D, Z, R
第 2 步：兩個結果數組都進一步細分如下：
N, H V, B Q, D Z, R
第 3 步：最後，所有四個數組都被進一步拆分，直到整個數據系列被分解成各個部分：
N H V B Q D Z R
然後該過程反轉，各個數據點現在開始以分階段的方式合併。 但是在這個合併過程中，每個子數組中的每個元素都會被評估和交換，以便它們按照邏輯順序（字母順序）對自己進行排序，如下所示：
第 4 步：單個元素合併成對，同時根據需要交換位置以形成正確的序列：
H, N B, V D, Q R, Z
第五步：合併和排序的遞歸過程繼續到下一次迭代：
B、H、N、V D、Q、R、Z
第 6 步：整個數據系列最終按其邏輯字母順序重組：
B、D、H、N、Q、R、V、Z
探索我們的熱門數據科學課程
| IIITB 的數據科學執行研究生課程 | 商業決策數據科學專業證書課程 | 亞利桑那大學數據科學碩士 |
| IIITB 的數據科學高級證書課程 | 馬里蘭大學數據科學和商業分析專業證書課程 | 數據科學課程 |
合併排序實現
在 Python 中有兩種實現合併排序的方法。 自上而下的方法和自下而上的方法。
自上而下的方法：
更常用的自上而下的方法是上面描述的方法。 它需要更長的時間並佔用更多的內存，因此在處理較小的數據集時效率低下。 但是，它要可靠得多，尤其是在應用於大型數據集時。
閱讀我們流行的數據科學文章
| 數據科學職業道路：綜合職業指南 | 數據科學職業發展：工作的未來就在這裡 | 為什麼數據科學很重要？ 數據科學為企業帶來價值的 8 種方式 |
| 數據科學對管理者的相關性 | 每個數據科學家都應該擁有的終極數據科學備忘單 | 你應該成為數據科學家的 6 大理由 |
| 數據科學家的一天：他們做什麼？ | 神話破滅：數據科學不需要編碼 | 商業智能與數據科學：有什麼區別？ |
輸入代碼：
def merge_sort (inp_arr):
大小 = len(inp_arr)
如果大小 > 1：
中間 = 大小 // 2
left_arr = inp_arr(:middle)
rIght_arr = inp_arr（中間：）
merge_sort(left_arr)
合併_sort（right_arr）
我 = 0
j = 0
k = 0
（其中i和j分別是遍歷數據序列左右兩邊的迭代器，k是整個數據序列的迭代器）。
left_size = len(left_arr)
右 _size = len(right_arr)
當 i < left_size 且 j < right size 時：
如果 left_arr(i) < right_arr(j):
inp_arr(k) – left_arr(i)
我 >= 1
別的：
inp_arr(k) = right_arr(j)
j += 1
k += 1
當我 < left_size:
inp_arr (k) = left_arr(i)
我 += 1
k += 1
而 j < right_size:
inp_arr (k) = right_arr(j)
j += 1
k += 1
inp_arr = (N, H, V, B, Q, D, Z, R)
打印（：輸入數組：\n”）
打印（inp_arr）
merge_sort (inp_arr)
打印（“排序數組：\n”）
打印（inp_arr）
輸出：
輸入數組：N、H、V、B、Q、D、Z、R
輸出數組：B、D、H、N、Q、R、V、Z
自下而上的方法：
自下而上的方法速度更快，佔用的內存更少，並且可以高效地處理較小的數據集，但在處理大型數據集時可能會遇到問題。 因此使用頻率較低。
輸入代碼：
def 合併（左，右）：
結果 = [] x, y = 0, 0
對於範圍內的 k（0，len（左）+ len（右））：
if i == len(left): # 如果在上半場結束時，
result.append(right[j]) # 添加第二部分的所有值
j += 1
elif j == len(right): # 如果在下半場結束時，
result.append(left[x]) # 添加第一半的所有值
我 += 1
elif 右 [j] < 左 [i]:
結果.追加（右[j]）
j += 1
別的：
結果.追加（左[i]）
我 += 1
返回結果
def mergesort（ar_list）：
長度 = len(ar_list)
大小 = 1
而大小 < 長度：
size+=size # 按照描述初始化為 2
對於範圍內的位置（0，長度，大小）：
開始=位置
中間 = 位置 + 整數（大小 / 2）
結束 = 位置 + 大小
left = ar_list[開始：mid] right = ar_list[mid：end]
ar_list[開始：結束] = 合併（左，右）
返回 ar_list
ar_list = [N, H, V, B, Q, D, Z, R] print(mergesort(ar_list))
輸出：
輸入數組：N、H、V、B、Q、D、Z、R
輸出數組：B、D、H、N、Q、R、V、Z
適用於更複雜的真實數據集的合併排序實現
讓我們將自上而下的方法應用於印度的四輛隨機越野車：
品牌 | 模型 | 千萬盧比的展廳前價格 |
| 吉普車 | 牧馬人 | 0.58 |
| 福特 | 努力 | 0.35 |
| 捷豹路虎 | 路虎攬勝運動版 | 2.42 |
| 奔馳 | G級 | 1.76 |
輸入代碼：
類車：
def __init__（自我，品牌，型號，價格）：
self.brand = 品牌
self.model = 模型
self.price = 價格
定義__str __（自我）：
return str.format(“品牌：{}，型號：{}，價格：{}”，self.brand,
self.model, self.price)
def merge(list1, i, j, k, comp_fun):
left_copy = list1[i:k + 1]
r_sublist = list1[k+1:r+1]
left_copy_index = 0
j_sublist_index = 0
排序索引=我
而left_copy_index < len(left_copy)和j_sublist_index <
len(j_sublist):
如果comp_fun(left_copy[left_copy_index], j_sublist[j_sublist_index]):
list1[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
其他：
list1[sorted_index] = j_sublist[j_sublist_index]
j_sublist_index = j_sublist_index + 1
排序索引 = 排序索引 + 1
而left_copy_index < len(left_copy):
list1[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
排序索引 = 排序索引 + 1
而j_sublist_index < len(j_sublist):
list1[sorted_index] = j_sublist[j_sublist_index]
j_sublist_index = j_sublist_index + 1
排序索引 = 排序索引 + 1
def merge_sort(list1, i, j, comp_fun):
如果我 >= j:
返回
k = (i + j)//2
merge_sort(list1, i, k, comp_fun)
merge_sort(list1, k + 1, j, comp_fun)
合併（list1，i，j，k，comp_fun）
car1 = Car(“Jeep”, “Wrangler”, 0.58)
car2 = 汽車（“福特”，“奮進”，0.35）
car3 = Car(“Jaguar Land Rover”, “Range Rover Sport”, 1.76)
car4 = Car(“奔馳”, “G級”, 2.42)
list1 = [car1, car2, car3, car4]
merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.brand < carB.brand)
打印（“按品牌分類的汽車：”）
對於列表 1中的汽車：
打印（汽車）
打印()
merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.price< carB.price)
打印（“汽車按價格排序：”）
對於列表 1中的汽車：
打印（汽車）
輸出：
按品牌分類的汽車：
福特奮進號
捷豹路虎攬勝運動版
吉普牧馬人
奔馳G級
按價格排序的汽車：
福特奮進號
吉普牧馬人
捷豹路虎攬勝
奔馳G級
您可以通過馬里蘭大學的 upGrad 數據科學和商業分析專業證書學習 Python 的理論和實踐方面。 本課程可幫助您從頭開始學習 Python。 即使您是編程和編碼的新手，upGrad 也會為您提供為期兩週的預備課程，以便您掌握編程的基礎知識。 在從事多個行業項目時，您將學習各種工具，如 Python、SQL 等。
