Python データ構造とアルゴリズムにおける一般的な割り当てソート方法の例 [バケット ソートと基数ソート]_python

この記事では、主に Python のデータ構造とアルゴリズムの一般的な割り当てとソートの方法を紹介し、バケット ソートと基数ソートの関連する原理と実装テクニックを例の形式で分析します。この記事の例では、Python データ構造とアルゴリズムの一般的な割り当ておよび並べ替え方法について説明します。参考のために皆さんと共有してください。詳細は次のとおりです。

ボックスの並べ替え (バケットの並べ替え)

ボックスの並べ替えは、キーワード値の範囲 1~m に基づいており、m 個のボックスが事前に設定されています。ソートにはキーワード タイプが必要です。これは限定されたタイプであり、無限のボックスを持つ可能性がありますが、実用的な価値はほとんどなく、通常は基数ソートの中間プロセスで使用されます。

バケット ソートはボックス ソートの実用的な変形で、[0,1) などのデータ セットの範囲を同じサイズの n 個のサブ間隔に分割し、各サブ間隔をバケットとして割り当てます。 n 個の非レコードを各バケットに入れます。キーワード シーケンスは [0,1) に均等に分散されているため、通常、同じバケットに分類されるレコードはそれほど多くありません。

次のバケットソートメソッドは辞書を使用して実装されているため、整数型の場合は余分なスペースを作成する必要はありません

def BuckSort(A):
 bucks = dict()  # 桶
 for i in A:
  bucks.setdefault(i,[]) # 每个桶默认为空列表
  bucks[i].append(i)  # 往对应的桶中添加元素
 A_sort = []
 for i in range(min(A), max(A)+1):
  if i in bucks:     # 检查是否存在对应数字的桶
   A_sort.extend(bucks[i])  # 合并桶中数据
 return A_sort

基数ソート

# 基数排序
# 输入：待排序数组s, keysize关键字位数, 亦即装箱次数, radix基数
def RadixSort(s, keysize=4, radix=10):
 # 按关键字的第k分量进行分配 k = 4,3,2,1
 def distribute(s,k):
  box = {r:[] for r in range(radix)}  # 分配用的空箱子
  for item in s:   # 依次扫描s[]，将其装箱
   t = item
   t /= 10**(k-1)
   t %= 10    # 去关键字第k位
   box[t].append(item)
  return box
 # 按分配结果重新排列数据
 def collect(s,box):
  a = 0
  for i in range(radix):
   s[a:a + len(box[i])] = box[i][:] # 将箱子中元素的合并，覆盖到原来的数组中
   a += len(box[i])     # 增加偏移值
 # 核心算法
 for k in range(1,keysize+1):
  box = distribute(s,k)   # 按基数分配
  collect(s,box)     # 按分配结果拼合

以下は「データ構造とアルゴリズム - 理論と実践」より抜粋

基本的なソートは、ポーカー カードをスートと番号でソートするなど、複数のキーワードによるソートに拡張できます。
一般に、線形テーブルにソート対象の要素があり、各要素に d 個のキーワード {k1, k2,...,kd} が含まれていると仮定すると、線形テーブルには、線形内の任意の 2 つのキーに対して、キーワードへの順序付けされた参照が含まれます。 table 要素 r[i] と r[j]、1 {k1i,k2i,...,kdi} < ..,kdj}
ここで、k1 は最上位桁キーワード、kd は最下位桁キーワードと呼ばれます
ソート方法には 2 つあります: 最上位桁が最初の MSD (最上位桁ファースト) と最下位桁が最初の LSD (最下位)有効数字が最初)

MSD: まずグループを k1 で並べ替えます。キーワード k1 が同じグループ内の要素と等しい場合、各グループを k2 で並べ替えてサブグループに分割し、最後の桁 kd まで同様に続けます。各サブグループを並べ替えてから、グループをリンクします。

LSD: MSD とは逆に、最初に kd、次に kd-1 などで並べ替えます。

追記: 参考として推奨される並べ替えに関する別のデモ ツール:

挿入/選択/バブル/マージ/ヒル/クイック ソート アルゴリズム プロセス ツールのオンライン アニメーション デモ:
http: //tools.jb51.net/aideddesign/paixu_ys

この記事の内容は以上です。皆さんのお役に立てれば幸いです。 ！

関連する推奨事項:

文字列一致アルゴリズムのサンプルコードのPython実装

Pythonクローラーエントリーの経験の共有

Pythonでのロギングライブラリの使用の概要

以上がPython データ構造とアルゴリズムにおける一般的な割り当てソート方法の例 [バケット ソートと基数ソート]_pythonの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。