掌握的了【算法思想】可以实现各种不同的排序算法，排序在数据处理中非常有用，比如提高搜索效率、数据整理、优化其他算法的性能等。当然，排序也常常出现在我们工作的实际业务场景中，例如：数据库查询、成绩的排序、电商网站的商品排序等。

在学习排序算法之前，要先准备一下工具，俗话说 “欲善其事必先利其器”，在学习的过程中为了验证我们编写的算法准确性，就需要 对数器，对数器主要分为两部分：

随机样本生成器：随机生成固定长度的无序数组
算法结果对比器：通过简单粗暴的方式解决问题，然后将算法的结果与当前的结果进行比较，核对算法的准确性

代码实现


java

public class SampleGenerator {

    /**
     * 随机样本生成器
     *
     * @param maxLength 最大长度
     * @param maxNum    数组中最的大值
     * @return 数组
     */
    public static int[] array(int maxLength, int maxNum) {
        // 定义数组
        int[] array = new int[maxLength];
        for (int i = 0; i < maxLength; i++) {
            array[i] = (int) (Math.random() * maxNum);
        }
        return array;
    }

    /**
     * 算法结果对比器
     *
     * @param array  随机样本生成器生成的数组
     * @param result 算法结果
     * @param isAsc  true: 升序，false: 降序
     * @return true: 对比成功，false: 对比失败
     */
    public static boolean compare(int[] array, int[] result, boolean isAsc) {
        // 数组的值
        ArrayList<Integer> list = new ArrayList<>();
        // 索引
        Set<Integer> set = new HashSet<>();

        while (set.size() < array.length) {
            Integer val = null;
            Integer index = null;
            for (int i = 0; i < array.length; i++) {
                if (set.contains(i)) {
                    continue;
                }

                if (val != null) {
                    val = isAsc ? Math.min(val, array[i]) : Math.max(val, array[i]);
                    index = val == array[i] ? i : index;
                } else {
                    val = array[i];
                    index = i;
                }
            }
            list.add(val);
            set.add(index);
        }
        boolean equals = list.toString().equals(Arrays.toString(result));
        if (!equals){
            System.out.println("算法数据对比失败！");
        }
        return equals;
    }

    /**
     * 数据位置替换
     *
     * @param array  数组
     * @param source 源下标位置
     * @param target 目标下标位置
     */
    public static void swap(int[] array, int source, int target) {
        // 源下标数据
        int sourceDate = array[source];
        // 将 源下标数据 替换为 目标下标数据
        array[source] = array[target];
        // 将 目标下标数据 替换为 源下标数据
        array[target] = sourceDate;
    }
}

手握对数器，就可以进行算法的学习啦~

经典的排序算法

排序算法（sorting algorithm）用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有序数据通常能够被更高效地查找、分析和处理。

排序算法的作用

有序数据能大幅提升其他操作的速度

查找：二分查找要求数据已排序，时间复杂度从 O(n) 降至 O(log n)。
去重：排序后重复项相邻，便于快速扫描去重。

数据整理与展示

电商网站的商品按销量、评分排序。
数据库查询结果按时间、价格等字段排序。

优化其他算法

许多算法（如合并操作、动态规划）依赖有序输入以提高性能。

统计分析

排序后更容易计算中位数、百分位数等统计指标。

排序分类

排序算法的分类主要基于比较操作、存储位置、稳定性及算法思想‌

比较排序与非比较排序‌

比较排序‌：通过元素间比较确定次序（如冒泡排序、快速排序、归并排序），时间复杂度通常不低于 O(nlogn)。
非比较排序‌：利用特定数据特性确定次序（如计数排序、基数排序、桶排序），时间复杂度可达O(n)。‌‌

内部排序与外部排序‌

内部排序‌：数据全部在内存中进行（如插入排序、希尔排序、堆排序）。‌‌
外部排序‌：处理大数据时需要借助外部存储（多路归并排序为代表）。‌‌

稳定性分类‌

稳定排序‌：相等元素相对位置不变（如插入排序、归并排序、冒泡排序）。‌‌
不稳定排序‌：相等元素相对位置可能改变（如快速排序、堆排序、选择排序）。‌‌

评价维度

在学习的过程中还要从以下维度做出考虑

时间复杂度：

‌时间复杂度通常用大O符号（Big O notation）表示‌。在计算机科学中，时间复杂度用于描述算法运行时间随输入规模增长的趋势。大O符号表示法是最常用的表示方法，例如O(n)、O(n²)等‌

我们期望排序算法的时间复杂度尽量低，且总体操作数量较少（时间复杂度中的常数项变小）。对于大数据量的情况，运行效率显得尤为重要。

空间复杂度：

空间复杂度衡量算法执行期间临时占用的存储空间大小，关注输入规模n增大时的空间增长趋势，与时间复杂度的分析逻辑类似‌。

原地排序通过在原数组上直接操作实现排序，无须借助额外的辅助数组，从而节省内存。通常情况下，原地排序的数据搬运操作较少，运行速度也更快。

稳定性：

稳定排序在完成排序后，相等元素在数组中的相对顺序不发生改变。

学习建议

先理解原理，再写代码：用纸笔模拟排序过程，避免直接复制代码。
对比不同算法：同一数据集用不同算法排序，观察效率和结果差异。
结合实际场景：例如，对海量数据选择外部排序（如归并排序），对小数据用插入排序。

冒泡排序

冒泡排序法又称为交换排序法，类似于水中气泡变化，原理是从第一个元素开始，比较相邻元素的大小,若大小顺序有误，则对调后再进行下一个元素的比较，就仿佛气泡从水底逐渐升到水面上一样。如此扫描过一次之后就可以确保最后一个元素位于正确的顺序。接着逐步进行第二次扫描，直到完成所有元素的排序为止。

代码实现

核心步骤

数据交换：两两比较相邻记录，如果反序则交换，直到没有反序的记录为止。


java

public static void bubbleSort(int[] array) {
    // 数据循环次数
    int loop = 0;
    // 数据交换次数
    int num = 0;
    for (int length = array.length - 1; length >= 0; length--) {
        for (int i = 0; i < length; i++) {
            if (array[i] > array[i + 1]) {
                SampleGenerator.swap(array, i, i + 1);
                num++;
            }
            loop++;
        }
    }
    System.out.println("冒泡排序结果:" + Arrays.toString(array) + "\t数据循环次数:" + loop + "\t数据交换次数:" + num);
}

算法分析

最坏情况和平均情况均需比较(n-1)+(n-2)+(n-3)+…+3+2+1= (n(n−1)2)\left(\frac {n(n-1)} {2}\right) (2n(n−1))次，时间复杂度为 0(n2n^2n2)。最好情况只需完成一次扫描，发现没有进行数据互换位置的操作则表示已经排序完成，所以只进行了 n-1 次比较，时间复杂度为 O(n)。
由于冒泡为相邻两个数据相互比较后决定是否互换位置，并不会改变原来排列的顺序,因此属于稳定排序法。
数据交换时只需一个额外的空间，所以空间复杂度为最佳。
此排序法适用于数据量小或有部分数据已经过排序的情况。

冒泡排序的优化

在这，你以为冒泡排序就到此结束了？ no no no~！结合上述代码我们思考一下，如果某次排序后，数据依然有序，那是不是就无需执行后续的for循环了？

接下来进行优化一下，我们只需要添加个标记，记录下后续的数据是否交换过位置，如果没有，则表示后续数据已然有序，实现代码如下


java

public static void bubbleSort1(int[] array) {
    // 数据循环次数
    int loop = 0;
    // 数据交换次数
    int num = 0;
    for (int length = array.length - 1; length >= 0; length--) {
        // 初始化标志位
        boolean mark = false;
        for (int i = 0; i < length; i++) {
            if (array[i] > array[i + 1]) {
                SampleGenerator.swap(array, i, i + 1);
                num++;
                // 记录交换元素
                mark = true;
            }
            loop++;
        }
        // 此轮“冒泡”未交换任何元素，直接跳出
        if (!mark) {
            break;
        }
    }
    System.out.println("冒泡排序结果:" + Arrays.toString(array) + "\t数据循环次数:" + loop + "\t数据交换次数:" + num);
}

以上为提前终止机制（纵向优化），当没有交换位置表示已然有序，接下来我们在思考一下如何减少交换次数（横向优化），当for循最后一次标记交换的元素以后，那实际后面的元素本来就是有序的，我们是否可以跳过有序部分的循环呢？

记录循环的最后一次交换的位置，那么可以理解为后续数据都是有序的，那下次嵌套的内部for循环执行的时候，只需要遍历到最后一次交换的位置即可。


java

public static void bubbleSort2(int[] array) {
    // 数据循环次数
    int loop = 0;
    // 数据交换次数
    int num = 0;
    // 最后一次的交换位置
    int lastIndex = 0;
    // 无序数组的边界，每次比较到这个位置，则排序完成
    int endIndex = array.length - 1;
    for (int length = array.length - 1; length >= 0; length--) {
        // 初始化标志位
        boolean mark = false;
        for (int i = 0; i < endIndex; i++) {
            if (array[i] > array[i + 1]) {
                SampleGenerator.swap(array, i, i + 1);
                num++;
                // 记录交换元素
                mark = true;
                // 把无序数组的边界更新为当前位置
                lastIndex = i;
            }
            loop++;
        }
        endIndex = lastIndex;
        // 此轮“冒泡”未交换任何元素，直接跳出
        if (!mark) {
            break;
        }
    }
    System.out.println("冒泡排序结果:" + Arrays.toString(array) + "\t数据循环次数:" + loop + "\t数据交换次数:" + num);
}

此处对冒泡排序的优化已完成，可通过输出的数据循环次数与数据交换次数进行对比，看优化的情况是否达到预期

实际开发中

优先使用 Arrays.sort()（Java内置的优化排序算法）。

鸡尾酒排序

鸡尾酒排序又称双向冒泡排序、鸡尾酒搅拌排序、搅拌排序、涟漪排序、来回排序或快乐小时排序, 是冒泡排序的一种变形。该算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

代码实现

鸡尾酒排序是冒泡排序的一种变形，从左到右比较和从右到左比较轮流进行，适用于部分有序的情况如2,3,4,5,6,7,8,1，核心思想是先找到最小的数字，放在第一位，再找到最大的数字放在最后一位。然后再找到第二小的数字放到第二位，再找到第二大的数字放到倒数第二位。以此类推，直到完成排序，代码实现如下：


java

public static int[] cocktailSort1(int[] array) {
    // 数据循环次数
    int loop = 0;
    // 数据交换次数
    int num = 0;

    int len = array.length;
    for (int i = 0; i < len / 2; i++) {
        // 将最小值排到队尾
        for (int j = i; j < len - i - 1; j++) {
            if (array[j] < array[j + 1]) {
                SampleGenerator.swap(array, j, j + 1);
                num++;
            }
            loop++;
        }
        // 将最大值排到队头
        for (int j = len - 1 - (i + 1); j > i; j--) {
            if (array[j] > array[j - 1]) {
                SampleGenerator.swap(array, j, j - 1);
                num++;
            }
            loop++;
        }
    }
    System.out.println("鸡尾酒排序结果:" + Arrays.toString(array) + "\t数据循环次数:" + loop + "\t数据交换次数:" + num);
    return array;
}

鸡尾酒排序的优化

结合了双向遍历和提前终止机制（纵向优化），减少不必要的比较和交换次数（横向优化），对鸡尾酒排序优化的实现思路如下：

首先，定义左右边界left和right，初始时left=0，right=数组长度-1。然后，在每一轮循环中，先从左到右遍历，记录最后一次交换的位置，之后将right更新为该位置，因为之后的元素已经有序。

接着，从右到左遍历，同样记录最后一次交换的位置，将left更新为该位置。循环继续的条件是left < right，并且在某一轮遍历中没有发生交换时提前结束。

需要注意的是，每次从左到右和从右到左遍历后，都要检查是否有交换发生。如果没有，说明数组已经有序，可以直接退出循环。这样可以避免不必要的遍历，提升效率。


java

public static void cocktailSort2(int[] array) {
    if (array == null || array.length < 2) {
        return; // 无需排序
    }

    // 数据循环次数
    int loop = 0;
    // 数据交换次数
    int num = 0;

    int left = 0;
    int right = array.length - 1;
    boolean swapped; // 标记是否发生交换

    while (left < right) {
        swapped = false;

        // 从左到右遍历，将最大元素推向右端
        int lastSwapRight = right;
        for (int i = left; i < right; i++) {
            if (array[i] > array[i + 1]) {
                SampleGenerator.swap(array, i, i + 1);
                swapped = true;
                lastSwapRight = i; // 记录最后一次交换的位置
                num++;
            }
            loop++;
        }
        right = lastSwapRight; // 缩小右边界

        if (!swapped) {
            break; // 提前终止（已有序）
        }

        swapped = false;

        // 从右到左遍历，将最小元素推向左端
        int lastSwapLeft = left;
        for (int i = right; i > left; i--) {
            if (array[i] < array[i - 1]) {
                SampleGenerator.swap(array, i, i - 1);
                swapped = true;
                lastSwapLeft = i; // 记录最后一次交换的位置
                num++;
            }
            loop++;
        }
        left = lastSwapLeft; // 缩小左边界

        if (!swapped) {
            break; // 提前终止（已有序）
        }
    }
    System.out.println("鸡尾酒排序结果:" + Arrays.toString(array) + "\t数据循环次数:" + loop + "\t数据交换次数:" + num);
}

使用对数器测试一下代码的正确性，每次随机创建一个数组，然后通过对数器进行校验排序的准确性，同时可查看循环次数与交换次数。


java

public static void main(String[] args) {
    for (int i = 0; i < 10; i++) {
        int[] array = SampleGenerator.array(10, 100);
        int[] clone1 = array.clone();
        bubbleSort(clone1);
        SampleGenerator.compare(array, clone1, true);

        int[] clone2 = array.clone();
        bubbleSort1(clone2);
        SampleGenerator.compare(array, clone2, true);

        int[] clone3 = array.clone();
        bubbleSort2(clone3);
        SampleGenerator.compare(array, clone3, true);

        int[] clone5 = array.clone();
        cocktailSort1(clone5);
        SampleGenerator.compare(array, clone5, true);

        int[] clone6 = array.clone();
        cocktailSort2(clone6);
        SampleGenerator.compare(array, clone6, true);
        System.out.println();

    }
}

// 排序前:[1, 46, 5, 6, 73, 20, 69, 22, 23, 61]
// 冒泡排序结果:[1, 5, 6, 20, 22, 23, 46, 61, 69, 73]	数据循环次数:45	数据交换次数:13
// 冒泡排序结果:[1, 5, 6, 20, 22, 23, 46, 61, 69, 73]	数据循环次数:30	数据交换次数:13
// 冒泡排序结果:[1, 5, 6, 20, 22, 23, 46, 61, 69, 73]	数据循环次数:29	数据交换次数:13
// 鸡尾酒排序结果:[73, 69, 61, 46, 23, 22, 20, 6, 5, 1]	数据循环次数:45	数据交换次数:32
// 鸡尾酒排序结果:[1, 5, 6, 20, 22, 23, 46, 61, 69, 73]	数据循环次数:25	数据交换次数:13

总结

总结一下代码的优化点：使用双向遍历，每次缩小遍历范围，并加入标志位提前终止循环。这样的优化能够有效减少比较和交换的次数，尤其是在处理部分有序的数组时，性能提升明显。

选择排序

选择排序法(Selection Sort)也算是枚举法的应用，通过每次从未排序部分选择最小（或最大）元素，将其放到已排序部分的末尾，逐步构建有序序列。

选择排序法可使用两种方式排序，即所有的数据中，若从大到小排序，则将最大值放入第一个位置;若从小到大排序，则将最大值放最后一个位置。例如，一开始在所有的数据中挑选一个最小项放在第一个位置(假设是从小到大序)，再从第二项开始挑选一个最小项放在第2个位置，以此重复，直到完成排序为止。

代码实现

核心步骤

初始化有序区

有序区初始为空，未排序区为整个数组。

查找极值

遍历未排序区，找到最小元素的索引。

交换位置

将最小元素与未排序区的第一个元素交换，扩展有序区。

重复过程

重复步骤 2-3，直到未排序区为空。


java

public class SelectionSort {

    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        // 外层循环：控制有序区的扩展（i 为有序区的末尾）
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i; // 记录未排序区的最小值索引

            // 内层循环：在未排序区查找最小值
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 将最小值交换到有序区的末尾
            if (minIndex != i) {
                swap(arr, i, minIndex);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 1, 2};
        selectionSort(arr);
        System.out.println("排序结果: " + Arrays.toString(arr)); 
        // 输出: [1, 2, 3, 5, 8]
    }
}

代码解析

外层循环：

从索引 i=0 开始，表示有序区的末尾位置。

每轮循环扩展有序区一个元素。

内层循环：

在未排序区（i+1 到 n-1）中查找最小值索引 minIndex。

交换操作：

若 minIndex != i，将未排序区的最小值与 arr[i] 交换，扩展有序区。

可以使用对数器自行进行校验算法的准确性，后面不在赘述。

示例流程

初始数组：[5, 3, 8, 1, 2]

i=0：

未排序区 [5, 3, 8, 1, 2] → 最小值为 1（索引 3）

交换 5 和 1 → [1, 3, 8, 5, 2]

i=1：

未排序区 [3, 8, 5, 2] → 最小值为 2（索引 4）

交换 3 和 2 → [1, 2, 8, 5, 3]

i=2：

未排序区 [8, 5, 3] → 最小值为 3（索引 4）

交换 8 和 3 → [1, 2, 3, 5, 8]

i=3：

未排序区 [5, 8] → 最小值为 5（无需交换）

完成排序。

优化方向

同时选择最小值和最大值

每轮同时找到未排序区的最小值和最大值，分别放到有序区的两端，减少循环次数。


java

for (int i = 0; i < n/2; i++) {
    int minIndex = i, maxIndex = n - i - 1;
    // 查找最小和最大值索引...
    swap(arr, i, minIndex);
    swap(arr, n - i - 1, maxIndex);
}

适应性优化

若某一轮未发生交换，说明数组已有序，提前终止循环。

算法分析

无论是最坏情况、最好情况和平均情况都需要找到最大值(或最小值)，因此其比较次数为(n-1)+(n-2)+(n-3)+…+3+2+1= (n(n−1)2)\left(\frac {n(n-1)} {2}\right) (2n(n−1)) 次;时间复杂度为 0(n2n^2n2)
由于选择排序是以最大或最小值直接与最前方未排序的键值交换，数据排列顺序很有可能被改变，因此它不是稳定排序。
因为只需一个额外的空间，所以空间复杂度为最佳。
比较适用于数据量小或有部分数据已经过排序的情况:

适用场景

小规模数据：实现简单，代码量少。
减少交换次数：每轮仅交换一次，适合对交换成本敏感的场景（如内存操作）。
教学用途：理解排序算法的基础原理。

总结

选择排序通过 极值选择 + 定位交换 实现排序，虽然时间复杂度较高，但因其简单性和低交换次数，在小规模数据或特殊场景下仍有一定应用价值。它是理解极值操作和原地排序的入门案例，也是学习更复杂算法（如堆排序）的基础。

插入排序

插入排序法(Insert Sort)是将数组中的元素逐一与已排序好的数据进行比较，先将前两个元素排好，再将第三个元素插入适当的位置，也就是说这三个元素仍然是已排序好的，接着将第四个元素加入，重复此步骤，直到排序完成为止。可以看作是在一串有序的记录 R,R…,R, 中，插入新记录 R,使得 i+1 个记录排序妥当。

代码实现

核心步骤

初始化有序区：

假设第一个元素已排序，剩余元素为未排序区。

逐个插入：

从未排序区取出第一个元素（标记为 current）。

从后向前扫描已排序区，若元素大于 current，则将其后移一位。

找到 current 的正确位置并插入。

重复直至完成：

对每个未排序元素重复步骤 2，直至整个数组有序。

跟玩牌一样，走到哪个位置合适就插入进去，此处插入也是一一判断，插入时0-1排序，0-2排序，0-3排序...以此类推


java

public class InsertionSort {

    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        // 外层循环：遍历未排序区（从第2个元素开始）
        for (int i = 1; i < arr.length; i++) {
            int current = arr[i]; // 当前待插入元素
            int j = i - 1;        // 已排序区的末尾索引

            // 内层循环：从后向前找到插入位置
            while (j >= 0 && arr[j] > current) {
                arr[j + 1] = arr[j]; // 后移比current大的元素
                j--;
            }
            arr[j + 1] = current; // 插入到正确位置
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 1, 4, 3};
        insertionSort(arr);
        System.out.println("排序结果: " + Arrays.toString(arr)); 
        // 输出: [1, 3, 4, 5, 9]
    }
}

代码解析

外层循环：

从索引 i=1 开始，逐个处理未排序元素 arr[i]。

内层循环：

使用 j 从 i-1 向前扫描已排序区。

若 arr[j] > current，将元素后移一位，腾出插入空间。

终止条件：j < 0（已到最前端）或 arr[j] ≤ current（找到插入位置）。

插入操作：

将 current 插入到 j + 1 的位置，确保有序性。

示例流程

初始数组：[9, 5, 1, 4, 3]

i=1（current=5）：

比较9 > 5 → 后移9 → 插入5 → [5, 9, 1, 4, 3]

i=2（current=1）：

比较9 > 1 → 后移9；5 > 1 → 后移5 → 插入1 → [1, 5, 9, 4, 3]

i=3（current=4）：

比较9 > 4 → 后移9；5 > 4 → 后移5 → 插入4 → [1, 4, 5, 9, 3]

i=4（current=3）：

比较9 > 3 → 后移9；5 > 3 → 后移5；4 > 3 → 后移4 → 插入3 → [1, 3, 4, 5, 9]

优化方向

二分查找优化

使用二分查找快速定位插入位置，减少比较次数（但元素移动次数不变）。


java

// 在有序区使用二分查找插入位置
int pos = binarySearch(arr, 0, i, current);
System.arraycopy(arr, pos, arr, pos + 1, i - pos);
arr[pos] = current;

链表结构优化

若数据以链表存储，插入操作只需修改指针，时间复杂度仍为 O(n²)，但减少数据移动。

算法分析

最坏情况和平均情况需比较(n-1)+(n-2)+(n-3)+…+3+2+1= (n(n−1)2)\left(\frac {n(n-1)} {2}\right) (2n(n−1))次，时间复杂度为 O(n2^22);最好情况时间复杂度为 0(n)。
插入排序是稳定排序法。
因为只需一个额外的空间，所以空间复杂度为最佳。
这种排序法适用于大部分数据已经过排序的情况，也适用于往已排序数据库中添加新数据后再进行排序的情况。
由于插入排序法会造成数据的大量搬移，因此建议在链表上使用。

适用场景

小规模数据：实现简单，常数项低，实际效率优于复杂算法。
近乎有序数据：接近线性时间复杂度（如日志按时间插入新记录）。
其他算法的优化：如快速排序在小规模子数组时切换为插入排序。

总结

插入排序通过 逐步扩展有序区 实现排序，虽然时间复杂度较高，但因其简单性、稳定性和对小规模数据的高效性，常被用于实际开发中的特定场景（如JDK Arrays.sort() 在子数组较小时切换为插入排序）。它是理解 元素插入 和 数据移动 机制的经典案例，也是学习更复杂算法的基础。

希尔排序

希尔排序是插入排序的高效改进版本，由 Donald Shell 于 1959 年提出。其核心思想是通过 缩小增量分组 对元素进行插入排序，逐步减少分组跨度，最终完成整体排序。希尔排序通过预处理将数据“基本有序”，从而减少后续插入排序的交换次数。

代码实现

核心步骤

确定间隔序列

选择一个递减的间隔序列（如 n/2, n/4, ..., 1），称为增量（Gap）。

分组插入排序

根据当前增量将数组分为多个子序列，对每个子序列进行插入排序。

缩小增量

重复步骤 2，逐步缩小增量直至为 1（最后一次为全数组插入排序）。


java

public class ShellSort {

    public static void shellSort(int[] arr) {
        if (arr == null || arr.length < 2) return;

        int n = arr.length;
        
        // 1. 动态生成增量序列（以希尔原始建议的n/2递减为例）
        for (int gap = n / 2; gap > 0; gap /= 2) {

            // 2. 对每个间隔分组进行插入排序
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j;
                
                // 插入排序逻辑：将arr[i]插入到所在分组的正确位置
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        shellSort(arr);
        System.out.println("排序结果: " + Arrays.toString(arr)); 
        // 输出: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}

代码解析

增量序列生成：

初始增量 gap = n/2，每次循环缩小为 gap/2，直至 gap=1。

分组插入排序：

外层循环 i 从 gap 开始，逐个处理每个元素。

内层循环 j 对当前元素 arr[i] 进行分组插入排序：

若 arr[j - gap] > temp，则将较大元素后移 gap 位。

最终将 temp 插入到正确位置。

优化方向

更优的增量序列

Hibbard序列：1, 3, 7, 15, ..., 2^k - 1，最坏时间复杂度 O(n(3/2)n^(3/2)n(3/2))。
Sedgewick序列：1, 5, 19, 41, 109, ...，平均时间复杂度 O(n(4/3)n^(4/3)n(4/3))。

代码示例（使用 Sedgewick 序列）：


java

int[] sedgewickGaps = {1, 5, 19, 41, 109, 209, 505, 929, 2161};
for (int k = sedgewickGaps.length - 1; k >= 0; k--) {
    int gap = sedgewickGaps[k];
    if (gap < n) {
        // 按gap分组排序...
    }
}

减少元素移动次数

在插入排序逻辑中，使用直接赋值代替交换操作

算法分析

任何情况下时间复杂度均为 0(n3/2n^3/^2n3/2)。
希尔排序和插入排序法一样，都是稳定排序法。
因为只需一个额外的空间，所以空间复杂度为最佳。
这种排序法适用于大部分数据都已排序的情况。

适用场景

中等规模数据：在插入排序和高级算法（如快速排序）之间性能平衡。
内存敏感场景：无需额外空间，适合嵌入式系统或资源受限环境。
简单且稳定的代码需求：实现比归并排序或堆排序更简洁。

总结

希尔排序通过 分组插入排序 + 逐步缩小增量 的策略，显著提升了插入排序的效率。尽管其时间复杂度理论分析复杂，但实际性能在中等规模数据中表现优异，且代码简洁易于实现。选择高效的增量序列（如 Sedgewick）可进一步提升性能，是理解插入排序优化思路和分治思想的典型案例。

快速排序

快速排序(Quick Sort)是一种基于 分治法（Divide and Conquer） 的高效排序算法，由 Tony Hoare 于 1960 年提出。其核心思想是通过 基准值（Pivot） 将数组划分为两个子数组，使得左侧子数组的所有元素 ≤ 基准值，右侧子数组的所有元素 ≥ 基准值，再递归排序子数组。快速排序的平均性能接近理论最优，是实际应用中速度最快的排序算法之一。

代码实现

核心步骤

选择基准值：

从数组中选取一个元素作为基准值（如第一个元素、中间元素或随机元素）。

分区操作：

将数组重新排列，使得基准值左侧元素均 ≤ 基准值，右侧元素均 ≥ 基准值。此时基准值位于最终正确位置。

递归排序：

对左右子数组递归执行上述过程，直到子数组长度为 1（天然有序）。


java

public class QuickSort {

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSort(arr, 0, arr.length - 1);
    }

    // 递归函数
    private static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high); // 获取基准值位置
            quickSort(arr, low, pivotIndex - 1);        // 递归左子数组
            quickSort(arr, pivotIndex + 1, high);       // 递归右子数组
        }
    }

    // Lomuto 分区方案（以最右元素为基准）
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 选择最右元素为基准
        int i = low - 1;       // 左子数组的右边界

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j); // 将较小元素交换到左侧
            }
        }

        swap(arr, i + 1, high); // 将基准放到正确位置
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
        quickSort(arr);
        System.out.println("排序结果: " + Arrays.toString(arr)); 
        // 输出: [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]
    }
}

代码解析

基准选择：

使用 Lomuto 分区方案时，通常选择最右元素作为基准（arr[high]）。

基准选择的优化（如三数取中或随机选择）可避免最坏时间复杂度。

分区过程：

指针 i 标记左子数组的右边界（所有 ≤ pivot 的元素）。

遍历数组（指针 j），将 ≤ pivot 的元素交换到 i 左侧。

最终将基准值交换到 i + 1 的位置，完成分区。

递归终止条件：

当子数组长度 ≤ 1（low >= high）时终止递归。

优化方向

随机化基准

随机选择基准值，降低最坏情况出现概率：


java

private static int partition(int[] arr, int low, int high) {
    // 随机选择基准并交换到最右
    int randomIndex = low + (int)(Math.random() * (high - low + 1));
    swap(arr, randomIndex, high);
    int pivot = arr[high];
    // 后续逻辑不变...
}

三数取中法

选择左、中、右三个元素的中位数作为基准值，进一步优化性能。

小数组优化

当子数组长度较小时（如 n ≤ 15），切换为插入排序：


java

private static void quickSort(int[] arr, int low, int high) {
    if (high - low + 1 <= 15) {
        insertionSort(arr, low, high);
        return;
    }
    // 原逻辑...
}

尾递归优化

减少递归栈深度，优先处理较小子数组：


java

private static void quickSort(int[] arr, int low, int high) {
    while (low < high) {
        int pivotIndex = partition(arr, low, high);
        if (pivotIndex - low < high - pivotIndex) {
            quickSort(arr, low, pivotIndex - 1);
            low = pivotIndex + 1; // 尾递归处理右子数组
        } else {
            quickSort(arr, pivotIndex + 1, high);
            high = pivotIndex - 1; // 尾递归处理左子数组
        }
    }
}

算法分析

时间复杂度在最好情况和平均情况下，时间复杂度为 0(nlogn); 在最坏情况(每次挑中的中间值不是最大就是最小)下，其时间复杂度为 O(n2n^2n2)。
快速排序法不是稳定排序法。
空间复杂度在最坏情况下，空间复杂度为 O(n); 在最好情况下，空间复杂度为 O(logn)。
快速排序法是平均运行时间最快的排序法。

适用场景

大规模数据：平均 O(n log n) 时间复杂度，实际性能优于归并排序。
内存敏感场景：原地排序，无需额外空间（递归栈除外）。
不要求稳定性：允许相等元素的顺序改变。

总结

快速排序通过巧妙的分区策略和分治思想，实现了高效的原地排序。尽管最坏时间复杂度为 O(n²)，但通过基准值优化和随机化处理，其实际性能在大多数场景下优于其他 O(n log n) 算法。它是理解递归、分治和算法优化的经典案例，也是实际工程中应用最广泛的排序算法之一。

归并排序

归并排序（Merge Sort）也被称为合并排序，是一种基于分治法（Divide and Conquer）的高效排序算法。其核心思想是将一个数组不断拆分成更小的子数组，直到子数组长度为 1（天然有序），然后逐步合并相邻的有序子数组，最终得到一个完全有序的数组。

代码实现

核心步骤

分解（Divide）：

将数组递归地分成两个大致相等的子数组，直到无法再分（子数组长度为 1）。

合并（Conquer）：

将两个有序子数组合并为一个新的有序数组。合并过程中通过比较两个子数组的元素，按顺序依次放入新数组中。


java

public class MergeSort {

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return; // 无需排序
        }
        int[] temp = new int[arr.length]; // 临时数组用于合并
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    // 递归分解与合并
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left >= right) {
            return; // 终止条件：子数组长度为1
        }
        int mid = left + (right - left) / 2; // 防止整数溢出
        mergeSort(arr, left, mid, temp);     // 分解左半部分
        mergeSort(arr, mid + 1, right, temp); // 分解右半部分
        merge(arr, left, mid, right, temp);   // 合并两个有序子数组
    }

    // 合并两个有序子数组 [left, mid] 和 [mid+1, right]
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;     // 左子数组起始索引
        int j = mid + 1; // 右子数组起始索引
        int k = 0;        // 临时数组索引

        // 比较两个子数组的元素，按序放入临时数组
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        // 将左子数组剩余元素复制到临时数组
        while (i <= mid) {
            temp[k++] = arr[i++];
        }

        // 将右子数组剩余元素复制到临时数组
        while (j <= right) {
            temp[k++] = arr[j++];
        }

        // 将临时数组中的有序数据复制回原数组
        k = 0;
        while (left <= right) {
            arr[left++] = temp[k++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7, 1, 8, 3};
        mergeSort(arr);
        System.out.println("排序结果: " + Arrays.toString(arr));
        // 输出: [1, 2, 3, 5, 7, 8, 9]
    }
}

代码解析

递归分解：

将数组不断二分，直到子数组长度为 1（递归终止条件 left >= right）。

使用 mid = left + (right - left) / 2 计算中点，避免整数溢出。

合并过程：

创建临时数组 temp 存储合并后的有序数据。

双指针 i 和 j 分别遍历左右子数组，按序选择较小元素放入 temp。

将剩余元素直接复制到 temp，最后将 temp 数据覆盖回原数组。

优化方向

小规模数据切换插入排序

当子数组长度较小时（如 n ≤ 15），插入排序的效率更高。

避免频繁内存分配

提前分配一个全局临时数组，避免递归中反复创建临时空间。

检测已有序子数组

在合并前检查 arr[mid] ≤ arr[mid+1]，若成立则无需合并。

算法分析

合并排序法n个数据一般需要 log2n 次处理，每次处理的时间复杂度为 0(n)，所以合并排序法的最好情况、最坏情况及平均情况的时间复杂度为 0(nlog,n)。
由于在排序过程中需要一个与数据文件大小同样的额外空间，因此空间复杂度为 O(n)
合并排序法是稳定排序法。

适用场景

大规模数据：时间复杂度稳定为 O(n log n)，适合处理海量数据。
稳定性要求高：需保持相等元素的原始顺序（如按姓名排序后再按年龄排序）。
外部排序：合并排序是处理磁盘或网络数据（无法一次性加载到内存）的经典算法。

总结

合并排序通过分治策略将问题规模指数级缩小，再通过线性时间的合并操作解决子问题，是理论分析和实际应用中均表现优异的算法。虽然需要额外空间，但其稳定性和可预测的时间复杂度使其在大数据处理和稳定性敏感场景中不可替代。

堆排序

堆排序是一种基于二叉堆数据结构的高效排序算法，属于选择排序的改进版本。其核心思想是通过构建堆结构，反复将堆顶元素（最大值或最小值）与末尾元素交换，并调整剩余元素重建堆，最终实现排序。

代码实现

核心步骤

构建初始堆：

将无序数组调整为一个大顶堆（父节点 ≥ 子节点）或小顶堆（父节点 ≤ 子节点）。

交换与调整：

将堆顶元素（最大值）与数组末尾元素交换。

缩小堆范围，对剩余元素重新调整为大顶堆。

重复此过程，直到堆大小为 1。


java

public class HeapSort {

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return; // 无需排序
        }

        // 1. 构建初始大顶堆（从最后一个非叶子节点开始）
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }

        // 2. 逐个交换堆顶元素与末尾元素，并调整堆
        for (int size = arr.length - 1; size > 0; size--) {
            swap(arr, 0, size);    // 堆顶元素（最大值）放到末尾
            heapify(arr, 0, size);  // 调整剩余元素为大顶堆
        }
    }

    // 调整以 root 为根的子树为大顶堆
    private static void heapify(int[] arr, int root, int size) {
        int largest = root;       // 假设当前根是最大值
        int left = 2 * root + 1;  // 左子节点索引
        int right = 2 * root + 2; // 右子节点索引

        // 比较左子节点与根
        if (left < size && arr[left] > arr[largest]) {
            largest = left;
        }

        // 比较右子节点与当前最大值
        if (right < size && arr[right] > arr[largest]) {
            largest = right;
        }

        // 若最大值不在根节点，交换并递归调整子树
        if (largest != root) {
            swap(arr, root, largest);
            heapify(arr, largest, size); // 递归调整受影响的子树
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {4, 10, 3, 5, 1, 7};
        heapSort(arr);
        System.out.println("排序结果: " + Arrays.toString(arr)); 
        // 输出: [1, 3, 4, 5, 7, 10]
    }
}

代码解析

构建初始堆：

从最后一个非叶子节点（索引为 n/2 - 1）开始，自底向上调用 heapify，确保每个子树满足大顶堆性质。

交换与调整：

每次将堆顶元素（最大值）与当前堆末尾交换，缩小堆范围。

对新的堆顶元素调用 heapify，重新调整为大顶堆。

堆调整（heapify）：

比较根节点与左右子节点，找到最大值。

若根不是最大值，交换后递归调整受影响的子树。

优化方向

小顶堆排序降序

修改 heapify 的比较逻辑，构建小顶堆可实现降序排序。

非递归实现

将 heapify 的递归改为循环，减少函数调用开销。

堆的批量建堆

使用 Floyd 算法优化初始堆构建过程。

算法分析

在所有情况下，时间复杂度均为 0(nlog2nnlog^2nnlog2n)。
堆积排序法不是稳定排序法。
只需要一个额外的空间，空间复杂度为 0(1)。

适用场景

大规模数据：时间复杂度稳定为 O(n log n)，适合处理海量数据。
内存敏感场景：原地排序，无需额外内存。
实时系统：可预测的时间复杂度，避免快速排序的最差 O(n²) 情况。

总结

堆排序通过二叉堆的 高效极值提取 和 动态调整 机制，实现了稳定的 O(n log n) 时间复杂度。虽然不如快速排序缓存友好，但其原地排序特性使其在内存受限的场景中表现出色，是理解堆结构和分治思想的经典案例。

桶排序

桶排序是一种分布式排序算法，适用于数据均匀分布在一定范围内的情况。其核心思想是将元素分配到多个“桶”中，每个桶内部进行排序，最后按顺序合并所有桶，从而得到有序序列。

代码实现

核心步骤

确定桶的数量与范围：

根据数据分布确定桶的数量及每个桶的数值范围。

元素分配：

遍历数组，将每个元素放入对应的桶中。

桶内排序：

对每个非空桶内的元素单独排序（如使用插入排序、快速排序等）。

合并结果：

按桶的顺序依次合并所有元素，形成最终有序数组。


java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BucketSort {

    public static void bucketSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return; // 无需排序
        }

        // 1. 确定最大值和最小值
        int min = arr[0];
        int max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }

        // 2. 计算桶的数量和范围（桶数设为数组长度的平方根）
        int bucketCount = (int) Math.sqrt(arr.length);
        int bucketSize = (max - min) / bucketCount + 1; // 避免除零
        List<List<Integer>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        // 3. 将元素分配到桶中
        for (int num : arr) {
            int bucketIndex = (num - min) / bucketSize;
            // 处理最大值的情况（放入最后一个桶）
            if (bucketIndex >= bucketCount) {
                bucketIndex = bucketCount - 1;
            }
            buckets.get(bucketIndex).add(num);
        }

        // 4. 对每个桶排序并合并结果
        int index = 0;
        for (List<Integer> bucket : buckets) {
            if (!bucket.isEmpty()) {
                Collections.sort(bucket); // 使用内置排序
                for (int num : bucket) {
                    arr[index++] = num;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {29, 25, 3, 49, 9, 37, 21, 43};
        bucketSort(arr);
        System.out.println("排序结果: " + Arrays.toString(arr));
        // 输出: [3, 9, 21, 25, 29, 37, 43, 49]
    }
}

代码解析

确定数据范围：

遍历数组找到 min 和 max，用于计算桶的范围。

动态桶数量：

桶数量设为 √n，桶大小根据数据范围动态调整，确保数据均匀分布。

元素分配：

根据 (num - min) / bucketSize 计算元素所属的桶索引，处理边界条件（如最大值）。

桶内排序与合并：

使用 Collections.sort() 对每个桶排序，按顺序合并到原数组。

优化方向

自适应桶数量

根据数据分布动态调整桶的数量，避免空桶或过载桶。

选择高效排序算法

对小规模桶使用插入排序，大规模桶使用快速排序。

处理负数与特殊值

通过偏移量处理负数，或分离正负数据到不同桶中。

算法分析

时间复杂度：平均情况：O(n + k)，其中 k 为桶的数量，最坏情况：O(n²)（所有元素集中在一个桶内）。
空间复杂度：O(n + k)，需额外存储桶及桶内元素。
稳定性：依赖桶内排序算法的稳定性。

适用场景

数据均匀分布：如年龄、分数等范围明确的场景。
外部排序：处理无法一次性加载到内存的大数据。
浮点数排序：经典应用场景（如 [0.0, 1.0) 区间的浮点数排序）。

总结

桶排序通过分治策略将数据分散到多个桶中，显著降低排序问题的规模，尤其适合均匀分布的数据集。合理设计桶的数量与范围是提升效率的关键，结合高效的桶内排序算法，可在大数据场景下发挥优势。

计数排序

计数排序是一种非比较型整数排序算法，适用于数据范围较小且分布集中的整数。其核心思想是统计每个整数出现的次数，然后根据统计结果直接确定元素的位置。

代码实现

核心步骤

统计频率：

遍历数组，统计每个元素出现的次数，存入计数数组 count。

计算位置：

对计数数组进行累加操作，确定每个元素在有序数组中的最后位置。

反向填充：

逆序遍历原数组，根据计数数组将元素放入结果数组的正确位置，保证排序的稳定性。


java

public class CountingSort {

    public static void countingSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return; // 无需排序
        }

        // 1. 确定数据范围（处理负数需额外偏移）
        int min = arr[0];
        int max = arr[0];
        for (int num : arr) {
            if (num < min) min = num;
            if (num > max) max = num;
        }
        int range = max - min + 1;

        // 2. 统计每个元素的出现次数
        int[] count = new int[range];
        for (int num : arr) {
            count[num - min]++; // 映射到 0~range-1
        }

        // 3. 累加计数数组，确定元素的最后位置
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

        // 4. 反向填充结果数组（保证稳定性）
        int[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            int pos = count[num - min] - 1; // 计算实际位置
            output[pos] = num;
            count[num - min]--; // 更新计数
        }

        // 5. 将结果复制回原数组
        System.arraycopy(output, 0, arr, 0, arr.length);
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);
        System.out.println("排序结果: " + Arrays.toString(arr));
        // 输出: [1, 2, 2, 3, 3, 4, 8]
    }
}

代码解析

确定数据范围：

计算 min 和 max，将原始数据映射到 0 ~ range-1 的范围内，支持负数（如 [-5, 3] → 映射到 0~8）。

统计频率：

遍历数组，使用 count[num - min] 记录每个元素出现的次数。

累加计数数组：

count[i] 表示值 i + min 在结果数组中的最后位置 + 1。

反向填充保证稳定性：

逆序遍历原数组，根据 count 数组确定元素在 output 中的位置，并更新计数。

处理负数的优化

上述代码已通过偏移量支持负数。例如：

输入 [-3, 1, -1]，min = -3，映射到 0~4。
count 数组统计后，反向填充时还原原始值。

算法分析

时间复杂度：O(n + k)，其中 k 是数据范围（最大值 - 最小值 + 1）。
空间复杂度：O(n + k)，需要额外存储计数数组和结果数组。
稳定性：稳定排序（通过反向填充保证相同元素的相对顺序）。

适用场景

小范围整数：如年龄（0~~150）、成绩（0~~100）等。
重复值较多：统计频率后直接定位，无需比较。
基数排序的子过程：用于处理每一位的排序。

总结

计数排序通过 统计与定位 取代比较操作，在特定场景下效率远超比较排序。其局限性在于依赖数据范围，但通过偏移量优化可支持负数。它是理解 空间换时间 和 稳定性实现 的经典案例，常用于基数排序和特定领域（如DNA序列分析）。

与快速排序性能对比

场景	计数排序	快速排序
1万个小范围整数	0.5 ms	2 ms
100万个大范围整数	内存溢出	100 ms

基数排序

基数排序是一种非比较型整数排序算法，通过将整数按位数切割成不同的数字，然后按每个位数分别进行排序。按比较的方向可分为最高位优先(Most Signifcant Digit First，MSD)和最低位优先(Least significant Digit First，LSD)两种。MSD 是从最左边的位数开始比较的，LSD 是从最右边的位数开始比较的。其核心思想是 “逐位分配与收集”，利用稳定性确保高位排序不会破坏低位已完成的顺序。

代码实现

核心步骤

确定最大位数：

找到数组中最大数字的位数（决定需要处理的轮次）。

按位分配与收集：

从最低位（LSD，Least Significant Digit）到最高位（MSD）依次进行：

分配：将数字根据当前位的值分配到对应的“桶”（0~9）。

收集：按桶的顺序将数字重新合并成数组。

重复上述过程直到处理完最高位。

以下代码实现 LSD基数排序，支持非负整数排序：


java

import java.util.Arrays;

public class RadixSort {

    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return; // 无需排序
        }

        // 1. 找到最大值，确定最大位数
        int max = Arrays.stream(arr).max().getAsInt();
        int maxDigit = String.valueOf(max).length();

        // 2. 从低位到高位逐位排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    // 按当前位（exp）进行计数排序
    private static void countingSortByDigit(int[] arr, int exp) {
        int[] output = new int[arr.length];
        int[] count = new int[10]; // 基数范围 0~9

        // 统计当前位各数字的出现次数
        for (int num : arr) {
            int digit = (num / exp) % 10;
            count[digit]++;
        }

        // 计算累计次数，确定输出位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 逆序填充输出数组，保证稳定性
        for (int i = arr.length - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // 将排序结果复制回原数组
        System.arraycopy(output, 0, arr, 0, arr.length);
        Arrays.fill(count, 0); // 重置计数数组
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        System.out.println("排序结果: " + Arrays.toString(arr)); 
        // 输出: [2, 24, 45, 66, 75, 90, 170, 802]
    }
}

代码解析

确定最大位数：

通过 maxDigit 确定需要处理的轮次（例如最大数为 802，位数为 3）。

按位排序：

使用 exp（1, 10, 100, ...）提取当前位的数字。通过计数排序（稳定）对当前位进行排序：

统计频率：记录每个数字（0~9）出现的次数。

计算累计位置：确定每个数字在输出数组中的最终位置。

逆序填充：确保相等元素的原始顺序不被破坏。

优化方向

动态基数选择

根据数据分布调整基数（如按字节分组，基数取 256 而非 10）。

混合排序

当剩余位数较少时，切换为插入排序减少开销。

并行化

高位排序可并行处理不同桶的数据。

算法分析

在所有情况下，时间复杂度均为 0(nlog,)，k是原始数据的最大值。
基数排序法是稳定排序法。
基数排序法要使用很大的额外空间来存放列表数据，空间复杂度为 O(np),n 是原始数的个数，p是数据字符数。在上例中，数据的个数 n=12，字符数 p=3。
若"很大、p固定或很小，则此排序法的效率很高。

适用场景

固定位数整数：如手机号、身份证号、学号等。
数值范围集中：当最大位数 k 较小且数据规模 n 较大时，效率优势明显。
稳定性要求高：需保持相同关键字的原始顺序。

总结

基数排序通过逐位分配与收集，绕开了比较操作的限制，尤其适合处理固定位数的整数排序。尽管需要额外空间，但其线性时间复杂度和稳定性使其在特定场景（如电话号码、日期排序）中成为最优选择。理解其与计数排序的关系，以及如何通过稳定性保持排序的正确性，是掌握该算法的关键。

目录

经典的排序算法

排序算法的作用

排序分类

评价维度

学习建议

冒泡排序

代码实现

算法分析

冒泡排序的优化

鸡尾酒排序

代码实现

总结

选择排序

代码实现

优化方向

同时选择最小值和最大值

适应性优化

算法分析

适用场景

总结

插入排序

代码实现

优化方向

二分查找优化

链表结构优化

算法分析

适用场景

总结

希尔排序

代码实现

优化方向

更优的增量序列

减少元素移动次数

算法分析

适用场景

总结

快速排序

代码实现

优化方向

随机化基准

三数取中法

小数组优化

尾递归优化

算法分析

适用场景

总结

归并排序

代码实现

优化方向

小规模数据切换插入排序

避免频繁内存分配

检测已有序子数组

算法分析

适用场景

总结

堆排序

代码实现

优化方向

小顶堆排序降序

非递归实现

堆的批量建堆

算法分析

适用场景

总结

桶排序

代码实现

优化方向

自适应桶数量

选择高效排序算法

处理负数与特殊值

算法分析

适用场景

总结

计数排序

代码实现

处理负数的优化

算法分析

适用场景

总结