一、排序算法简介
排序是对批量数据按照一定的顺序进行排列的操作。
1.1 学习排序算法的要点
算法原理、代码实现、评价算法优劣。
-
时间性能：最好、最坏、平均时间复杂度；
-
内存占用：是否原地排序，原地排序算法，特指空间复杂度是 O(1) 的排序算法；
-
稳定性：相等的数据，排序前后顺序是否有变化，顺序不变是稳定排序算法。
| 排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 | 算法核心 |
| 冒泡排序 | O(n2) | O(1) | 稳定 | 比较交换 |
| 选择排序 | O(n2) | O(1) | 不稳定 | 比较交换 |
| 插入排序 | O(n2) | O(1) | 稳定 | 插入排序 |
| 希尔排序 | O(n1.3) | O(1) | 不稳定 | 插入排序 |
| 归并排序 | O(nlog2n) | O(n) | 稳定 | 比较合并 |
| 快速排序 | O(nlog2n) | O(log2n) | 不稳定 | 比较交换 |
| 桶排序 | O(n) | O(n) | 稳定 | 非比较 |
| 计数排序 | O(n) | O(n) | 稳定 | 非比较 |
| 基数排序 | O(n) | O(n) | 稳定 | 非比较 |
1.3 有序度与逆序度
有序度是数组中具有有序关系的元素对的个数。有序元素对用数学表达式表示如下：
有序元素对：对于数组 arr，如果下标 i < j，那么 arr[i] <= arr[j]。根据定义可知，数组 [4，5，6，3，2，1] 的有序度为 3，因为其有序元素对为 3 个，分别是：（4，5） （4，6） （5，6）。
倒序排列的数组，有序度为 0；完全有序的数组，有序度为 n(n-1)/2，比如，数组 [1，2，3，4，5，6] 的有序度为 15，这种完全有序数组的有序度叫做满有序度。
逆序度与有序度正好相反。用数学表达式表示如下：
逆序元素对：对于数组 arr，如果下标 i < j，那么 arr[i] > arr[j]。数组 [4，5，6，3，2，1] 的逆序度为 12，因为其逆序元素对为 12 个，分别是：（4，3）（4，2）（4，1）（5，3）（5，2）（5，1）（6，3）（6，2）（6，1）（3，2）（3，1）（2，1）。
根据有序度、逆序度、满有序度的概念，可以得到一个公式：逆序度 = 满有序度 - 有序度。
数组排序的实质，就是增加有序度，减少逆序度的过程，最后达到满有序度，排序完成。
二、常见排序算法
2.1 冒泡排序
2.1.1 算法原理
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，如果不满足大小关系要求，就进行交换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序。
示例：对数组 arr = [4，5，6，3，2，1] 从小到大进行冒泡排序。
第1次冒泡：
第2次冒泡：
第3次冒泡：
第4次冒泡：
第5次冒泡：
第6次冒泡：
冒泡过程回顾
冒泡排序算法优化
思路：当某次冒泡操作没有数据交换时，说明数组已经完全有序，不用再进行后续的冒泡操作。
示例：对数组 arr = [3，5，4，1，2，6] 从小到大进行冒泡排序。
第1次冒泡：
第2次冒泡：
第3次冒泡：
第4次冒泡：
第4次冒泡操作无数据交换，说明数组已经完全有序，不用再进行后续的冒泡操作。
2.1.2 代码实现
/**
* 冒泡排序：时间复杂度 O(n^2)，空间复杂度 O(1)，稳定
*
* @param arr 待排序数组
*/
public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) {return;}boolean isSwap = false;for (int i = 0, len = arr.length; i < len - 1; i++) { // 冒泡操作的次数for (int j = 0; j < len - 1 - i; j++) { // 每次冒泡比较的元素if (arr[j] > arr[j + 1]) {swap(arr, j, j + 1);isSwap = true;}}// 优化：没有交换代表数组已经完全有序if (!isSwap) {return;}}
}private static void swap(int[] arr, int i, int j) {if (i == j) {return;}arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];
}
2.1.3 算法评价
时间复杂度
最好时间复杂度：O(n)
最好情况下，要排序的数组已经是有序的，只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。
最坏时间复杂度：O(n2)
最坏情况下，要排序的数组刚好是倒序排列的，需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n2)。
平均时间复杂度：O(n2)
平均时间复杂度就是加权平均期望时间复杂度，分析的时候要结合概率论的知识。对于包含 n 个数据的数组，这 n 个数据就有 n! 种排列方式。不同的排列方式，冒泡排序执行的时间肯定是不同的。比如我们前面举的那两个例子，其中一个要进行 6 次冒泡，而另一个只需要 4 次。如果用概率论方法定量分析平均时间复杂度，涉及的数学推理和计算会很复杂。这里我们通过“有序度”和“逆序度”来进行分析。
冒泡排序包含两个操作原子：比较和交换。每交换一次，有序度就加 1。不管算法怎么改进，交换的总次数是确定的，即为逆序度，也就是 n*(n-1)/2 - 初始有序度。第1个示例中的数组就是 15 – 3 = 12，要进行 12 次交换操作。
对于包含 n 个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏情况下，初始状态的有序度是 0，所以要进行 n*(n-1)/2 次交换。最好情况下，初始状态的有序度是 n*(n-1)/2，就不需要进行交换。我们可以取个中间值 n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。换句话说，平均情况下，需要 n*(n-1)/4 次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是 O(n2)，所以平均情况下的时间复杂度就是 O(n2)。这个平均时间复杂度推导过程并不严谨，但是很实用，毕竟概率论的定量分析太复杂，不太好理解。
空间复杂度
冒泡过程只涉及相邻元素的比较和交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。
稳定性
冒泡排序中，只有交换才会改变两个元素的前后顺序。当相邻的两个元素大小相等时，我们不做交换，所以相同大小的数据在排序前后不会改变顺序，这样就可以保证冒泡排序是稳定的排序算法。
