排序第零讲-基础篇

本系列试图结合原理和实践讲清楚排序。第零讲作为系列的开头会定义排序问题并讲解比较基础的两种排序算法：选择排序、插入排序。

排序问题的定义

我们先从最基础的排序问题入手，即将一个整型数组变为有序（可以是正序或倒序）。
基于比较的排序算法中都要用到两个最基础的操作

• 比较操作用于确定元素顺序
• 交换操作用于将元素换到有序位置。

// 交换数组中两个位置的值
public void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

//  比较两个整数a和b，a < b返回-1， a == b返回0，a > b返回1，倒序则相反
public int compareTo(int a, int b, boolean asc) {
    if (a == b) {
        return 0;
    } else {
        return (a < b ? -1 : 1) * (asc ? 1 : -1);
    }
} 

这里说明一下，整数的交换还可以采用异或的方式，但是这仅限于整数，且效率不一定高于直接交换，仅供参考。

// 交换数组中两个位置的值
public void swap(int[] nums, int i, int j) {
    nums[i] = nums[i] ^ nums[j];
    nums[j] = nums[i] ^ nums[j];
    nums[i] = nums[i] ^ nums[j];
}

选择排序

最直觉的排序方式应该就是选择排序了，即每次选出数组中最小的一个放在最前，最前面的元素已经有序，继续处理剩余元素，直到数组为空
举个例子，这里加粗显示每一步中被交换的最小元素

1. [3, 2, 5 ,4, 1] （原数组）
2. [1, 2, 5, 4, 3]
3. [1, 2, 5, 4, 3] （最小值在原位不需要交换）
4. [1, 2, 3, 5, 4]
5. [1, 2, 3, 4, 5] （排序完成）

代码如下

// https://leetcode.cn/problems/sort-the-people/submissions/577188726
public void sort(int[] nums, boolean asc) {
    // selection sort
    for (int i = 0; i <= nums.length - 2; i++) {
        int minIdx = i;
        for (int j = i + 1; j < nums.length; j++) {
            int min = nums[minIdx];
            int value = nums[j];
            if (compareTo(min, value, asc) == 1) {
                minIdx = j;
            }
        }
        swap(nums, minIdx, i);
    }
}

空间复杂度：算法仅使用了常数级别的空间，即\(O(1)\)
时间复杂度：按比较次数统计，第一次循环比较了n-1次（n为数组长度），之后每次的比较次数减一，结果为\(\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}\) ，从而时间复杂度为\(O(n^2)\)
算法效率是否和输入相关：选择排序的时间复杂度不受输入数组的有序程度影响，即使是已经有序的数组，排序的时间复杂度依然不变

插入排序

下面以同一个原数组[3, 2, 5 ,4, 1]演示插入排序的执行过程
插入排序的基本原理是向已经有序的数组中插入元素，新元素从后往前比较，插入到目标位置（之前的元素都不大于自身）后，整个数组仍然有序。
显然单个元素的数组是有序的，所以我们从下标1开始。

• 首先将元素2插入数组[3]，由于2小于3，将2和3交换，得到新数组[2, 3]
• 然后插入5，由于5大于数组的最大元素3，插入到尾部即可，得到[2, 3, 5]
• 插入4，和5交换，得到[2, 3, 4, 5]
• 插入1，和前面的所有元素交换，最终得到[1, 2, 3, 4, 5],排序完成

代码如下

// https://leetcode.cn/problems/sort-the-people/submissions/577189399/
    public void sort(int[] nums, boolean asc) {
        // insertion sort
        for (int i = 1; i < nums.length; i++) {
            for (int j = i - 1; j >= 0 && (-1 == compareTo(nums[j + 1], nums[j], asc)); j--) {
                swap(nums, j + 1, j);
            }
        }
    }

空间复杂度：算法仅使用了常数级别的空间，即\(O(1)\)
时间复杂度：

• 最坏情况为数组为倒序，如[3, 2, 1]，第一次循环(插入元素为2)需要比较1次，第二次循环(插入元素为1)需要比较2次，总比较次数为\(\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}\) ，此时时间复杂度为\(O(n^2)\)
• 最佳情况为数组有序，如[1, 2, 3]，只需比较n-1次，所以时间复杂度为\(O(n)\)
• 平均时间复杂度为\(O(n^2)\)

结语

本文从排序问题的定义入手，通过实例和代码讲解了选择排序和插入排序两个基础排序算法，为后续更高效的排序算法及其应用做铺垫。