前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课
以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。
1. 排序算法
1.1 介绍
下面是我们常用的 8 种排序算法，按照时间复杂度分成了三类，如下图
1.2 排序算法的执行效率
最好情况、最坏情况、平均情况时间复杂度
以及对应的要排序的原始数据，有序度不同的数据，对于排序的执行时间是有影响的时间复杂度的系数、常数、低阶
时间复杂度反映的是数据规模 n 很大时的一个增长趋势，会忽略系数、常数、低阶，但实际开发中，排序的可能是 10 个、100 个、1000 个数据，在对同一阶时间复杂度的排序算法性能对比时，需要把系数、常数、低阶考虑进来。比较次数和交换（移动）次数
基于比较的排序算法的执行过程，会涉及两种操作：比较大小和元素交换或移动，也需要考虑进去
1.3 排序算法的内存消耗
算法的内存消耗可以通过空间复杂度来衡量，针对排序算法的空间复杂度，还引入了一个新的概念：原地排序。原地排序算法，就是特指空间复杂度是 O(1)的排序算法。
1.4 排序算法的稳定性
什么是稳定的排序算法？就是如果待排序序列中存在值相等的元素，经过排序后，相等元素之间原有的先后顺序不变，否则就是不稳定的排序算法。
举个例子，比如有一组数据 2 9 3 4 8 3，按照大小排序之后就是 2 3 3 4 8 9，经过某种排序算法排序之后，如果两个 3 的前后顺序没有改变，那这种排序算就是稳定的排序算法，否则就是不稳定的排序算法。
2. 有序度&逆序度
-
有序度是数组中具有有序关系的元素对的个数
image.png
对于一个倒序排列的数组，比如 6 5 4 3 2 1，有序度为 0；
对于一个有序排列的数组，比如 1 2 3 4 5 6，有序度就是n*(n-1)/2，就是 15，完全有序，为满有序度。
逆序度的定义和有序度相反，并且逆序度 = 满有序度 - 有序度。我们排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，说明排序完成。
3. 冒泡排序
冒泡排序只会操作相邻的两个数据，每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系需求。如果不满足就让它俩互换，一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
对一组数据 4，5，6，3，2，1，从小到大进行排序，第一次冒泡操作示例如下：
经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上了，要想完成所有数据的排序，我们只要进行 6 次冒泡操作就行了：
我们可以对相面的冒泡过程进行优化，当某次冒泡操作没有数据交换时，说明已经达到完全有序，不需要在进行后续的冒泡操作，如下图：
代码如下：
// 冒泡排序，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^2)
image.png
4. 插入排序
主要思想就是在有序的数组中，通过遍历数组，将新的数据插入到合适的位置，继续保持数组有序：
就是将数组中的数据分为已排序区间和未排序区间，初始时已排序区间只有数组的第一个元素。插入算法的核心思想就是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。
代码如下：
// 插入排序，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(1)，为原地排序算法
- 是稳定的排序算法，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面元素的后面，保持原有的前后顺序不变
- 平均时间复杂度为 O(n^2)
5. 选择排序
选择排序实现思路类似于插入排序，也分为已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾（交换）：
- 选择排序空间复杂度为 O(1)，也是一种原地排序算法
- 时间复杂度为 O(n^2)
- 选择排序是一种不稳定的排序算法，相对于冒泡排序和插入排序，选择排序稍微逊色
6. 总结
冒泡排序不管怎么优化，元素交换的次数总是原始数据的逆序度；
插入排序不管怎么优化，元素移动的次数也是原始数据的逆序度。
从代码实现上看，冒泡排序的数据交换要比插入排序的数据移动复杂，冒泡排序需要 3 个赋值操作，插入排序只需要 1 个，所以插入排序要优于冒泡排序：
冒泡排序中数据的交换操作：
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true;
}
插入排序中数据的移动操作：
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
- 分析&评价一个排序算法，要从执行效率、内存消耗和稳定性三个方面来看
