数据结构与算法第七讲 - 排序（上）
对于排序算法，主要掌握内容如下：
- 排序算法的实现原理
- 手写出实现代码
- 评价及分析算法
本讲内容
如何分析一个排序算法
冒泡排序
插入排序
选择排序
思考题：插入排序和冒泡排序的时间复杂度相同，都是 O(n2)，在实际的软件开发里，为什么我们更倾向于使用插入排序算法而不是冒泡排序算法呢？
如何分析一个排序算法？
排序算法的执行效率
-
最好情况、最坏情况、平均情况时间复杂度
有序度不同的数据，算法的时间复杂度不同 -
时间复杂度的系数、常数 、低阶
时间复杂度反映的是数据规模 n 很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。
但在实际开发中，排序算法中的数据集一般是有限的，有的可能还比较小，所以这个时候不能忽略系数、常数、低阶，要考虑进去 -
比较次数和交换（或移动）次数
基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。
TODO：那些是基于比较的排序算法
排序算法的内存消耗
算法的内存消耗可以通过空间复杂度来衡量。
针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in place）。
原地排序算法，就是特指空间复杂度是 O(1) 的排序算法
排序算法的稳定性
稳定性：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
为什么要引入稳定性？
对于纯数据的排序，数据是否改变顺序没什么影响
但实际业务开发过程中，大多是对一个对象进行排序，而一个对象有多个属性。
比如我们现在要给电商交易系统中的“订单”排序。订单有两个属性，一个是下单时间，另一个是订单金额。如果我们现在有 10 万条订单数据，我们希望按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序。对于这样一个排序需求，我们怎么来做呢？
最先想到的方法是：我们先按照金额对订单数据进行排序，然后，再遍历排序之后的订单数据，对于每个金额相同的小区间再按照下单时间排序。这种排序思路理解起来不难，但是实现起来会很复杂。
借助稳定排序算法，这个问题可以非常简洁地解决。解决思路是这样的：
- 先按照下单时间给订单排序，注意是按照下单时间，不是金额。
- 排序完成之后，用稳定排序算法，按照订单金额重新排序。
两遍排序之后，得到的订单数据就是按照金额从小到大排序，金额相同的订单按照下单时间从早到晚排序的。因为稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变。
冒泡排序（Bubble Sort）
原理：
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
代码实现：
// 冒泡排序，a表示数组，n表示数组大小
public void bubbleSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; ++i) {
// 提前退出冒泡循环的标志位
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有数据交换
}
}
if (!flag) break; // 没有数据交换，提前退出
}
}
算法分析：
- 原地排序算法，即空间复杂度为O（1），因为只有在进行数据交换时申请一个临时空间用于交换数据
- 稳定排序算法，相同的元素排序前后顺序没有改变
-
时间负复杂度：最好O（n），最坏O(n2），平均O（n2）
TODO：平均复杂度的计算过程
借助于有序度，逆序度和满有序度进行计算
有序度：数组中具有有序关系的元素对的个数。有序元素对：a[i] <= a[j], 如果i < j。
有序度
对于一个倒序排列的数组，比如 6，5，4，3，2，1，有序度是 0；对于一个完全有序的数组，比如 1，2，3，4，5，6，有序度就是 n(n-1)/2，也就是 15。
我们把这种完全有序的数组的有序度叫作满有序度*。
逆序度：
插入排序
原理：
一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？
-
遍历数组，找到数据应该插入的位置将其插入即可。
插入数据前，要把要插入位置之后的数据进行后移，腾挪出空间给新插入的数据
有序数组插入一个新元素
上面一个动态排序的过程，即动态地往有序集合中添加数据，我们可以通过这种方法保持集合中的数据一直有序。
而对于一个静态的数组，我们如何借鉴上面的插入思想保证其有序呢？
- 将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。
插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
插入排序也包含两种操作，一种是元素的比较，一种是元素的移动。当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。
思考：对于一个给定的数据序列，使用插入排序算法使其有序，需要移动多少次元素？
解答：移动次数是固定的，等于逆序度
代码实现：
// 插入排序，a表示数组，n表示数组大小
public void insertionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 1; i < n; ++i) {
int value = a[i];
int j = i - 1;
// 查找插入的位置
for (; j >= 0; --j) {
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
}
a[j+1] = value; // 插入数据
}
}
算法分析：
- 原地排序算法
- 稳定排序算法
- 时间复杂度：最好O（n），最坏O(n2），平均O（n2）
选择排序
原理：
选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
代码：
算法分析
- 原地排序算法
- 非稳定排序算法
- 最好，最坏和平均时间复杂度都是O（n2）
排序画图工具：https://visualgo.net/en
