排序算法(一):冒泡排序

排序算法(一):冒泡排序

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

算法过程

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

  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]

排序算法(一):冒泡排序

观察以上过程可知,每次排序后会有一个元素变为已排序,即有一个元素处于正确的位置上。所以 排序算法(一):冒泡排序 个元素的序列,经过 排序算法(一):冒泡排序 次排序后,则有 排序算法(一):冒泡排序 个元素处于已排序状态,则剩下的一个元素不再需要进行排序。

算法示例

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
代码分析 :
  • 以上代码中,第一层循环为需要进行的迭代次数,元素个数为 排序算法(一):冒泡排序 的集合,最多需要 排序算法(一):冒泡排序 次迭代即可确定 排序算法(一):冒泡排序 个元素的位置,即完成排序;
  • 第二层循环为待排序集合中元素的遍历比较大小操作,随着迭代次数的增加,待排序元素个数减少;
  • 代码中增加了一个 flag 标志变量,用于标志排序结束状态。若某一轮迭代中,待排序集合中元素遍历过程中,没有发生元素位置交换操作,则该待排序集合为有序的,排序算法结束。

算法分析

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

  • 最坏情况下,当序列为逆序时,需要 排序算法(一):冒泡排序 次迭代才能结束排序过程, 每一次遍历都比较并交换待排序集合中所有元素位置,即第 排序算法(一):冒泡排序 次迭代,遍历的元素个数为 排序算法(一):冒泡排序,所以最坏情况下,算法的交换复杂度和比较复杂度都为 排序算法(一):冒泡排序 ;
  • 最好情况下,当序列为已排序时,第一次迭代即可结束排序过程,第一次遍历元素个数为 排序算法(一):冒泡排序 次,交换次数为 0,所以最好情况下,算法的比较复杂度为 排序算法(一):冒泡排序 ,交换复杂度为 0。

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

github 链接:冒泡排序

上一篇:redis的使用和安装,redis基础和高级部分


下一篇:实战开发经验: 软件中的错误收集策略