排序算法（一）：冒泡排序

冒泡排序是一种通过交换元素位置实现的稳定排序方式，其特点是每一轮排序后，都会在首端或尾端产生一个已排序元素，就像水泡不断上浮一样，通过多次排序，最终所有元素变得有序。

算法过程

以递增排序为例，初始集合即为待排序集合，已排序集合初始为空

1. 从待排序集合中第一个元素开始向后遍历集合中元素，比较与下一个元素值的大小，大于下一个元素值则交换两个元素位置，直到待排序集合最后一个元素；
2. 标记待排序集合最后一个元素为已排序；
3. 重复步骤 1,2，直到待排序集合只有一个元素

演示示例

初始状态：0 次排序 待排序集合：[6,3,4,0,2,1,8,5,9,7] 已排序集合：[]

初始状态为：

根据算法过程：

• 步骤一，从待排序集合中第一个元素开始，比较 6 和 3，比较大小并交换位置后，选择第二个元素，比较 6 和 4，比较大小并交换位置，依次遍历直到待排序集合最后一个元素；
• 步骤二，标记待排序集合中的最后一个元素为已排序，即元素 9 标记为已排序，从待排序集合中移除该元素

1 次排序后 待排序集合：[3, 4, 0, 2, 1, 6, 5, 8, 7] 已排序集合：[9]

根据算法过程步骤三，待排序集合中不止一个元素，所以重复执行步骤一、二：

• 步骤一，遍历待排序集合，选择第一个元素，比较 3,4，比较大小后，选择第二个元素，比较 4,0，比较大小并交换位置，选择第三个元素，比较4,2，依次遍历直到集合最后一个元素；
• 步骤二，标记最后一个元素为已排序

2 次排序后 待排序集合：[3, 0, 2, 1, 4, 5, 6, 7] 已排序集合：[8, 9]

... ... ...

9 次排序后 待排序集合：[0] 已排序集合：[1, 2, 3, 4, 5, 6, 7, 8, 9]

观察以上过程可知，每次排序后会有一个元素变为已排序，即有一个元素处于正确的位置上。所以

N

个元素的序列，经过

N-1

次排序后，则有

N-1

个元素处于已排序状态，则剩下的一个元素不再需要进行排序。

算法示例

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

代码分析 ：

• 以上代码中，第一层循环为需要进行的迭代次数，元素个数为

N

的集合，最多需要

N-1

次迭代即可确定

N-1

个元素的位置，即完成排序；

• 第二层循环为待排序集合中元素的遍历比较大小操作，随着迭代次数的增加，待排序元素个数减少；
• 代码中增加了一个 flag 标志变量，用于标志排序结束状态。若某一轮迭代中，待排序集合中元素遍历过程中，没有发生元素位置交换操作，则该待排序集合为有序的，排序算法结束。

算法分析

冒泡排序是一种稳定排序算法，排序过程中，如果两个元素值相等，则不交换元素位置。对于

N

个元素的序列：

• 最坏情况下，当序列为逆序时，需要

N-1

次迭代才能结束排序过程， 每一次遍历都比较并交换待排序集合中所有元素位置，即第

i

次迭代，遍历的元素个数为

N-i

，所以最坏情况下，算法的交换复杂度和比较复杂度都为

O(n^2)

;

• 最好情况下，当序列为已排序时，第一次迭代即可结束排序过程，第一次遍历元素个数为

N

次，交换次数为 0，所以最好情况下，算法的比较复杂度为

O(n)

，交换复杂度为 0。

算法执行过程中，不需要申请额外的序列空间来保存临时元素，属于原地排序方式，所以算法的空间复杂度为

O(1)

。