扶贫基金会网站建设是哪家公司,cn域名做外贸网站,电商模板哪个网站好,重庆华鼎达网站建设冒泡排序在排序算法中是最简单的一种#xff0c;它通过多次遍历列表#xff0c;将最大的元素冒泡到列表的头部或尾部。我们通过对四张扑克牌#xff08;花色相同#xff09;以从小到大的方式进行排序来演示该算法的工作原理。首先将扑克牌面朝上放在桌上#xff0c;如下图…冒泡排序在排序算法中是最简单的一种它通过多次遍历列表将最大的元素冒泡到列表的头部或尾部。我们通过对四张扑克牌花色相同以从小到大的方式进行排序来演示该算法的工作原理。首先将扑克牌面朝上放在桌上如下图所示该算法要求多次遍历扑克每次都从头开始并在上一次遍历的前一张结束。在每一次遍历中总是从前两张牌开始。如果前者比后者大则交换位置。然后比较第二张和第三张同样如果前者更大则互换否则保持原样。这样依次类推直到将最大的那一张牌移动到最后。
下图演示了接下来的两次遍历。第二次遍历将会使第二大的牌交换至倒数第二的位置上第三次只需比较头两张然后整个流程结束。下面是Python版的冒泡排序
# Sorts a sequence in ascending order using the bubble sort algorithm.
def bubbleSort( theSeq ):
n len( theSeq )
# Perform n-1 bubble operations on the sequence
for i in range( n - 1 ) :
# Bubble the largest item to the end.
for j in range( i n - 1 ) :
if theSeq[j] theSeq[j 1] : # swap the j and j1 items.
tmp theSeq[j]
theSeq[j] theSeq[j 1]
theSeq[j 1] tmp
冒泡排序的效率仅仅取决于列表中元素的个数与元素的值和初始序列无关。为了确认其效率我们必须知道一个含有N个元素的列表在排序时内层循环总的执行次数。外层一共会循环n - 1次因为需要遍历n - 1次列表。而内层循环不定第一次列表遍历执行n - 1次第二次n - 2次第三次则是n - 3次直到最后一次遍历内层只需执行1次即可。这样内部循环总的遍历次数是前n - 1个整数的总和即等同于得到其时间复杂度为On2。正因如此冒泡排序是排序算法中效率最低的一种。如果给定一个倒序的列表那每次迭代的内层循环中都会做交换操作这在实际操作中无疑是非常耗性能的。
在前面的代码中其内层循环总是n2但如果给定序列已经是排好序的呢该情况下排序实际是不需要的但代码并不知情它依然如此辛勤劳作以至于其性能依旧是n2。
更多请参考Rance D. Necaise - 《Data Structures and Algorithms Using Python》
