当前位置：首页 > article >正文

【数据结构】(10) 排序算法

article 2025/2/21 4:37:56

一、排序算法

冒泡排序在C语言部分学过，堆排序上一章学过，还剩五种常见排序算法。以下默认从小到大排序。

稳定性：相同元素在排序过后，前后相对位置依旧不变。一个本身稳定的排序，可以改成不稳定的；但一个本身不稳定的排序，无法改为稳定的。

二、直接插入排序

2.1、算法思想

第一个元素默认已排好，第 i 个元素依次与第 i-1 ~ 0 个元素比较，大于 i 号元素的就往后移一位，小于等于 i 号元素的，i 号元素就插入在其后，结束此趟排序。

2.2、代码实现

    /**
     * 直接插入排序
     * 最坏时间复杂度：1 + 2 + 3 + ... + n = O(n^2)
     * 最好时间复杂度：O(n)，基本有序
     * 空间复杂度：O(1)
     * 稳定性：稳定
     */
    public static void insertSort(int[] arr) {
        // 第一个元素默认已排好序，从第二个元素开始
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i]; // 待排序元素
            // 与 i-1 ~ 0 之间的所有元素比较
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > temp) { // 大于 arr[i] 的元素，向后移动一位
                    arr[j + 1] = arr[j];
                } else { // 小于等于 arr[i] 的元素，在其后插入 arr[i]，结束次趟排序
                    // 与 0 位置的元素比较后，仅仅是 0 位置元素向后移动一位，并没有在 0 位置插入 arr[i]，就退出了内循环
                    // 因此，插入代码应该放在外循环。放在内循环，会导致没有考虑到在 0 位置插入 arr[i] 的情况。
//                    arr[j + 1] = temp;
                    break;
                }
            }
            // 在 0 位置插入的情况，退出时 j = -1
            arr[j + 1] = temp; // 插入 arr[i]
        }
    }

2.3、时间复杂度分析

最坏时间复杂度（倒序）：每第 i 个元素都要与前 i 个已排序好的元素比较。从第 2 个元素开始，1 + 2 + 3 + ... + n-1 = n*(n-1)/2 = O(n^2)。

最好时间复杂度（顺序）：每第 i 个元素都已经有序，只需要跟第 i-1 个元素比较一次。一共要比较 n-1 次，O(n)。如果序列基本有序的时候，可以使用直接插入排序算法。

二、希尔排序（缩小增量排序）

是优化版的直接插入排序。

2.1、算法思想

将数组分为 gap 组，组内进行直接插入排序，gap 逐渐缩小，直到 gap 为 1，此时数组已经基本有序，进行最后一次直接插入排序。（gap > 1 时，属于预排序，目的是让数组更接近有序。最后一次排序，数组已基本有序，排序就很快了。）

gap 的取法有很多，比如 n/2（后续每次 gap/2）、n/3+1。

gap 的分组是间隔 gap 个元素分为一组，而不是邻近元素分为一组：如下图，初始 gap=5，第 0 个元素和第 0+gap 个元素分为一组。

间隔元素分为一组的目的：排序后，让小的都在前一半，让大的都在后一半，更趋于有序。若是邻近元素分为一组，则没有这个规律，排序后数组是混乱的。

2.2、手动模拟希尔排序

gap=10/2=5 时，分5组。

组内进行直接插入排序。

gap=gap/2=5/2=2：

组内进行插入排序：

gap=2/2=1：

排序后：1 2 3 4 5 6 7 8 9。

2.3、代码实现

第一层循环，gap 从 n/2 逐步缩减到 1。第二层和第三层循环：组内进行直接插入排序。一组内：i 从 gap 开始，下一个组内元素递增 gap，直到 gap ≥ len 为止；j 从 i-1 开始，前一个组内元素递减 gap，直到 gap ＜ 0 结束。但这样存在一个问题，只排序好了一组，剩下的组并没有实现插入排序。

所以我们应该间断式地进行插入排序，将第二层循环的 i 自增 gap 改为自增 1，这一次对第一组的第二个元素进行插入排序，下一次对第二组的第二个元素进行插入排序……这样所有组都能完成插入排序。

    /**
     * 希尔排序
     * 时间复杂度：难以准确计算
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public static void shellSort(int[] arr) {
        int gap = arr.length / 2; // 初始步长。第一趟排序后，前一半元素小，后一半元素大
        // gap 逐渐缩减到 1（即最后对基本有序的一组元素进行插入排序）
        while (gap > 0) {
            shellInsertSort(arr, gap);
            gap /= 2;
        }
    }

    // 希尔排序中的插入排序
    private static void shellInsertSort(int[] arr, int gap) {
        // 从第一组的第2个元素开始，不同组交叉进行插入排序
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            // 组内每个元素之间间隔 gap
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if(arr[j] > temp) {
                    arr[j + gap] = arr[j];
                }
                else {
                    break;
                }
            }
            arr[j + gap] = temp;
        }
    }

2.4、时间复杂度分析

若数组有 n 个元素，gap 组，则组内有 n/gap 个元素。最坏情况下，组内的比较次数为 1+2+……+(n/gap-1)。

以 gap=gap/2 为例子，当 gap=n/2 时，比较次数为 n/2 * 1 = (1/2)*n；

当 gap=n/4 时，比较次数为 n/4 * (1+2+3) = (3/2)*n；

当 gap=n/8 时，比较次数为 n/8 * (1+2+3+4+5+6+7) = (7/2)*n；

当 gap=n/16 时，比较次数为 n/16 * (1+2+……+15) = (15/2)*n；

…………

当 gap=1时，数组基本有序，比较次数接近 n 。

因此，我们可以得知，随着 gap 的缩减，比较次数会先递增，再递减，会存在一个最大比较次数。而 gap 为何值时，比较次数达到最大，我们是难以计算的。这也就导致，希尔排序的时间复杂度难以准确计算。

根据《数据结构(C语言版)》严蔚敏所说，希尔排序的时间复杂度大致为 O(N^1.5)。

总的来说，时间复杂度是比直接插入排序法更优的。

我们通过测试，也能直观地看到这种差距：（3万个随机整数排序）

三、选择排序

3.1、算法思想

在 n 个元素中选择最小值，与第一个位置的元素交换；在后 n-1 个元素中选择最小值，与第二个位置的元素交换……直到排好前 n-1 个小元素，最后一个元素自然排好。

3.2、代码实现

    /**
     * 选择排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public static void selectSort(int[] arr) {
        // 排前 n-1 个元素，最后一个元素自然排好
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i; // 最小元素的索引
            // 找出 i 到 n-1 之间最小的元素的索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换 i 与最小元素。最小元素索引为 i 时，不需要交换
            if (minIndex!= i) {
                swap(arr, i, minIndex);
            }
        }
    }

3.3、时间复杂度分析

不管时倒序还是正序，都需要比较 i 后所有的元素，以找到最小值，因此不分最好、最坏时间复杂度。

时间复杂度：找到第1小元素，比较 n-1 次，找到第2小元素，比较 n-2 次，……，找到第二大元素，比较 1 次。因此，(n-1)+(n-2)+……+2+1 = n*(n-1)/2，O(n^2)。

3.4、另一种选择排序

思路：在未排序的元素中选择最小值和最大值，分别与第一个未排序元素和最后一个未排序元素交换。

    /**
     * 选择排序：同时选择最小值和最大值
     */
    public static void selectSort2(int[] arr) {
        // left 和 right 分别指向未排序部分的第一个元素和最后一个元素
        int left = 0;
        int right = arr.length - 1;
        // left 和 right 相遇时，排序完成
        while (left < right) {
            // 找出 [left, right] 范围内的最小值和最大值
            int minIndex = left;
            int maxIndex = left;
            for (int i = left + 1; i <= right; i++) {
                if (arr[i] < arr[minIndex]) {
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            // 交换最小值和 left 指向的元素
            if (minIndex!= left) {
                swap(arr, left, minIndex);
            }
            // 如果 left 指向的元素就是最大值，left 与最小值交换后，会把最大值换走
            // 因此，当 left 指向的元素就是最大值时，需要把 maxIndex 改为 minIndex（最大值被换到的位置）
            if (arr[left] == arr[maxIndex]) {
                maxIndex = minIndex;
            }
            // 交换最大值和 right 指向的元素
            if (maxIndex != right) {
                swap(arr, right, maxIndex);
            }
            // 移动 left 和 right 指针
            left++;
            right--;
        }
    }

四、堆排序

4.1、算法思想

创建大根堆，每次将最大值堆顶换到最后一个未排序元素位置，再从堆顶开始向下调整，调整范围是未排序元素。

4.2、代码实现

    /**
     * 堆排序
     * 时间复杂度：O(N*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public static void heapSort(int[] arr) {
        // 建堆，O(N*logN)
        buildMaxHeap(arr, arr.length);
        // 排序,O(N*logN)
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i); // 堆顶元素与最后一个元素交换
            shiftDown(arr, 0, i); // 堆调整
        }
    }

    // 创建大根堆
    private static void buildMaxHeap(int[] arr, int n) {
        // 从下往上调整每一棵子树
        for (int parent = (n-1-1) / 2; parent >= 0; parent--) {
            shiftDown(arr, parent, n);
        }
    }

    // 向下调整堆
    private static void shiftDown(int[] arr, int i, int n) {
        int parent = i;
        int child = 2 * i + 1;
        while (child < n) { // 存在孩子
            if (child + 1 < n && arr[child + 1] > arr[child]) { // 存在右孩子，且右孩子大于左孩子
                child++; // 最大孩子指向右孩子
            }
            if (arr[child] > arr[parent]) {
                swap(arr, child, parent); // 孩子大于父节点，交换
                parent = child; // 继续向下调整
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

五、冒泡排序

5.1、算法思想

每次将邻近值比较，逐渐将最大值“冒”到后面。

5.2、代码实现

    /**
     * 冒泡排序：优化版本，分析时间复杂度时，不考虑优化情况
     * 时间复杂度：O(N^2)
     *    如果考虑优化：O(N)，对比一趟就结束
     * 空间复杂度：O(1)
     */
    public static void bubbleSort(int[] arr) {
        // 最后一个元素自然排好
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flag = false; // 标记是否发生交换
            // j+1 < arr.length-i 每一趟排序后，最大的元素被排到最后
            for (int j = 0; j < arr.length - i - 1; j++) {
                // 相邻元素比较，较大的元素向后冒泡
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = true; // 发生交换
                }
            }
            // 若没有发生交换，说明已排序完成，退出
            if (!flag) {
                break;
            }
        }
    }

六、快速排序

6.1、算法思想

一种二叉树结构的交换排序法。现在序列中任选一个元素作为基准，经过一趟排序后，基准左边的元素都小于基准，基准右边的元素都大于基准。分别对左、右子序列重复上述过程，直到序列不可再分。

6.2、主逻辑代码实现

6.2.1、非递归版

    /**
     * 快速排序，主逻辑
     * 时间复杂度：O(N*logN)
     *      最坏情况：O(N^2)，有序或逆序时
     * 空间复杂度：O(logN)
     *      最坏情况，O(N)
     * 稳定性：不稳定
     */
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int left, int right) {
        // 序列长度小于等于 1，结束递归
        if (left >= right) {
            return;
        }
        // 选取基准元素
        int divPosition = partitionHoare(arr, left, right);
        // 左子序列排序
        quickSort(arr, left, divPosition);
        // 右子序列排序
        quickSort(arr, divPosition + 1, right);
    }

6.2.2、递归版

分析：模拟递归，首先想到栈，后进先出。过程：找到序列的划分后，得到基准下标。右子序列的 left 和 right 入栈，左子序列的 left 和 right 入栈，入栈条件是 left > right，才有必要继续划分。弹出栈顶的两个元素，即 left 和 right，继续划分。执行上述循环，直到栈空。

    public static void quickSort2(int[] arr) {
        Stack<Integer> stack = new Stack<>(); // 栈，保存每个子序列的左右边界
        // 初始边界
        if (arr.length > 1) {
            stack.push(0);
            stack.push(arr.length - 1);
        } else {
            return;
        }
        // 栈为空，表示没有子序列需要划分
        while (!stack.isEmpty()) {
            int right = stack.pop();
            int left = stack.pop();
            // 划分子序列
            int divPosition = partitionHoare(arr, left, right);
            // 右子序列边界入栈
            if (divPosition > left) {
                stack.push(left);
                stack.push(divPosition);
            }
            // 左子序列边界入栈
            if (divPosition + 1 < right) {
                stack.push(divPosition + 1);
                stack.push(right);
            }
        }
    }

6.3、按基准划分的方法

不同的划分方法，得到的划分结果也不同。

6.3.1、Hoare 法

思路：选取序列的第一个元素作为基准，left、right 分别指向首、尾元素，每趟交换前，right 直到找到小于基准的元素停止自减，left 直到找到大于基准的元素停止自增，自减自增过程中指针left 不能大于 right（① 可以防止指针越界。② 相遇时就表明序列已遍历完，并且它们指向的元素必定小于或等于基准）。最后，将左边的大元素与右边的小元素进行交换。重复寻找交换元素并交换的过程，直到 left 与 right 相遇。循环结束后，交换基准与 left 与 right 相遇时指向的元素。

    private static int partitionHoare(int[] arr, int left, int right) {
        int div = left;
        while (left < right) {
            // 右指针向左移动，直到遇到小于基准元素的元素
            while (left < right && arr[right] >= arr[div]) {
                right--;
            }
            // 左指针向右移动，直到遇到大于基准元素的元素
            while (left < right && arr[left] <= arr[div]) {
                left++;
            }
            // 交换左右指针指向的元素，即将小于基准元素的元素放到左边，大于基准元素的元素放到右边
            swap(arr, left, right);
        }
        // 基准元素归位
        swap(arr, div, right);
        // 返回基准元素的索引
        return right;
    }

① 为什么不能 left 先找：完成最后一次交换后，left 和 right 之间的序列已经划分好。如果 left 先找，必然是 left 自增遇到 right 停止自增，而 right 此时指向的位置必然是大于等于基准的，left = right 最后与基准交换就可能出现错误，让大于基准的数放到了左边。

② 为什么 arr[right] >= div，要包含等于：如果不包含等于，表明 left 或 right 遇到等于基准的元素会停止自增自减，然后触发交换。如果是序列 6……6，left 将始终指向首，right 始终指向尾，导致死循环。

6.3.2、挖坑法

思路：默认选序列首元素为基准，基准另外存在一个变量中，此时序列首位置 left 就是一个坑。right 找到小于基准的，就放到 left 的坑中，right 位置成为坑；left 找到大于基准的，就放到 right 的坑中，left 成为坑。重复上述循环，直到相遇，最后将基准放到 left=right 指向的坑中。

    private static int partition2(int[] arr, int left, int right) {
        int div = arr[left];
        while (left < right) {
            // 右指针向左移动，直到遇到小于基准元素的元素，将小于基准元素的元素放到 left 位置的坑中
            while (left < right && arr[right] >= div) {
                right--;
            }
            arr[left] = arr[right];
            // 左指针向右移动，直到遇到大于基准元素的元素，将大于基准元素的元素放到 right 位置的坑中
            while (left < right && arr[left] <= div) {
                left++;
            }
            arr[right] = arr[left];
        }
        // 基准元素归位
        arr[left] = div;
        // 返回基准元素的索引
        return left;
    }

6.3.3、前后指针法（了解）

思路：如果 cur 指向小于基准的元素，且 pre 的下一个是 cur，则同时自增（pre 与 cur 之间没有大于基准的的元素）；如果 cur 指向大于基准的元素，仅 cur 自增，pre 负责守着 pre 后 cur 前的大于基准的元素；如果 cur 再次指向小于基准的元素，且 pre 的下一个不是 cur（pre 和 cur 之间存在大于基准的元素），pre 就把下一个守着的大于基准的元素跟 cur 指向的小于基准的元素交换，实现小的在左边，大的在右边。

    private static int partition3(int[] arr, int left, int right) {
        int pre = left; // 守着 pre 后 cur 前的大于基准的元素
        // 遇到大于等于基准的元素，就存在 pre 与 cur 之间（pre不自增），继续找
        // 遇到小于基准的元素，就判断 pre 与 cur 之间存没存大于等于基准的元素（pre要自增），存了就交换，实现大或等于的放左，小的放右，然后继续找；没存直接继续找
        int cur = left + 1;
        while (cur <= right) { // cur 不能越界
            if(arr[cur] < arr[left] && arr[++pre] != arr[cur]) {
                // cur 遇到小于基准的元素，pre 与 cur 之间存有大于等于基准的元素，pre 指向下一个大于基准的元素，然后交换
                swap(arr, pre, cur);
            }
            cur++; // 继续找
        }
        // 最后 pre 指向的位置就是基准元素的位置
        swap(arr, left, pre);
        return pre;
    }

6.4、复杂度分析

时间复杂度：k=logn 层二叉树，每层都比较了 n 次（划分阶段，会遍历子序列的所有元素），总共 n*logn 次。O(N*logN)。

最坏时间复杂度：有序或逆序时，k个元素的子序列，k-1 个元素都排在基准的一边。最后 n 个元素的排列结果，二叉树有 n 层，每层都要比较 n 个元素（下图中，只有1个元素的划分未画出）。 O(N^2)。

空间复杂度：递归深入的层数就是二叉树的层数。左子序列递归完成后，会回收内存，继续递归右子序列，因此，使用的最大内存空间是二叉树的高度 O(logN)。

最坏空间复杂度：二叉树高度为N。O(N)。

6.5、快速排序递归版的优化

从 6.4 小节我们知道，当序列基本有序时，如果只是简单的将序列首元素作为基准划分，会导致空间复杂度高，达到 O(N)。当 N 较大时，就容易导致栈溢出，简单粗暴的解决办法就是在idea上设置栈内存大小。

另一种是用改进的算法，避免因划分的左右子序列大小极度不均，导致的空间复杂度过高。

6.5.1、三数取中

思路：将首、中、尾元素取中位数，作为基准元素，让划分更均匀。

    public static void quickSort(int[] arr, int left, int right) {
        // 序列长度小于等于 1，结束递归
        if (left >= right) {
            return;
        }
        // 求中位数
        int div = median(arr, left, right);
        // 中位数作为基准
        swap(arr, left, div);
        // 选取基准元素
//        int divPosition = partitionHoare(arr, left, right);
//        int divPosition = partition2(arr, left, right);
        int divPosition = partition3(arr, left, right);
        // 左子序列排序
        quickSort(arr, left, divPosition);
        // 右子序列排序
        quickSort(arr, divPosition + 1, right);
    }


    /**
     * 三数取中
     */
    public static int median(int[] arr, int left, int right) {
        int mid = (left + right) / 2;
        // left 和 right 中，较大值作为 left
        left = arr[left] > arr[right]? left : right;
        if(arr[mid] > arr[left]) {
            return left;
        } else if(arr[mid] < arr[right]) {
            return right;
        } else {
            return mid;
        }
    }

6.5.2、结合插入排序

思路：快速排序时，当子序列越小越趋于有序。基本有序时，直接插入排序的效率高，时间复杂度为 O(N)。因此，可以当子序列小到一定范围时，改用直接插入排序，减少递归深度，并提高排序效率。

    public static void quickSort(int[] arr, int left, int right) {
        // 序列长度小于等于 1，结束递归
        if (left >= right) {
            return;
        }
        // 子序列长度小于等于 10 时，改用直接插入排序
        if (right - left + 1 <= 10) {
            insertSort(arr, left, right);
            return;
        }
        // 求中位数
//        int div = median(arr, left, right);
        // 中位数作为基准
//        swap(arr, left, div);
        // 选取基准元素
//        int divPosition = partitionHoare(arr, left, right);
//        int divPosition = partition2(arr, left, right);
        int divPosition = partition3(arr, left, right);
        // 左子序列排序
        quickSort(arr, left, divPosition);
        // 右子序列排序
        quickSort(arr, divPosition + 1, right);
    }
    
    private static void insertSort(int[] arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int temp = arr[i];
            int j = i - 1;
            while (j >= left && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

七、归并排序

7.1、算法思想

分治思想。先使子序列有序，再合并有序的子序列，得到有序的序列。如果是合并两个有序子序列，就叫二路归并。

合并思路：创建新的数组，存放合并后的结果。i，j 指针指向两个子序列的元素，更小的放入新数组，并指向下一个。一个子序列遍历完后，若另一个还没遍历完，就把另一个剩的元素直接加到新数组里。最后将合并后的数组复制到原数组对应位置。

7.2、代码实现

合并代码：

    public static void merge(int[] arr, int left1, int right1, int left2, int right2) {
        int[] temp = new int[right2 - left1 + 1];
        int i = left1;
        int j = left2;
        int k = 0;
        while (i <= right1 && j <= right2) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 剩的复制到结尾
        while (i <= right1) {
            temp[k++] = arr[i++];
        }
        while (j <= right2) {
            temp[k++] = arr[j++];
        }
        // 复制回原数组
        for (i = left1; i <= right2; i++) {
            arr[i] = temp[i - left1];
        }
    }

7.2.1、递归版

思路：先求中间位置，然后左、右子序列分别进行归并排序，再将两个有序的子序列合并。

    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }
    private static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, mid + 1, right);
    }

7.2.2、非递归版

思路：初始 gap=1，每次增加 gap 的一倍，逐渐增加到 gap=n/2，相邻两个分组两两合并。

    public static void mergeSort2(int[] arr) {
        for(int gap = 1; gap < arr.length; gap *= 2) {
            for(int i = 0; i < arr.length; i += gap * 2) { // 两两合并
                int mid = i + gap - 1;
                // 只够分一组的情况，不用合并
                if(mid >= arr.length - 1) {
                    break;
                }
                int right = Math.min(mid + gap, arr.length - 1); // 防止越界
                merge(arr, i, mid, mid + 1, right);
            }
        }
    }

7.3、复杂度分析

时间复杂度：每层每个子序列分裂为2组，有 logN 层，每层都会对比 N 次，时间复杂度 O(N*logN)。

空间复杂度：logN + N（存放合并后的序列），O(N)。

稳定性：稳定。

7.4、应用场景

当需要对大量数据进行排序时，需要进行外部排序（在外部磁盘中进行排序）。比如对 100 G 的数据进行排序，但是内存只有 1G 的情况。

首先将 100G的文件分为 200 份，每份 512M，选用任意一种排序算法，分别对每份文件在内存中进行排序。对每份文件进行合并时，在磁盘中用归并排序算法进行合并。

八、其它非基于比较的排序

8.1、计数排序

算法思想：计算待排序序列的最大值 max 和最小值 min，再创建一个计数数组 count，大小为 max-min+1。遍历原数组，将计数统计在 count 中，对应下标就是原数组的元素值。最后遍历 count 数组，对应 index 有多少计数，就在原数组中放置多少个 index。

使用场景：序列元素比较集中（连续）的情况。

代码实现：

    public static void countSort(int[] arr) {
        int max = arr[0];
        int min = arr[0];
        // 找出最大值和最小值，O(N)
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
            if (arr[i] < min) {
                min = arr[i];
            }
        }
        int[] count = new int[max - min + 1];
        // 统计每个元素出现的次数，O(N)
        for (int j : arr) {
            count[j - min]++;
        }
        // 遍历计数数组，将每个元素复制到原数组，O(max-min+1)
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            int temp = count[i];
            while (temp-- > 0) {
                arr[index++] = i + min;
            }
        }
    }

时间复杂度：O(max(N, max-min+1))。

空间复杂度：count 数组的大小，O(max-min+1)。

稳定性：稳定。