Pythonを使用してマージソートを実装する方法

マージ ソートは古典的なソート アルゴリズムです。その中心的な考え方は、ソート対象の配列をいくつかのサブ配列に分割し、これらのサブ配列をソートし、最後にソートされたサブ配列を順序付けされた配列にマージすることです。マージ ソートは、時間計算量が O(nlogn) の比較的効率的なソート アルゴリズムです。

この記事では、Pythonでマージソートを実装する方法を説明します。

1. マージ ソートの実装のアイデア

マージ ソートの実装のアイデアには、分割統治とマージの 2 つの部分が含まれます。具体的な実装手順は次のとおりです:

1) ソート対象の配列を連続的に 2 つの部分に分割し、左部分と右部分を再帰的にソートします;

2) ソートされた左部分と右部分をマージします。部分を順序付けられた配列に変換します。

2. Python を使用して分割統治を実装する

分割統治はマージ ソートの中心的なアイデアです。最初に分割統治の部分を実装する必要があります。

コードは次のとおりです:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

この関数では、まず配列の長さが 1 以下であるかどうかを判断し、次に配列を直接返します。それ以外の場合は、配列を 2 つに分割し、左側と右側の部分をそれぞれ再帰的に並べ替えて、最後に並べ替えられた左側と右側の部分をマージする必要があります。

2.1 マージの実装

分割統治に基づいて、マージされた部分を実装する必要があります。

コードは次のとおりです:

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

この関数では、まず、左側と右側の部分でそれぞれ比較される要素を指すポインター i と j を初期化します。次に、継続的に左と右の要素を比較し、小さい方の要素を結果リストに追加し、ポインタを右に移動します。最後に、残りのすべての要素を結果のリストに追加して、ソートされた配列が完成します。

3. 完全なコード

分割統治部分とマージ部分を組み合わせると、完全なコードは次のようになります:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

4. Test

マージソートコードが正しいことを確認するには、テストする必要があります。

コードは次のとおりです:

arr = [5, 3, 8, 6, 4, 7, 2, 1]
print(merge_sort(arr))

出力結果は次のとおりです:

[1, 2, 3, 4, 5, 6, 7, 8]

テスト 結果は、マージソートコードが正しいことを示しています。

以上がPythonを使用してマージソートを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。