【基础算法】排序算法

一、排序算法简介

排序是对批量数据按照一定的顺序进行排列的操作。

1.1 学习排序算法的要点

算法原理、代码实现、评价算法优劣。

1.2 评价排序算法的优劣

排序算法的优劣可以从以下 3 个方面进行评价：

• 时间性能：最好、最坏、平均时间复杂度；

• 内存占用：是否原地排序，原地排序算法，特指空间复杂度是 O(1) 的排序算法；

• 稳定性：相等的数据，排序前后顺序是否有变化，顺序不变是稳定排序算法。

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(n²)

最坏情况下，要排序的数组刚好是倒序排列的，需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n²)。

平均时间复杂度：O(n²)

平均时间复杂度就是加权平均期望时间复杂度，分析的时候要结合概率论的知识。对于包含 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(n²)，所以平均情况下的时间复杂度就是 O(n²)。这个平均时间复杂度推导过程并不严谨，但是很实用，毕竟概率论的定量分析太复杂，不太好理解。

空间复杂度

冒泡过程只涉及相邻元素的比较和交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。

稳定性

冒泡排序中，只有交换才会改变两个元素的前后顺序。当相邻的两个元素大小相等时，我们不做交换，所以相同大小的数据在排序前后不会改变顺序，这样就可以保证冒泡排序是稳定的排序算法。