选择排序与插入排序

Python 中的数据结构与算法

Miriam Antona

Software engineer

选择排序

一个包含无序数字的列表示意图。有一个指针指向第1个元素。

  • 找到最小值
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。有一个指针指向第1个元素。第1个元素为橙色。

  • 找到最小值
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。有一个指针指向第2个元素。第1个元素为橙色。

  • 找到最小值
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。有一个指针指向第2个元素。第2个元素为橙色。

  • 找到最小值
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。有一个指针指向第3个元素。第2个元素为橙色。

  • 找到最小值
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。有一个指针指向第4个元素。第2个元素为橙色。

  • 找到最小值
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。有一个指针指向第4个元素。第4个元素为橙色。

  • 找到最小值
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。有一个指针指向第5个元素。第4个元素为橙色。

  • 找到最小值
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第4个元素为橙色。有两条箭头表示第1个与第4个元素将被交换。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1个元素为橙色。第1个与第4个元素已交换。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1个元素为蓝色，第2个元素为橙色。有一个指针指向第2个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1个元素为蓝色，第2个元素为橙色。有一个指针指向第3个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1个元素为蓝色，第2个元素为橙色。有一个指针指向第4个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1和第2个元素为蓝色。有一个指针指向第5个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1和第2个元素为蓝色。有一个指针指向第3个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1和第2个元素为蓝色，第3个元素为橙色。有一个指针指向第3个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1和第2个元素为蓝色，第3个元素为橙色。有一个指针指向第4个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1和第2个元素为蓝色，第4个元素为橙色。有一个指针指向第4个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1和第2个元素为蓝色，第4个元素为橙色。有一个指针指向第5个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1和第2个元素为蓝色，第4个元素为橙色。有两条箭头表示第3与第4个元素将被交换。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1、2个元素为蓝色，第3个元素为橙色。第3与第4个元素已交换。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1、2、3个元素为蓝色。有一个指针指向第4个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1、2、3个元素为蓝色，第4个元素为橙色。有一个指针指向第4个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1、2、3个元素为蓝色，第4个元素为橙色。有一个指针指向第5个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1、2、3个元素为蓝色，第5个元素为橙色。有一个指针指向第5个元素。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1、2、3个元素为蓝色，第5个元素为橙色。有两条箭头表示第4与第5个元素将被交换。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1、2、3个元素为蓝色，第4个元素为橙色。第4与第5个元素已交换。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。第1、2、3、4个元素为蓝色。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序

一个包含无序数字的列表示意图。所有元素为蓝色。

  • 找到最小值
  • 将最小值与第一个未排序元素交换
Python 中的数据结构与算法

选择排序 - 实现

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

    lowest = my_list[i]

    index = i

    for j in range(i + 1, list_length):

      if my_list[j] < lowest:

        index = j

        lowest = my_list[j]

    my_list[i] , my_list[index] = my_list[index] , my_list[i]

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

选择排序 - 复杂度

  • 最坏情况：$O(n^2)$
  • 平均情况：$\Theta(n^2)$
  • 最好情况：$\Omega(n^2)$
Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1个元素为蓝色，第2个元素被提升到上方。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1个元素为蓝色，第2个元素被提升到上方。第1个元素已右移。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第2个元素为蓝色。被提升的元素现在位于第1位。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1和第2个元素为蓝色。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1和第2个元素为蓝色。第3个元素被提升到上方。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1、第2和第3个元素为蓝色。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1、第2和第3个元素为蓝色。第3个元素被提升到上方。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1、第2和第3个元素为蓝色。第3个元素被提升到上方。第3个元素已右移。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1、第2和第3个元素为蓝色。第3个元素被提升到上方。第3和第2个元素已右移。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1、第2和第3个元素为蓝色。第3个元素被提升到上方。第3、第2和第3个元素已右移。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1、第2和第3个元素为蓝色。第3个元素被提升到上方。第3、第2和第3个元素已右移。被提升的元素现在位于第1位。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1、第2、第3和第4个元素为蓝色。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1、第2、第3和第4个元素为蓝色。第5个元素被提升到上方。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1、第2、第3和第4个元素为蓝色。第5个元素被提升到上方。第4个元素已右移。

Python 中的数据结构与算法

插入排序

一个包含无序数字的列表示意图。第1、第2、第3和第4个元素为蓝色。第5个元素被提升到上方。被提升的元素现在位于第4位。

Python 中的数据结构与算法

插入排序 - 实现

def insertion_sort(my_list):
  for i in range(1, len(my_list)):

      number_to_order = my_list[i]

      j = i - 1

      while j >= 0 and number_to_order < my_list[j]:

          my_list[j + 1] = my_list[j]

          j -= 1

      my_list[j + 1] = number_to_order

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

插入排序 - 复杂度

  • 最坏情况：$O(n^2)$
  • 平均情况：$\Theta(n^2)$
  • 最好情况：$\Omega(n)$
Python 中的数据结构与算法

Vamos praticar!

Python 中的数据结构与算法

Preparing Video For Download...