排序算法之——选择，插入，冒泡详解(动态图+python)

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

排序动画过程解释

1.线性搜索数列并找到最小值，此时找到了为 2
2.将最小值替换为数列中左端的数字，即将 2 与 4 进行交换
3.此时 2 已经排序好
4.继续线性搜索剩余数列找到最小值，此时找到了 3
5.将最小值替换为数列中左端的数字，即将 3 与 4 进行交换
6.此时 2 与 3 已经排序好
7.继续线性搜索剩余数列找到最小值，此时找到了 4
8.如果最小值已经在左端，那么不执行任何操作，所以此时不做任何处理
9.此时 2 、 3 、 4 已经排序好
10.重复相同操作，直到所有数字都被排序

代码：

算法的内存消耗可以用空间复杂度来衡量，但是排序算法中引入一个新的概念：原地排序。原地排序算法就是指空间复杂度是O(1)的排序算法。
还有一个稳定性的概念，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

选择排序是一种原地排序算法，但不是一个稳定的算法，从动态图中可以看出来，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

比如5，8，5，2，9这样一组数据，使用选择排序算法来排序，第一次找到最小元素2，与第一个5交换位置，那第一个5和中间的5顺序就变了，所以就不稳定了。

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）。

排序动画过程解释

1.一开始左端数字已经排序，数字 5 不动
2.然后，取出剩余未操作的左端数字 3
3.将其与已经操作的左侧数字相比较
4.如果左边的数字较大，则交换两个数字
5.这种情况下，由于 5 大于 3 ，所以交换两个数字
6.重复此操作，直到出现一个较小的数字到达左端
7.数字 3 已经完成排序
8.接下来，和之前一样取出剩余未操作的左端数字 4
9.与其相邻的左边数字进行比较
10.这种情况下，由于 5 大于 4 ，所以交换两个数字
11.继续操作，由于 3 小于 4 ，即出现了更小的数字，所以 4 停止移动
12.数字 4 已经完成排序
13.重复相同的操作，直到所有的数字完成排序

总之就是将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间就只有一个元素，就是数组的第一个元素，核心思想就是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入并保证已排序区间数据一直有序。

插入排序的运行并不需要额外的存储空间，所以时间复杂度是O(1)，是一个原地排序算法。

在插入排序中，对于值相等的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；

• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

算法步骤

1.选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
2.按增量序列个数 k，对序列进行 k 趟排序；
3.每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

排序动画过程解释

1.首先，选择增量 gap = 10/2 ，缩小增量继续以 gap = gap/2 的方式
2.初始增量为 gap = 10/2 = 5，整个数组分成了 5 组
3.按颜色划分为【 8 , 3 】，【 9 , 5 】，【 1 , 4 】，【 7 , 6 】，【 2 , 0 】
4.对这分开的 5 组分别使用上节所讲的插入排序
5.结果可以发现，这五组中的相对小元素都被调到前面了
6.缩小增量 gap = 5/2 = 2，整个数组分成了 2 组
7.【 3 , 1 , 0 , 9 , 7 】，【 5 , 6 , 8 , 4 , 2 】
8.对这分开的 2 组分别使用上节所讲的插入排序
9.此时整个数组的有序性是很明显的
10.再缩小增量 gap = 2/2 = 1，整个数组分成了 1 组
11.【 0, 2 , 1 , 4 , 3 , 5 , 7 , 6 , 9 , 0 】
此时，只需要对以上数列进行简单的微调，不需要大量的移动操作即可完成整个数组的排序

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法步骤
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

排序动画过程解释

1.将天平放在序列的右端，并比较天平左右的数字
2.在这种情况下我们比较 3 和 8
3.比较后如果右边的数字较小，则被交换
4.因为 8 大于 3 ，所以数字不用交换
5.比较完成后，将天平向左移动一个位置，比较数字
6.因为 3 大于 2 ，所以数字不用交换
7.比较完成后，逐一移动天平，比较数字
8.此时 2 小于 4 ，所以左右的数字互相交换
9.重复同样的操作，直到天平移动到左端
。。。。。。
10.天平到达左端
11.经过上述的操作，数列中最小的数字已经移动到左端
12.将天平返回右端
13.重复相同的操作，直到所有数字都被排序
14.排序完成

冒泡排序也是原地排序O(1)，只有交换才可以改变两个元素的前后顺序。保证冒泡的稳定性，相等的数我们就不做交换。

插入排序和冒泡排序时间复杂度都是O(n^2)，冒泡排序不管怎么优化，元素交换的次数是一个固定值，是原始数据的逆序数。插入排序是同样的，不管怎么优化，元素移动的次数也等于原始数据的逆序数。

但是bubble的数据交换要比插入排序的数据移动要复杂，冒泡排序需要三个赋值操作。而插入排序只需要1个。

这里的时间复杂度是O(n^2)，对于小数据量是够了，但是我们一般是用快排，归并等等。

我们接着再谈一个思考：我们都是用的数组实现的排序，如果数据存储在链表中，这三种排序算法还能工作吗？

答：应该有个前提，是否允许修改链表的结点value值，还是只能改变结点的位置。一般而言，考虑只能改变结点位置，冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂；插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表；选择排序比较次数一致，交换操作同样比较麻烦。