Python のソート アルゴリズムとは何ですか?

Python で一般的に使用されるソート アルゴリズムには、バブル ソート、挿入ソート、選択ソート、クイック ソート、マージ ソート、ヒープ ソートなどがあります。これらの並べ替えアルゴリズムの原理を以下に紹介し、対応するコード例を示します。

1. バブル ソート:
   バブル ソートは、シンプルで直感的な並べ替えアルゴリズムです。ソート対象のリストを繰り返し走査し、隣接する 2 つの要素のサイズを比較し、大きい方の要素を後方に移動します。各反復中に、最大の要素がリストの最後に「バブル」します。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

2. 挿入ソート:
   挿入ソートの基本的な考え方は、ソート対象の要素をソートされたリスト内の正しい位置に 1 つずつ挿入することです。挿入ソートは 2 番目の要素から開始され、各要素を以前にソートされたリストと比較して、適切な位置に挿入します。

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

3. 選択ソート:
   選択ソートは毎回リストを走査し、最小の要素を見つけて、それを現在の位置と交換します。リスト全体が並べ替えられるまで、このプロセスを繰り返します。

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

4. クイック ソート:
   クイック ソートは効率的な並べ替えアルゴリズムです。これは、分割統治の考え方を使用してリストを 2 つのサブリストに分割し、サブリストを再帰的に並べ替えます。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

5. マージ ソート:
   マージ ソートは、リストを 2 つのサブリストに分割し、各サブリストを並べ替えてから、並べ替えられたサブリストをマージします。

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

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

6. ヒープ ソート:
   ヒープ ソートは、ソートにバイナリ ヒープのプロパティを使用するツリー選択ソート アルゴリズムです。ヒープは最大ヒープと最小ヒープに分けられ、最大ヒープのルート ノードが最大の要素、最小ヒープのルート ノードが最小の要素になります。

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[i] < arr[left]:
        largest = left
    if right < n and arr[largest] < arr[right]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

上記は、Python で一般的に使用されるいくつかの並べ替えアルゴリズムであり、対応するコード例が提供されています。ソートアルゴリズムは状況やデータサイズに応じて異なりますので、状況に応じて適切なソートアルゴリズムを選択することで、プログラムの動作効率を向上させることができます。

以上がPython のソート アルゴリズムとは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。