一、歸并排序

歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法采用經(jīng)典的分治（divide-and-conquer）策略（分治法將問題分(divide)成一些小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修補(bǔ)"在一起，即分而治之)，將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序，若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。

二、歸并排序的基本思想

將待排序序列R[0…n-1]看成是n個(gè)長度為1的有序序列，將相鄰的有序表成對歸并，得到n/2個(gè)長度為2的有序表；將這些有序序列再次歸并，得到n/4個(gè)長度為4的有序序列；如此反復(fù)進(jìn)行下去，最后得到一個(gè)長度為n的有序序列

三、歸并排序的算法描述

第一步：申請空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來存放合并后的序列
第二步：設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
第三步：比較兩個(gè)指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針超出序列尾，將另一序列剩下的所有元素直接復(fù)制到合并序列尾

歸并排序其實(shí)要做兩件事：

（1）“分解”——將序列每次折半劃分（遞歸實(shí)現(xiàn)）

（2）“合并”——將劃分后的序列段兩兩合并后排序

如何合并？
在每次合并過程中，都是對兩個(gè)有序的序列段進(jìn)行合并，然后排序。

這兩個(gè)有序序列段分別為 R[low, mid] 和 R[mid+1, high]。

先將他們合并到一個(gè)局部的暫存數(shù)組R2中，帶合并完成后再將R2復(fù)制回R中。

我們稱 R[low, mid] 第一段，R[mid+1, high] 為第二段。

每次從兩個(gè)段中取出一個(gè)記錄進(jìn)行關(guān)鍵字的比較，將較小者放入R2中，最后將各段中余下的部分直接復(fù)制到R2中。

經(jīng)過這樣的過程，R2已經(jīng)是一個(gè)有序的序列，再將其復(fù)制回R中，一次合并排序就完成了。

四、代碼實(shí)現(xiàn)過程(python)

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 找到中間索引
        L = arr[:mid]  # 左半部分
        R = arr[mid:]  # 右半部分

        merge_sort(L)  # 遞歸地排序左半部分
        merge_sort(R)  # 遞歸地排序右半部分

        # 合并兩個(gè)有序數(shù)組
        i = j = k = 0

        # 復(fù)制數(shù)據(jù)到臨時(shí)數(shù)組L[]
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        # 復(fù)制左半部分剩余的數(shù)據(jù)
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        # 復(fù)制右半部分剩余的數(shù)據(jù)
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

# 測試代碼
arr = [12, 11, 13, 5, 6, 7]
print("未排序的數(shù)組:", arr)
merge_sort(arr)
print("排序后的數(shù)組:", arr)

這個(gè)例子中，merge_sort函數(shù)首先找到數(shù)組的中間索引，然后將數(shù)組分為兩部分，遞歸地對這兩部分進(jìn)行排序。最后，使用一個(gè)循環(huán)將排序后的兩個(gè)數(shù)組合并為一個(gè)有序數(shù)組。

到此這篇關(guān)于python 歸并排序的文章就介紹到這了,更多相關(guān)python 歸并排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論