冒泡排序

Python 中的数据结构与算法

Miriam Antona

Software engineer

排序算法

  • 深入研究
  • 解决如何将未排序集合按升序/降序进行排序
  • 可降低问题复杂度
  • 常见排序算法：
    • 冒泡排序
    • 选择排序
    • 插入排序
    • 归并排序
    • 快速排序
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第一个元素，另一个指针指向第二个元素。

  • 第一个值大于第二个值
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第一个元素，另一个指针指向第二个元素。第一和第二个元素已被交换。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第二个元素，另一个指针指向第三个元素。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第三个元素，另一个指针指向第四个元素。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第三个元素，另一个指针指向第四个元素。第三和第四个元素已被交换。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第四个元素，另一个指针指向第五个元素。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第四个元素，另一个指针指向第五个元素。第四和第五个元素已被交换。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第四个元素，另一个指针指向第五个元素。第五个元素因已就位而标为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第一个元素，另一个指针指向第二个元素。最后一个元素为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第二个元素，另一个指针指向第三个元素。最后一个元素为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第二个元素，另一个指针指向第三个元素。第二和第三个元素已被交换。最后一个元素为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第三个元素，另一个指针指向第四个元素。最后一个元素为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第三个元素，另一个指针指向第四个元素。最后两个元素为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第一个元素，另一个指针指向第二个元素。最后两个元素为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第一个元素，另一个指针指向第二个元素。第一和第二个元素已被交换。最后两个元素为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第二个元素，另一个指针指向第三个元素。最后两个元素为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第二个元素，另一个指针指向第三个元素。最后三个元素为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第一个元素，另一个指针指向第二个元素。最后三个元素为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第一个元素，另一个指针指向第二个元素。最后四个元素为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序

一个包含未排序数字的列表示意图。一个指针指向第一个元素，另一个指针指向第二个元素。所有元素均为蓝色。

  • 第一个值大于第二个值
    • 交换
  • 第二个值大于第一个值
    • 不变
Python 中的数据结构与算法

冒泡排序——实现

def bubble_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length-1):
    for j in range(list_length-1-i):

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]
Python 中的数据结构与算法

冒泡排序——实现

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list
Python 中的数据结构与算法

冒泡排序——复杂度

  • 最坏情况：$O(n^2)$
  • 最好情况（未改进版）：$\Omega(n^2)$
  • 最好情况（改进版）：$\Omega(n)$
  • 平均情况：$\Theta(n^2)$
  • 对高度无序的大列表表现差
  • 表现较好：
    • 大型已排序/近乎有序列表
    • 小列表
Python 中的数据结构与算法

Passons à la pratique !

Python 中的数据结构与算法

Preparing Video For Download...