7599 - [选修1]Python五大排序算法 - 动态讲解

admin

冒泡排序
冒泡排序通常是在CS入门课程中教的，因为它清楚地演示了排序是如何工作的，同时又简单易懂。冒泡排序步骤遍历列表并比较相邻的元素对。如果元素顺序错误，则交换它们。重复遍历列表未排序部分的元素，直到完成列表排序。因为冒泡排序重复地通过列表的未排序部分，所以它具有最坏的情况复杂度O(n^2)。
7 F0 W6 q7 I2 c% X& v  w
选择排序
% S! s9 H) ]  C2 q, k7 h选择排序也很简单，但常常优于冒泡排序。如果您在这两者之间进行选择，最好默认选择排序。通过选择排序，我们将输入列表/数组分为两部分：已经排序的子列表和剩余要排序的子列表，它们构成了列表的其余部分。我们首先在未排序的子列表中找到最小的元素，并将其放置在排序的子列表的末尾。因此，我们不断地获取最小的未排序元素，并将其按排序顺序放置在排序的子列表中。此过程将重复进行，直到列表完全排序。

& u; m: }1 \  l- w. f' ]插入排序
插入排序比冒泡排序和选择排序既快又简单。有趣的是，有多少人在玩纸牌游戏时会整理自己的牌！在每个循环迭代中，插入排序从数组中删除一个元素。然后，它在另一个排序数组中找到该元素所属的位置，并将其插入其中。它重复这个过程，直到没有输入元素。

归并排序
/ X; n, q0 g: J+ r* x归并排序是分而治之算法的完美例子。它简单地使用了这种算法的两个主要步骤：
1 q8 y# ^5 d+ m. H. i( p. z6 w0 Y（1）连续划分未排序列表，直到有N个子列表，其中每个子列表有1个“未排序”元素，N是原始数组中的元素数。
  m/ k' e$ C! }+ y# u（2）重复合并，即一次将两个子列表合并在一起，生成新的排序子列表，直到所有元素完全合并到一个排序数组中。

% G+ F2 d% }- r( q! o4 M快速排序
快速排序也是一种分而治之的算法，如归并排序。虽然它有点复杂，但在大多数标准实现中，它的执行速度明显快于归并排序，并且很少达到最坏情况下的复杂度O(n) 。它有三个主要步骤：
（1）我们首先选择一个元素，称为数组的基准元素(pivot)。
9 V6 |+ U1 S' k% r（2）将所有小于基准元素的元素移到基准元素左侧；将所有大于基准元素的元素移到基准元素右侧。这称为分区操作。
: i/ h7 h9 p4 I" A% h（3）递归地将上述两个步骤分别应用于比上一个基准元素值更小和更大的元素的每个子数组。