Python で 8 つの並べ替えアルゴリズムを実装する方法

この記事では主に 8 つの並べ替えアルゴリズムの Python 実装を紹介し、8 つの並べ替えアルゴリズムの詳細な説明とコード実装を提供します。興味のある方は、

8 つの並べ替えアルゴリズムの Python 実装を参照してください。具体的な内容は次のとおりです。

1. 挿入ソート説明

挿入ソートの基本的な動作は、ソート済みの順序付きデータにデータを挿入し、その数値に 1 を加えた新しい順序付きデータを取得することです。このアルゴリズムは、少量のソートに適しています。のデータの場合、時間計算量は O(n^2) です。安定した選別方法です。挿入アルゴリズムは、ソートされる配列を 2 つの部分に分割します。最初の部分には、最後の要素を除く配列のすべての要素が含まれます (配列に挿入位置を追加するためのスペースが 1 つ増えます)。2 番目の部分には、この要素のみが含まれます。 1 つの要素 (つまり、挿入される要素)。最初の部分がソートされた後、この最後の要素がソートされた最初の部分に挿入されます。

コードの実装

def insert_sort(lists):
  # 插入排序
  count = len(lists)
  for i in range(1, count):
    key = lists[i]
    j = i - 1
    while j >= 0:
      if lists[j] > key:
        lists[j + 1] = lists[j]
        lists[j] = key
      j -= 1
  return lists

2. ヒルソート
説明

ヒルソート（シェルソート）は挿入ソートの一種です。これは削減増分ソートとも呼ばれ、直接挿入ソート アルゴリズムのより効率的かつ改良されたバージョンです。ヒル ソートは、不安定なソート アルゴリズムです。この方法はDLによるものです。シェルは 1959 年に提案されたことにちなんで名付けられました。 ヒル ソートでは、添字の特定の増分でレコードをグループ化し、直接挿入ソート アルゴリズムを使用して各グループをソートします。増分が徐々に減少するにつれて、各グループにはさらに多くのキーワードが含まれます。増分が 1 まで減少すると、ファイル全体がグループ化されます。ちょうど 1 つのグループに分割され、アルゴリズムは終了します。

コードの実装

def shell_sort(lists):
  # 希尔排序
  count = len(lists)
  step = 2
  group = count / step
  while group > 0:
    for i in range(0, group):
      j = i + group
      while j < count:
        k = j - group
        key = lists[j]
        while k >= 0:
          if lists[k] > key:
            lists[k + group] = lists[k]
            lists[k] = key
          k -= group
        j += group
    group /= step
  return lists

3. バブルソート
説明

ソート対象のシーケンスを繰り返し訪問し、一度に 2 つの要素を比較し、順序が間違っている場合はそれらを入れ替えます。配列を訪問する作業は、それ以上の交換が必要なくなるまで繰り返されます。これは、配列がソートされたことを意味します。

コードの実装

4. クイックソート

説明

1 回の並べ替えパスを通じて、並べ替えられるデータを 2 つの独立した部分に分割します。他の部分は小さく、このメソッドを使用してデータの 2 つの部分をそれぞれすばやく並べ替えることができ、並べ替えプロセス全体を再帰的に実行できるため、データ全体が順序付けされたシーケンスになります。
コード実装

def bubble_sort(lists):
  # 冒泡排序
  count = len(lists)
  for i in range(0, count):
    for j in range(i + 1, count):
      if lists[i] > lists[j]:
        lists[i], lists[j] = lists[j], lists[i]
  return lists

5. 直接選択ソート

説明

基本的な考え方: 最初のパスでは、ソート対象のレコード r1 ~ r[n] の中から最小のレコードを選択し、それを結合します。 r1 Exchange; 2 番目のパスでは、ソート対象のレコード r2 ~ r[n] の中から最小のレコードを選択し、それを r2 と交換します。以降、ソート対象のレコードの i 番目のパス r[i] となります。 ] ~ r[n] 最小のレコードを選択し、それを r[i] と交換します。これにより、順序付けられたシーケンスは、すべてがソートされるまで増加し続けます。
コード実装

def quick_sort(lists, left, right):
  # 快速排序
  if left >= right:
    return lists
  key = lists[left]
  low = left
  high = right
  while left < right:
    while left < right and lists[right] >= key:
      right -= 1
    lists[left] = lists[right]
    while left < right and lists[left] <= key:
      left += 1
    lists[right] = lists[left]
  lists[right] = key
  quick_sort(lists, low, left - 1)
  quick_sort(lists, left + 1, high)
  return lists

6. ヒープソート

説明

ヒープソートは、積み重ねられたツリー (ヒープ) のデータ構造を使用して設計されたソート アルゴリズムを指します。配列の特性を利用して、指定したインデックスにある要素をすばやく見つけることができます。ヒープは、大きなルート ヒープと小さなルート ヒープに分割され、完全なバイナリ ツリーになります。大規模なルート ヒープの要件は、各ノードの値がその親ノードの値以下であること、つまり A[PARENT[i]] >= A[i] であることです。配列の非降順ソートでは、大きなルート ヒープの要件に従って、最大値がヒープの先頭になければならないため、大きなルート ヒープを使用する必要があります。
コードの実装

def select_sort(lists):
  # 选择排序
  count = len(lists)
  for i in range(0, count):
    min = i
    for j in range(i + 1, count):
      if lists[min] > lists[j]:
        min = j
    lists[min], lists[i] = lists[i], lists[min]
  return lists

7. マージソート

説明

マージソートは、分割統治法 (pide と Conquer) を使用する非常に典型的なアプリケーションです。すでに順序付けされているサブシーケンスをマージして、完全に順序付けされたシーケンスを取得します。つまり、まず各サブシーケンスを順序どおりにしてから、サブシーケンス セグメントを順序どおりにします。 2 つの順序付きリストが 1 つの順序付きリストにマージされる場合、それは双方向マージと呼ばれます。
マージプロセスは次のとおりです: a[i] と a[j] のサイズを比較し、a[i]≤a[j] の場合、最初の順序付きリストの要素 a[i] を r[k ] にコピーします。それ以外の場合は、2 番目の順序付けされたリストの要素 a[j] を r[k] にコピーし、j と k にそれぞれ 1 を追加するというように、順序付きリストの 1 つがフェッチされるまで続きます。 、次に、もう一方の順序付きリストの残りの要素を、r の下付き文字 k から下付き文字 t までのセルにコピーします。通常、再帰を使用してマージ ソート アルゴリズムを実装します。まず、ソート対象の区間 [s, t] を中間点で 2 つに分割し、次に左側のサブ範囲をソートし、次に右側のサブ範囲をソートし、最後に を使用します。左側の間隔と右側の間隔の間のマージ操作。順序付けされた間隔 [s,t] にマージします。

コード実装

# 调整堆
def adjust_heap(lists, i, size):
  lchild = 2 * i + 1
  rchild = 2 * i + 2
  max = i
  if i < size / 2:
    if lchild < size and lists[lchild] > lists[max]:
      max = lchild
    if rchild < size and lists[rchild] > lists[max]:
      max = rchild
    if max != i:
      lists[max], lists[i] = lists[i], lists[max]
      adjust_heap(lists, max, size)

# 创建堆
def build_heap(lists, size):
  for i in range(0, (size/2))[::-1]:
    adjust_heap(lists, i, size)

# 堆排序
def heap_sort(lists):
  size = len(lists)
  build_heap(lists, size)
  for i in range(0, size)[::-1]:
    lists[0], lists[i] = lists[i], lists[0]
    adjust_heap(lists, 0, i)

8. 基数ソート

説明

基数ソート（基数ソート）は、「バケットソート」またはビンソートとも呼ばれる「分散ソート」（分散ソート）に属します。名前が示すように、ソート効果を達成するためにキー値情報の一部を通じてソート対象の要素を特定の「バケット」に割り当てます。基数ソート方法は安定したソートであり、その時間計算量は O (nlog(r)m) です。ここで、r は取得されるベース、m はヒープの数です。場合によっては、基数ソート方法が他の安定性ソート方法よりも効率的です。
コードの実装

import math
def radix_sort(lists, radix=10):
  k = int(math.ceil(math.log(max(lists), radix)))
  bucket = [[] for i in range(radix)]
  for i in range(1, k+1):
    for j in lists:
      bucket[j/(radix**(i-1)) % (radix**i)].append(j)
    del lists[:]
    for z in bucket:
      lists += z
      del z[:]
  return lists

以上就是Python实现八大排序算法的详细介绍，希望对大家的学习有所帮助。

以上がPython で 8 つの並べ替えアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。