Python 冒泡排序

冒泡排序算法是一种基于比较的算法，其中比较每对相邻元素，如果元素顺序不正确，则交换元素。冒泡排序的平均和最坏情况复杂度为 O(n2)，其中 n 是项目数。

Python bubble sort examples

  • Example 1 - basic
# ascending order:
In [1]: x = [7,2,8,9,4,3,5,6,1]

In [2]: print x
[7, 2, 8, 9, 4, 3, 5, 6, 1]

In [3]: for i in range(len(x)):
   ...:     for j in range(len(x)-1-i):
   ...:         if x[j] > x[j+1]:
   ...:             x[j], x[j+1] = x[j+1], x[j]
   ...:             

In [4]: print x
[1, 2, 3, 4, 5, 6, 7, 8, 9]

# descending order:
In [5]: x = [7,2,8,9,4,3,5,6,1]

In [6]: print x
[7, 2, 8, 9, 4, 3, 5, 6, 1]

In [7]: for i in range(len(x)):
   ...:     for j in range(len(x)-1-i):
   ...:         if x[j] < x[j+1]:
   ...:             x[j], x[j+1] = x[j+1], x[j]
   ...:             

In [8]: print x
[9, 8, 7, 6, 5, 4, 3, 2, 1]
  • Example 2 - improved
In [1]: x = [6,1,2,3,4,5]

In [2]: for i in range(len(x)):
   ...:     sorted = True
   ...:     for j in range(len(x)-1-i):
   ...:         if x[j] > x[j+1]:
   ...:             x[j], x[j+1] = x[j+1], x[j]
   ...:             sorted = False
   ...:     if sorted:
   ...:         break
   ...:     

In [3]: print x
[1, 2, 3, 4, 5, 6]

参考资料

python algorithm

🇨🇳 🇯🇵 📍 ⌚