目录
1. 排序算法基础
1.1 常见排序算法的时间复杂度
排序算法有很多种，最常用的包括：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序。按照时间复杂度可分为三类：O(n^2)、O(nlogn)、O(n)，如下图所示：
1.2 如何分析一个排序算法
- 最好情况、最坏情况、平均时间复杂度
- 时间复杂度的系数、常数、低阶
- 比较次数和交换（或移动）次数
1.3 排序算法的内存消耗
算法的内存消耗可以通过空间复杂度来衡量。不过，针对排序算法的空间复杂度，我们还引入了一个新的概念，原地排序（Sorted in Place）。原地排序算法，就是特指空间复杂度是O(1)的算法。
本文提到的冒泡、插入、选择排序，都是原地排序算法
1.4 排序算法的稳定性
仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法，还有一个重要的度量指标，稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变，那么这个算法就是稳定的。
1.5 有序度/逆序度
1. 有序度
有序度是数组中具有有序关系的元素对的个数：
有序元素对：a[i] <= a[j], 如果 i < j
同理，对于一个倒序排列的数组，例如6, 5, 4, 3, 2, 1，有序度是0；对于一个完全有序的数组，例如1, 2, 3, 4, 5, 6，有序度是n*(n-1)/2，也就是15，又称满有序度。
2. 逆序度
逆序度的定义正好跟有序度相反：
逆序元素对：a[i] > a[j], 如果 i < j
3. 有序度和逆序度之间的关系
关于有序度、逆序度、满有序度这三个概念，还可以得到一个计算公式：
逆序度 = 满有序度 - 有序度
本质上，排序的过程就是一种增加有序度、减少逆序度、最后达到满有序度的过程。
2. 冒泡排序
2.1 基本思路
冒泡排序（Bubble Sort）只会比较相邻的两个元素，看是否满足大小关系要求，如果不满足就让他俩交换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。
可以看到，经过一次冒泡操作之后，6这个元素已经存储在正确的位置上。要想完成所有数据的排序，只需要进行n次这样的冒泡操作就可以：
2.2 优化技巧
实际上，上述冒泡的过程还可以进行优化。当某次冒泡操作已经没有数据交换的时候，就说明已经达到了完全有序，不用再继续执行后续的冒泡操作了。如下图的例子，6个元素只需要进行4次冒泡：
2.3 算法分析
- 冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为
O(1)，是一个原地排序算法 - 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，因此冒泡排序是稳定的排序算法
- 冒泡排序的最好情况是要排序的数据已经是有序的了，只需要进行一次冒泡操作，时间复杂度为
O(n)。而最坏情况是要排序的数据刚好都是倒序的，需要进行n次冒泡操作，所以最坏情况时间复杂度为O(n^2)
再来分析一下平均情况：要排序的数组初始状态下的有序度为3，元素个数n=6。所以排序完成之后终态的满有序度为n*(n-1)/2=15：
冒泡排序包含了两个操作原子：比较和交换。每交换一次，有序度就加 1。所以不管算法怎么改进，交换次数总是确定的，即为逆序度。上图的例子中就是12，所以要进行 12 次交换操作。
- 最坏情况下，初始状态的有序度为
0，要进行n*(n-1)/2次交换 - 最好情况下，初始状态的有序度为
n*(n-1)/2，不需要进行交换 - 取两者中间值
n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况
所以平均情况下，需要n*(n-1)/4次交换操作。比较操作肯定要比交换操作多，而复杂度的上限是O(n^2)，所以经过不严格的推导可得出，冒泡排序平均情况下的时间复杂度为O(n^2)。
2.4 Java 实现
// 冒泡排序，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; // 没有数据交换，提前退出
}
}
2.5 Go 实现
注：Go 语言提供了交换操作的语法糖：
a[j], a[j+1] = a[j+1], a[j]
// 冒泡排序，a 表示数组，n 表示数组大小
func BubbleSort(a []int, n int) {
if n <= 1 {
return
}
for i := 0; i < n; i++ {
// 提前退出标志
flag := false
for j := 0; j < n-i-1; j++ {
if a[j] > a[j+1] {
a[j], a[j+1] = a[j+1], a[j]
//此次冒泡有数据交换
flag = true
}
}
// 如果没有交换数据，提前退出
if !flag {
break
}
}
}
3. 插入排序
3.1 基本思路
对于一个有序的数组，为了继续保持数据有序，我们只需要遍历数组，找到数据应该插入的位置将其插入即可：
插入排序（Insertion Sort）正是借助上面的思想来实现排序。首先，我们将数组中的数据分为两个区间：已排序区间和未排序区间。初始已排序区间只有数组的第一个元素。插入算法的核心思想就是取未排序区间中的元素，在已排序区间中找到合适的插入位置并将其插入，重复这个过程直到未排序区间中元素为空，算法结束：
插入排序也包含两种操作原子：元素的比较和移动。
- 对于不同的查找插入点方法（从头到尾、从尾到头），元素的比较次数是有区别的
- 但对于一个给定的初始序列，移动操作的次数总是固定的，就等于逆序度：
3.2 算法分析
- 插入排序算法的运行并不需要额外的存储空间，空间复杂度为
O(1)，也是一个原地排序算法 - 对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序也是稳定的排序算法
- 最好情况下，数据全部有序，只需要从尾到头遍历所有数据，时间复杂度为
O(n)。最坏情况下，数据全部逆序，时间复杂度为O(n^2)。总的来看，平均时间复杂度为O(n^2)
3.3 Java 实现
// 插入排序，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; // 插入数据
}
}
3.4 Go 实现
// 插入排序，a 表示数组，n 表示数组大小
func InsertionSort(a []int, n int) {
if n <= 1 {
return
}
for i := 1; i < n; i++ {
value := a[i]
j := i - 1
// 查找要插入的位置并移动数据
for ; j >= 0; j-- {
if a[j] > value {
a[j+1] = a[j]
} else {
break
}
}
a[j+1] = value
}
}
4. 选择排序
4.1 基本思路
选择排序（Selection Sort）的实现思路类似于插入排序：也是分为已排序区间和未排序区间，但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾：
4.2 算法分析
- 选择排序的空间复杂度为
O(1)，也是一种原地排序算法 - 最好、最坏、平均时间复杂度都为
O(n^2) - 选择排序是一种不稳定的排序算法，原因在于每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性
例如
5, 8, 5, 2, 9这组数据，如果使用选择排序算法来排序的话，第一次找到最小元素为2，与第一个5交换位置，导致第一个5和中间的5前后顺序发生改变，所以就不稳定了
4.3 Java 实现
// 选择排序，a 表示数组，n 表示数组大小
public static void selectionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n - 1; ++i) {
// 查找最小值
int minIndex = i;
for (int j = i + 1; j < n; ++j) {
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
// 交换
if (minIndex != i) {
int tmp = a[i];
a[i] = a[minIndex];
a[minIndex] = tmp;
}
}
}
4.4 Go 实现
// 选择排序，a 表示数组，n 表示数组大小
func SelectionSort(a []int, n int) {
if n <= 1 {
return
}
for i := 0; i < n; i++ {
// 查找最小值
minIndex := i
for j := i + 1; j < n; j++ {
if a[j] < a[minIndex] {
minIndex = j
}
}
// 交换
if minIndex != i {
a[i], a[minIndex] = a[minIndex], a[i]
}
}
}
5. 为何插入比冒泡更受欢迎
- 冒泡排序和插入排序不管怎样优化，其元素交换次数是一个固定值，即原始数据的逆序度
- 从代码实现上来看，冒泡排序的数据交换比插入排序的数据移动要更复杂，交换需要
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;
}
因此，虽然冒泡排序和插入排序的时间复杂度都为O(n^2)，但是如果我们希望把性能优化做到极致，就首选插入排序。
插入排序的算法思路也有很大的优化空间，可以参考 希尔排序 | Wikipedia
6. 小结
