Python のソートアルゴリズムとは何ですか?-Python チュートリアル-php.cn

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

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

バブルソート:
バブルソートは、シンプルで直感的な並べ替えアルゴリズムです。ソート対象のリストを繰り返し走査し、隣接する 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

ログイン後にコピー

挿入ソート:
挿入ソートの基本的な考え方は、ソート対象の要素をソートされたリスト内の正しい位置に 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

ログイン後にコピー

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

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

ログイン後にコピー

クイックソート:
クイックソートは効率的な並べ替えアルゴリズムです。これは、分割統治の考え方を使用してリストを 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)

ログイン後にコピー

マージソート:
マージソートは、リストを 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

ログイン後にコピー

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

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 サイトの他の関連記事を参照してください。