冒泡排序是一种通过交换元素位置实现的稳定排序方式,其特点是每一轮排序后,都会在首端或尾端产生一个已排序元素,就像水泡不断上浮一样,通过多次排序,最终所有元素变得有序。
以递增排序为例,初始集合即为待排序集合,已排序集合初始为空
初始状态:0 次排序 待排序集合:[6,3,4,0,2,1,8,5,9,7] 已排序集合:[]
初始状态为:
根据算法过程:
1 次排序后 待排序集合:[3, 4, 0, 2, 1, 6, 5, 8, 7] 已排序集合:[9]
根据算法过程步骤三,待排序集合中不止一个元素,所以重复执行步骤一、二:
2 次排序后 待排序集合:[3, 0, 2, 1, 4, 5, 6, 7] 已排序集合:[8, 9]
... ... ...
9 次排序后 待排序集合:[0] 已排序集合:[1, 2, 3, 4, 5, 6, 7, 8, 9]
观察以上过程可知,每次排序后会有一个元素变为已排序,即有一个元素处于正确的位置上。所以
个元素的序列,经过
次排序后,则有
个元素处于已排序状态,则剩下的一个元素不再需要进行排序。
def bubbleSort(arr):
for i in range(1, len(arr)): # 迭代次数
flag = True
for j in range(len(arr) - i): # 遍历比较每个元素与下一个元素值大小
if arr[j] > arr[j+1]:
arr[j],arr[j+1] = arr[j+1],arr[j]
flag = False
if flag:
break
的集合,最多需要
次迭代即可确定
个元素的位置,即完成排序;
冒泡排序是一种稳定排序算法,排序过程中,如果两个元素值相等,则不交换元素位置。对于
个元素的序列:
次迭代才能结束排序过程, 每一次遍历都比较并交换待排序集合中所有元素位置,即第
次迭代,遍历的元素个数为
,所以最坏情况下,算法的交换复杂度和比较复杂度都为
;
次,交换次数为 0,所以最好情况下,算法的比较复杂度为
,交换复杂度为 0。
算法执行过程中,不需要申请额外的序列空间来保存临时元素,属于原地排序方式,所以算法的空间复杂度为
。