python実装ソートアルゴリズム-バブルソート

pythonを用いてバブルソートアルゴリズムを実現し,バブルソート法は非常に古典的で非常に簡単で効率的なソートアルゴリズムである.まず,バブルソートアルゴリズムを紹介する.
アルゴリズムの手順:
Step 1:最初の数と2番目の数を比較し、最初の数が2番目の数より大きい場合は、2つの数の位置を入れ替えます.Step 2:step 1のやり方で,シーケンス内のすべての隣接する2つの数を順次比較する.このとき,シーケンスの最大数は既に最後尾に「沈」している.Step 3:最後の数を除いてstep 1と2を順番に繰り返し、2番目に大きい数を最後から2番目の位置に「沈」し、比較ソートが終わるまで….
アルゴリズムの例:
シーケンス【3,2,1,5,4】を並べ替える
第1層サイクル:比較4回【3,2】:【2,3,1,5,4】比較【3,1】:【2,1,3,5,4】比較【3,5】:【2,1,3,5,4】比較【5,4】:【2,1,3,4,5】
このとき【5】「沈み」が最後尾まで確認されている
第2層サイクル:比較3回【2,1】:【1,2,3,4,5】比較【2,3】:【1,2,3,4,5】比較【3,4】:【1,2,3,4,5】比較【3,4】:【1,2,3,4,5】
このとき【4】最後から2番目の「沈」が確認されている
第3層サイクル:比較2回比較【1,2】:【1,2,3,4,5】比較【2,3】:【1,2,3,4,5】
このとき【3】最後から3番目に沈むことが確認されています
第4層サイクル:比較1回比較【1,2】:【1,2,3,4,5】
このとき【1,2】位置が確認されています.
以上の例から,サイクルの回数は数値の個数から1つ減少することが分かった.サイクルごとに比較が必要な回数も順次1減少する.
アルゴリズム評価:
発泡ソート法は余分な空間を必要としないことが分かった.従ってその空間的複雑さはO(1)O(1)O(1)O(1)である.しかし,発泡ソート法の効率は比較的低く,外層サイクル(n−1)(n−1)(n−1)(n−1)回,内層サイクル(n−i−1)(n−i−1)(n−i−1)(n−i−1)回が必要であるため,平均時間複雑度はO(n 2)O(n^2)O(n 2)であり,最適時間複雑度はO(n)O(n)O(n)O(n)O(n)O(n)である.そして発泡ソート法は安定である.
方法
へいきんじかんふくざつさ
最悪時間複雑度
さいてきじかんふくざつさ
くうかんふくざつさ
バブルソート
O ( n 2 ) O(n^2) O(n2)
O ( n 2 ) O(n^2) O(n2)
O ( n ) O(n) O(n)
O(1)
python実装:

########################################################
#####                                           #####
########################################################
def maopao(nums,order = 1):
    """
      order 1  ，          ；
      order 0  ，        ；
    """   
    for i in range(len(nums)-1):  #   n  ，      n-1 ，          1
        for j in range(len(nums)-1-i):
            if nums[j] > nums[j+1]:
                nums[j],nums[j+1] = nums[j+1],nums[j]
    if order == 1:
        return nums
    else:
        return nums[::-1]

In [5]：maopao([2,3,4,1,5])
Out[5]: [1, 2, 3, 4, 5]
In [6]: maopao([2,3,4,1,5],1)
Out[6]: [1, 2, 3, 4, 5]
In [7]: maopao([2,3,4,1,5],0)
Out[7]: [5, 4, 3, 2, 1]