王争数据结构与算法学习笔记-冒泡、插入、选择排序

插入排序和冒泡排序的时间复杂度相同，都是$O(n^2)$​，在实际的软件开发里，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢？

冒泡排序和插入排序不论如何优化，元素的交换次数是一个固定的值，即原始数据的逆序度。但是从代码的实现角度来看，冒泡排序的数据交换要比插入排序的数据移动复杂，冒泡排序需要3个赋值操作，而插入排序只要1个。比如如下的代码：

// 冒泡排序中的数据交换操作
if (a[i] > a[i+1]) {
    int tmp = a[i];
    a[i] = a[i + 1];
    a[i + 1] = tmp;
    flag = true;
}

// 插入排序中的数据移动操作
if (a[i] > value) {
    a[i+1] = a[i];
}
else {
    break;
}

假设执行一个赋值语句的时间粗略记为1个单位时间，然后使用冒泡和插入对同一个逆序度为k的数组进行排序。用冒泡排序，需要k次交换操作，每次需要3次赋值语句，所以交换操作总耗时为3k单位时间，而插入排序中数据移动操作只需要k个单位时间。

虽然冒泡排序和插入排序在时间复杂度上是一样的，都是 $O(n^2)$​，但是如果我们希望把性能优化做到极致，那肯定首选插入排序。

	是原地排序？	是否稳定？	最好 最坏 平均
冒泡排序	是	是	$O(n)$​ $O(n^2)$​ $O(n^2)$​
插入排序	是	是	$O(n)$​ $O(n^2)$​ $O(n^2)$​
选择排序	是	否	$O(n^2)$​ $O(n^2)$​ $O(n^2)$​

三种时间复杂度均为$O(n^2)$的排序算法中，冒泡、选择排序可能就纯粹停留在理论层面，学习的目的也是为了开拓思维，实际开发用的不多，但是插入排序还是很有用的。

如果将上述的三个算法使用链表来实现，需要确定一个前提：在交换数据的时候，是交换结点的位置还是交换两个结点的value值？如果是交换结点的值，那么对于冒泡排序、选择排序的时间复杂度和空间复杂度没有明显变化，而插入排序不涉及交换元素，插入元素的时候由于链表的特性，时间复杂度为$O(n)$​​，但是排序完毕之后需要倒置链表；如果是交换结点的位置，对于冒泡排序和选择排序，交换元素操作相比于数组更加复杂，而插入排序的分析和交换结点的值的情况下的分析类似。

如何分析一个“排序算法”？

排序算法的执行效率

1. 最好情况、最坏情况、平均情况时间复杂度

   有序度不同的数据，对于排序的执行时间有影响，我们要知道排序算法在不同数据下的性能表现。

2. 时间复杂度的系数、常数、低阶

   在实际的软件开发中，我们的排序可能是10个、100个、1000个这样规模很小的数据，所以在同一阶时间复杂度的排序算法性能对比的时候，就要将系数、常数、低阶也考虑进来。

3. 比较次数和交换（或移动）次数

   基于比较的排序算法的执行过程，会涉及两种操作，一种是元素的比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

排序算法的稳定性

很多数据结构示例中，我们排序都用的是整数来举例，但是在真正的软件开发中，我们要排序的往往不是单纯的整数，而是一组对象，我们需要按照对象的某个属性来排序。

比如说，我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。这样一个排序需求，我们可以使用稳定排序算法，首先按照下单时间对订单排序，然后使用稳定排序算法，按照订单金额重新排序。

冒泡排序

如何分析冒泡排序的平均时间复杂度？

对于包含n个数据的数组，这n个数据有n!中排列方式，同的排列方式，冒泡排序执行的时间不同，如果用概率论方法定量分析平均时间复杂度，涉及的数学推理和计算就会很复杂。可以通过“有序度”和“逆序度”这两个概念来进行分析。

有序度是数组中具有有序关系的元素对的个数。如：2，4，3，1，5，6这组数据的有序度为11，因为其有序元素对的个数为11个，分别是：

(2,4) (2,3) (2,5) (2,6) (4,5) (4,6) (3,5) (3,6) (1,5) (1,6) (5,6)

同理，对于一个倒序排列的数组，比如 6，5，4，3，2，1，有序度是 0；对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 $n * (n-1)/2$，也就是 15。我们把这种完全有序的数组的有序度叫作满有序度。逆序度=满有序度-有序度。

冒泡排序包含两个操作原子，比较和交换。每交换依次，有序度就加1，不管算法怎么改，交换次数总是确定的，即逆序度，也就是n*(n-1) / 2-初始有序度。

对于包含n个数据的数组进行冒泡排序，最坏的情况下，初始状态有序度是0，所以要进行$n * (n-1)/2$，最好的情况下，初始状态的有序度为$n * (n-1)/2$，就不需要进行交换，我们可以取中间值$n * (n-1)/2$，来表示初始有许多有既不是很高也不是很低的平均情况。

换句话说，平均情况下，需要 n*(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 $O(n^2)$​​，所以平均情况下的时间复杂度就是$O(n^2)$​​。

插入排序

插入排序的移动操作次数总是固定的，等于逆序度，比如初始序列为：4、5、6、1、3、2。数据移动的个数总和为10=3+3+4.

插入排序最好的情况下的时间复杂度为$O(n)$，最坏的情况下时间复杂度为$O(n^2)$。

选择排序

选择排序每一趟都会从无序序列中寻找最小或者最大值然后插入有序序列中，其最好、最坏的时间复杂度都是$O(n^2)$，选择排序不是稳定的算法，比如5,8,5,2,9，使用选择排序的话，最终第一个5就会替换到2的位置。