如何分析排序算法
算法的执行效率
- 最好情况、最坏情况、平均时间复杂度
要了解这三种情况分别对应什么样的原始数据输入。
- 时间复杂度的系数、常数、低阶
时间复杂度是当数据规模 n 很大时的一个增长趋势，所以可以忽略系数、常数、低阶。
但在实际软件开发中，我们可能要排序的是 10 个、100 个、 1000 个这样的小规模数据。这时我们就要分析每个整个 T(n），而不仅仅是 O(n) 了。
- 比较次数和交换（或移动）次数
排序算法分为基于比较的算法，还有不基于比较的算法。如果我们分析基于比较的算法，那就同时把这两种操作：比较和交换 一起考虑。
算法的内存消耗
算法的内存消耗应该被考虑。不过还可以了解一个概念：原地排序特指空间复杂度是 O(1) 的排序算法。
排序算法的稳定性
排序算法的稳定性指的是，如果待排序列中存储了相同的元素，那么经过排序之后，相等的元素之间原有的先后顺序不变。
O(n2) 的排序算法
冒泡排序
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。一次冒泡排序会让至少一个元素移动到它应该在的位置，重复 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; // 没有数据交换，提前退出
}
}
插入排序
插入排序的过程，就是不断将一个新的元素插入到一个有序的数组的过程。
// 插入排序，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; // 插入数据
}
}
选择排序
选择排序和插入排序类似，也是区分已排序区间和未排序区间。但是选择排序每次是选择未排序区间中最小的元素，将其添加到已排序列的末尾。而选择排序是固定选择第一个未排序的元素插入到已排序序列的合适位置。
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;
}
}
// 交换
int tmp = a[i];
a[i] = a[minIndex];
a[minIndex] = tmp;
}
}
三个问题
是原地排序算法吗？
这三个排序都是在原数组上进行排序排序，只需要常量级的临时空间，所以它们的空间复杂度是 O(1)，是原地排序算法
是稳定的排序算法吗？
冒泡排序和插入排序是稳定的排序算法，选择排序不是稳定的排序算法。
冒泡排序不对相同的元素做交换。插入排序把值相同的元素，将后面出现的元素插入到前面的元素后面，所以也是稳定的算法。
选择排序会找出未排序元素中的最小值，和未排序元素的第一个做交换，这个交换是不稳定的。
时间复杂度是多少？
- 有序度，逆序度，满有序度
有序度是数组中具有有序关系的元素对的个数。完全有序的数组，有序度就是 n*(n-1)/2，它的有序度叫满有序度。逆序度跟有序度相反。
总结公式就是 逆序度 = 满有序度 - 有序度
- 冒泡排序
冒泡排序最好情况下时间复杂度是 O(n)，即要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了。
最坏情况的时间复杂度是 O(n2)，这时要排序的数组是逆序的，需要进行 n 次冒泡操作。
对于冒泡排序的时间复杂度分析如下：冒泡排序每次交换，减少一个逆序度。故冒泡排序的具体每次执行的时间跟输入数据的逆序度息息相关，假如输入一个完全有序的数组，那么这个数组的逆序度就是 0，只需要进行 0 次交换，假如输入的数组是一个完全逆序的数组，那么它的逆序度就是 n(n-1)/2，需要进行 n(n-1)/2 次交换。我们不严谨地取个中间值 n*(n-1)/4，表示初始有序度不是很高也不是很低的平均情况。按照这样，平均时间复杂度就是 O(n2)。
- 插入排序
插入排序最好的时间复杂度是 O(n)，即要排序的数组已经有序，我们从尾到头每次只需要比较一个数据就可以确定插入的位置。
插入排序最坏的时间复杂度是 O(n2)，即待排序的数组完全逆序，每次插入都相当于在数组的第一个位置插入新的数组，这个插入的时间复杂度我们在数组那节分析过，是 O(n)，又一共有 n 个元素，所以最终的复杂度就是 O(n2)。
同样，我们在数组那节分析过，在数组插入一个数据的平均时间复杂度是 O(n)，所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度是 O(n2)。
- 选择排序
选择排序最好、最坏、平均时间复杂度都是 O(n2)。
选择排序每次需要比较整个未排序数组的的所有元素，找出最小的元素插入到已排序数组的最末端。这样每轮的时间复杂度是 O(n)，循环执行 n 次，时间复杂度就是 O(n2)。不受数组排列顺序的影响。
相关问题
冒泡排序和插入排序的时间复杂度都是 O(n2)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎？
我们在前面分析过，冒泡排序不管怎么优化，元素交换的次数是一个固定的值，是原始数据的逆序度。插入排序是同样的，不管怎么优化，元素移动的次数等于原始数据的逆序度。
但是，仔细分析下，冒泡排序的交换操作要比插入排序的移动操作复杂得多，冒泡排序每次需要做三个赋值操作，而插入排序只需要做一个移动操作。
冒泡排序中数据的交换操作：
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;
}
如果不严谨地把每次操作地时间粗略估计为单位时间 (unit_time)，然后分别用冒泡排序和插入排序对同一个逆序度为 K 的数组进行排序。用冒泡排序，需要进行 K 次交换操作，每次需要 3 个赋值语句，所以交换操作总耗时 3 * K 个单位时间。而插入排序中移动数据的总时间为 K 个单位时间。
特定的算法是依赖特定的数据结构的。上面几种算法都是基于数组的。如果将数据结构存储在链表中，这三种排序还能正常工作吗？如果能，那相应的时间、空间复杂度是多少？
对于这个问题，首先要明确一个前提，是否允许修改链表节点的 value 值，还是只能改变节点的位置。一般而言，考虑只能改变节点位置的情况。冒泡排序相比于数组实现，比较次数一致，但是交换操作更加复杂了。插入排序相比于数组实现，比较次数一致，但是插入操作不需要再改变后续节点，但如果是单链表，排序结束后可能要倒置链表。而对于选择排序，比较次数和插入次数都一致，但是由于链表的插入操作更复杂一点，可能会比数组操作慢一点点，变化不大。
综上，冒泡排序会慢一些，而选择排序系数会减小，选择排序变化不大。
