Python バブルソート

Document 对象参考手册Python3 サンプルコード

バブルソートは単純な交換ソートアルゴリズムです、その核となる動作原理は：

  1. ソート対象のリストを繰り返し走査し、一度に隣接する2つの要素を比較します；
  2. もし2つの要素の順序が要件を満たさない場合（例えば昇順ソートで前の要素が後ろの要素より大きい場合）、それらの位置を交換します；
  3. 各回の走査では、現在の未ソート部分の最大要素を末尾にバブルアップ（浮上）させます（昇順の場合）、気泡が上昇するように浮かび上がります；
  4. 上記のプロセスを、リスト全体が完全に整列するまで（交換操作が発生しないか、すべての要素を走査し終わるまで）繰り返します。

重要な特性

  • ソート種別：交換ソート
  • 時間計算量：最悪/O(n²)（リストが完全に逆順）、平均/O(n²)、最良/O(n)（最適化版、リストがすでに整列済み）
  • 空間計算量：O(1)（インプレースソート、追加の補助スペース不要）
  • 安定性：安定ソート（等しい要素の相対位置は変わらない）

サンプルコード

def bubbleSort(arr): n = len(arr) # すべての配列要素を走査します for i in range(n): # 最後の i 個の要素は正しい位置にあるため（再比較の必要なし） for j in range(0, n-i-1): if arr[j] > arr[j+1] : arr[j], arr[j+1] = arr[j+1], arr[j] arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print ("ソート後の配列：") for i in range(len(arr)): print ("%d" %arr[i]),

上記コードを実行すると出力結果は：

排序后的数组:
11
12
22
25
34
64
90

Document 对象参考手册Python3 サンプルコード

その他の拡張