数据结构——排序（二）

Han.miracle

发布于 2025-12-22 13:55:50

290

文章被收录于专栏：Java核心技术图谱：原理·对比·避坑Java核心技术图谱：原理·对比·避坑

2.3 交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的⽐较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较⼤的记录向序列的尾部移动，键值较⼩的记录向序列的前部移动。

2.3.1 冒泡排序

 /**
     * 冒泡排序：
     * 时间复杂度：O(N^2)
     *          加上优化之后，最好情况下-》O(N)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     * @param array
     */
    public static void bubbleSort(int[] array) {
        //i趟数
        for (int i = 0; i < array.length-1; i++) {
            //
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]){
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            if(!flg){
                break;
            }
        }
    }
private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

冒泡排序是⼀种非常容易理解的排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定 2.3.2 快速排序快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左⼦序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到

2.3 快速排序

快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

/**
     * 快速排序
     * 时间复杂度：  最坏(有序/逆序)：O(n^2)   最好：O(N*logN)
     * 空间复杂度：   最坏：O(N)   最好: O(logN)
     * 稳定性：不稳定
     * @param array
     */
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }

        if(end-start+1 <= 15) {
            insertSort(array,start,end);
            return;
        }

        //三数取中
        int index = mid_three(array,start,end);
        swap(array,index,start);

        int pivot = partition(array,start,end);

        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }

// 假设按照升序对array数组中[left, right)区间中的元素进⾏排序
 
void QuickSort(int[] array, int left, int right) {
 if(right - left <= 1)
 return;
 // 按照基准值对array数组的[left, right)区间中的元素进⾏划分
 
int div = partion(array, left, right);
 QuickSort(array, left, div);
 }
 // 划分成功后以div为边界形成了左右两部分 [left, div) 和[div+1, right) 
// 递归排[left, div) 
// 递归排[div+1, right) 
QuickSort(array, div+1, right);

1.Hoare 版

左哨兵：是找到比第一个的值(6)也就做基准值小的数，就停到这个数字这(7)，然后与右哨兵找到的交换位置，左哨兵接着走，继续找到比第一个大的数，一直按着这个规则，直到俩人相遇结束。相遇点记作：pivot ， 基准值跟相遇点的值换，但是看这个划分的话不是很有序，从这个相遇的这个点(3),就把3的左边的接着按着这个规则寻找，又相遇了接着按着这个规则，直到左右哨兵起点是同一个结束。

右哨兵：是从后往前找是找到比基准值（6）小的数，就停到这个数字这(3)，然后与左哨兵找到的交换位置(左右交换一次就行，我只是写下来了)，右哨兵接着走，继续找到比6小的数，一直按着这个规则，直到俩人相遇结束。后面跟左子树是一样的 简洁来说：

选择基准（Pivot）：从数组中选取一个元素作为 “基准”（通常选第一个、最后一个或中间元素）。

分区（Partition）：通过 Hoare 划分法，将数组重新排列为两部分：

左侧元素均小于等于基准；
右侧元素均大于等于基准；
基准元素最终落在正确的位置（左右分区的分界点）。
左侧≤基准，右侧≥基准，把这个交换到最前面然后在他的左边在进行排序

递归排序：对基准左侧和右侧的子数组分别重复上述步骤，直至子数组长度为 1 或 0（自然有序）。

这个有点像二叉树，左边只有左子树，右边只有右子树下标分为两种情况：第一次相遇的左边： L:0 起点 R:pivot-1 第一次相遇的右边： L:pivot +1 R : array.length -1 那为什么从后往前？ 准值的初始位置（第一个或最后一个元素）会决定指针的初始移动方向，其核心逻辑是一致的：通过调整指针移动顺序，确保最终相遇点的元素性质与基准值的初始位置匹配，从而在交换后将基准值正确放置在分区的分界点。说白了就是我们是以第一个数为准基值，我们先找比他小的，如果相遇这个值一定是班比他小的，然后他俩交换位置，反之，我们将最后一个数为准基值，我们就从前往后，找比它大的，交换，最后找到的值是比这个准基值大的，然后进行交换再用更直白的话补充两句：

当基准值在左边（第一个元素）时，我们的目标是 “在右边找一个比它小的元素”，让右指针先出发去 “捞”这个小元素。当指针相遇时，这个位置一定藏着一个 “该在左边” 的小元素，和基准值交换后，基准值左边就都是小的，右边都是大的。
当基准值在右边（最后一个元素）时，目标就变成 “在左边找一个比它大的元素”，让左指针先出发去 “捞” 这个大元素。相遇时的位置一定藏着一个 “该在右边” 的大元素，交换后，基准值右边就都是大的，左边都是小的。

为什么 array[right] >= tmp是>= 与 array[left] <= tmp要写< >？

右指针（right）：从后往前移，寻找 “应该放在左侧” 的元素（即 ≤ 基准值 tmp 的元素），找左侧的元素就是比准基值小的，所以array[right] 找比准基值小的停下来，进行交换换来的就是比准基值大的数
左指针（left）：从前往后移，寻找 “应该放在右侧” 的元素（即 ≥ 基准值 tmp 的元素）找右侧的元素就是比准基值大的，所以array[left] 找比准基值大的停下来，进行交换换来的就是比准基值小的数 = 存在的原因是： 如果左右两边的值是一样的，那就是啥也没有交换

既然他是不完整的子树，我们需不需要限制它呢？比如左边的子树的子树没有右边的子树”（即某个左分区的子分区只有左子数组、没有右子数组）是正常现象，本质上是由数组元素的分布和基准值的选择决定的，并不需要刻意 “限制”—— 因为快速排序的递归逻辑本身就通过 “终止条件” 自然处理了这种情况。终止条件是：当子数组长度≤1 时，不再对其进行分区

    /**
     * 划分待排序的序列
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition1(int[] array, int left, int right) {
        int i = left;
        int tmp = array[left];
        while (left < right) {
        //= 存在的原因是：**
 //如果左右两边的值是一样的，那就是啥也没有交换
            while (left < right && array[right] >= tmp) {
                right--;
            }

            while (left < right && array[left] <= tmp) {
                left++;
            }

            swap(array,left,right);
        }
//将基准值与相遇点交换，让基准值回到他应该在的位置
        swap(array,left,i);
        return left;
    }

2.挖坑法

挖坑法单趟排序动图

注：此图借鉴博主是此链接的https://blog.csdn.net/gfdxx/article/details/126826128 选择基准值 以数组左侧第一个元素为基准值（tmp = array[left]），目标是将数组中所有 ≤ tmp 的元素移到左侧，≥ tmp 的元素移到右侧。 2. 双向指针移动与元素覆盖 使用 left（左指针）和 right（右指针）从数组两端向中间逼近，通过覆盖操作逐步划分区域：

第一步：右指针左移（找≤基准的元素）

while (left < right && array[right] >= tmp) {
    right--; // 右指针左移，跳过所有≥基准的元素
}
array[left] = array[right]; // 将找到的≤基准的元素放到左指针位置

右指针从最右侧出发，不断左移，直到找到第一个小于等于基准值的元素，然后将该元素 “搬运” 到左指针当前位置（此时左指针位置的原始值已被存为 tmp，不会丢失）。

第二步：左指针右移（找≥基准的元素）

while (left < right && array[left] <= tmp) {
    left++; // 左指针右移，跳过所有≤基准的元素
}
array[right] = array[left]; // 将找到的≥基准的元素放到右指针位置

左指针从左侧出发（已被覆盖为右指针找到的元素），不断右移，直到找到第一个大于等于基准值的元素，然后将该元素 “搬运” 到右指针当前位置。 循环重复：上述两步不断交替，直到 left == right（左右指针相遇），此时数组已被划分为两部分（左侧≤基准，右侧≥基准）。 3. 基准值归位 当 left == right 时，相遇位置就是基准值 tmp 在排序后应处的位置，将 tmp 放入该位置：

array[left] = tmp;
return left; // 返回基准值的最终位置，用于后续递归划分左右子数组

代码如下：

* 快速排序
     * 时间复杂度：  最坏(有序/逆序)：O(n^2)   最好：O(N*logN)
     * 空间复杂度：   最坏：O(N)   最好: O(logN)
     * 稳定性：不稳定
  private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];

            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

该方法存在缺陷：

1、递归层数过多有爆栈风险 2、面对有序或者接近有序的待排序数据，时间复杂度就变成了O()

所以需要作如下优化：

1.4三数取中，优化选key 1、随机选key（听着很随机，虽然不靠谱，但有的场景还是可以使用随即选key的方法）

2、针对有序情况，选正中间数据做key（前提是知道有序）

3、三数取中（选出左中右三数中间大小的做key）（三数取中后，对于缺陷2，直接由最坏情况变成最好情况）

3.前后指针法

注：声明这个图还是借鉴博主是此链接的https://blog.csdn.net/gfdxx/article/details/126826128

判断cur 指针指向的数据是否小于key,若小于，则prev 指针后移一位，并则cur 指向的内容与prev 指向的内容交换，然后cur的指针++
此时cur 指针指向的数据大于key, 则cur指针继续++
在比较，cur 指针指向的数据还是小于key prev 先后移动一位，然后与cur 指向的数据交换
又一次比较，cur 指针指向的数据还是小于key，prev 先后移动一位，然后与cur指向的数据交换，cur 再++

 // 递归排序方法
    private static void quickSortRecursive(int[] array, int left, int right) {
        // 终止条件：当子数组范围无效（left >= right）时，停止递归
        if (left >= right) {
            return;
        }
        // 调用 partition3 进行分区，获取基准值的最终位置
        int pivotPos = partition3(array, left, right);
        // 递归排序基准值左侧子数组（left 到 pivotPos - 1）
        quickSortRecursive(array, left, pivotPos - 1);
        // 递归排序基准值右侧子数组（pivotPos + 1 到 right）
        quickSortRecursive(array, pivotPos + 1, right);
    }

 private static int partition3(int[] array, int left, int right) {
        int prev = left ;
        int cur = left+1;
        //防止cur越界超出范围
        while (cur <= right) {
          //cur 寻找比基准值小的数停下来
        //prev找到了prev+1 
        //prev 与 cur 之间一定都是比他大的数，然后交换即可
      
        //array[++prev] != array[cur]   然后交换
//array[++prev] != array[cur])相等的话有可能就是循环了
            if(array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,left);
        //此时prev 在与left交换
        return prev;
    }

那这三种方法搞出来的排序一般都是不一样的，如果出选择题优先用挖坑法，Hoare , 前后指针法，一般会以挖坑法去考察你，

4.优化快速排序

三数取中法选key
递归到小的子区间时，可以考虑使用插入排序可以直接在idea help里直接改栈大小：-Xss

优化快速排序的核心目的是提升其在实际场景中的稳定性和效率

1.避免极端情况导致性能退化

理想情况：基准元素能将数组均匀分割为两半，递归层数为 log n，时间复杂度为 O(n log n)。
极端情况：若基准元素是当前区间的最大值或最小值（例如对已排序数组选择第一个元素作为基准），会导致分割极不均匀（一边为空，另一边为原区间长度
1），递归层数退化为 n，时间复杂度退化到 O(n²)。 2.提升对小规模数据的处理效率快速排序的递归特性在处理小规模数据（如长度小于 10~20 的数组）时，效率不如插入排序等简单排序算法：
快速排序的递归调用本身有额外开销（函数调用、栈操作等）。
小规模数据的分割收益有限，反而可能被递归开销抵消。
处理重复元素较多的数组当数组中存在大量重复元素时，未优化的快速排序可能出现以下问题：
若基准元素是重复值，可能导致分割失衡（例如所有元素都等于基准，左右区间几乎未分割）。
递归层数增加，时间复杂度接近 O(n²)。 4 减少递归栈溢出风险
快速排序的递归深度在最坏情况下为 O(n)（如极端基准选择），可能导致栈溢出（尤其是对大数组）。
适应现代计算机体系结构 5.未优化的快速排序可能存在缓存利用率低的问题：
递归过程中对数组的随机访问可能导致缓存未命中（cache miss），增加内存访问开销。

快速排序的 “优化” 本质上是扬长避短：保留其平均 O(n log n) 时间复杂度、原地排序（空间效率高）的优点，同时通过针对性改进，解决基准选择不当、小规模数据低效、重复元素处理差等问题

1. 三数取中法选key

快速排序优化核心思路：

选好基准：用三数取中或随机法，避免选到最值导致分割失衡。
小数据换算法：区间长度较小时（如 < 15），改用插入排序，减少递归开销。
处理重复值：用三路分割（小于 / 等于 / 大于基准），避免重复元素拖累效率。
控制递归：用尾递归或手动栈，防止栈溢出，降低递归成本。
混合策略：如内省排序，快速排序 + 堆排序 + 插入排序结合，兼顾效率与稳定性。

private static void quick(int[] array, int start, int end) {
    if (start >= end) {
        return;
    }
    // 三数取中
    int index = mid_three(array, start, end);
    swap(array, index, start);

    int pivot = partition(array, start, end);

    quick(array, start, pivot - 1);
    quick(array, pivot + 1, end);
}
 private static int mid_three(int[] array, int left, int right) {
        int mid = (left+right)/2;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] > array[left]) {
                return left;
            }else if(array[mid] < array[right]) {
                return right;
            }else {
                return mid;
            }
        }
    }

但是这个优化的深度还是不够，如果他是[9,8,7,6,5],你在交换的完，右指针会进行很多的交换，还是有一定的问题的

2. 递归到小的子区间时，可以考虑使用插入排序

1.对外接口 quickSort(int[] array) 作为公共方法，接收待排序数组，调用内部递归方法 quick 并传入数组的全区间（从索引 0 到 array.length-1），隐藏了排序的细节实现。 2.核心递归方法 quick(int[] array, int start, int end)负责快速排序的主要逻辑，处理数组中 [start, end] 区间的排序：

**终止条件：**若 start >= end（区间为空或只有一个元素），直接返回（已有序）。
小规模数据优化：若区间长度 end - start + 1 <= 15（阈值可调整），调用 insertSort 用插入排序处理，避免快速排序的递归开销。
基准选择优化：通过 mid_three 方法（三数取中）选择区间内的 “中间值” 作为基准，交换到区间起始位置（便于后续分区）。
**分区与递归：**调用 partition 方法（需自行实现）将区间按基准分为 “小于基准” 和 “大于基准” 两部分，返回基准的最终位置 pivot，再递归处理左右子区间 [start, pivot-1] 和 [pivot+1, end]。

3.插入排序辅助方法 insertSort(int[] array, int left, int end)专门处理小规模区间 [left, end] 的排序：通过 “逐个将元素插入到已排序部分的正确位置” 实现排序，适合小规模数据（因逻辑简单、无递归开销，效率高于快速排序）。

    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }

        if(end-start+1 <= 15) {
            insertSort(array,start,end);
            return;
        }

        //三数取中
        int index = mid_three(array,start,end);
        swap(array,index,start);

        int pivot = partition(array,start,end);

        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
//插入排序
    public static void insertSort(int[] array,int left,int end) {
        for (int i = left+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= left; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

3.快速排序非递归

点击这里，进行把栈扩大

出现这个界面

if(pivot > start + 1){
	左边有两个及以上的数据
	}
	if(pivot < end - 1){
	右边有两个及以上的数据
}

    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];

            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
  public static void quickSortNonR(int[] array) {
        int start = 0;
        int end = array.length-1;
        Deque<Integer> stack = new LinkedList<>();
        int pivot = partition(array,start,end);
        if(pivot > start + 1) {
            stack.push(start);
            stack.push(pivot-1);
        }
        if(pivot < end - 1) {
            stack.push(pivot+1);
            stack.push(end);
        }
        while (!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partition(array,start,end);
            if(pivot > start + 1) {
                stack.push(start);
                stack.push(pivot-1);
            }
            if(pivot < end - 1) {
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }

4.快速排序的总结

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)

空间复杂度：O(logN)
稳定性：不稳定局部优化并不能从根上解决问题，对于快排，可以看一下尾递归的实现

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的⼀种有效的排序算法,该算法是采用分治法（Divide andConquer）的⼀个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成⼀个有序表，称为二路归并。思路：

1.不断的分割数据，让数据的每一段都有序（一个数据相当于有序）

2.当所有子序列有序的时候，在把子序列归并，形成更大的子序列，最终整个数组有序。

该图借鉴：https://www.cnblogs.com/MarisaMagic/p/16908457.html

 /**
     * 时间复杂度：O(N*logN) 和数据是否有序无序没有关系
     * 空间复杂度：O(N)
     * 稳定性：稳定的
     *       直接插入   冒泡排序  归并排序
     * @param array
     */
public static void mergeSort(int[] array) {
    mergeChild(array, 0, array.length - 1);
}

private static void mergeChild(int[] array, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = (left + right) / 2;
    mergeChild(array, left, mid);      // 递归排序左半部分
    mergeChild(array, mid + 1, right); // 递归排序右半部分
    merge(array, left, mid, right);    // 合并两个有序子数组
}

// 合并两个有序子数组：array[left..mid] 和 array[mid+1..right]
private static void merge(int[] array, int left, int mid, int right) {
    int[] temp = new int[right - left + 1]; // 临时数组，存储合并后的结果
    int i = left;   // 左子数组的起始指针
    int j = mid + 1; // 右子数组的起始指针
    int k = 0;      // 临时数组的指针

    // 比较左右子数组的元素，按从小到大放入临时数组
    while (i <= mid && j <= right) {
        if (array[i] <= array[j]) {
        //左右两个数组都是前边小，后边大，所以两边比较，谁小谁先存
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }
//因为两边的数不一定相等，需要我们判断到底是那一边长，就执行哪边

    // 处理左子数组剩余的元素
    while (i <= mid) {
        temp[k++] = array[i++];
    }

    // 处理右子数组剩余的元素
    while (j <= right) {
        temp[k++] = array[j++];
    }

    // 将临时数组的结果拷贝回原数组
    for (k = 0; k < temp.length; k++) {
        array[left + k] = temp[k];
    }
}

非递归的归并

  /**
     * 非递归的归并排序
     * @param array
     */
    public static void mergeSortNor(int[] array) {
        int gap = 1;
        while (gap < array.length) {
        // 用于遍历每个分组的起始位置
        //i + 2*gap 表示跳到 “下一个同类型分组的起始位置”（因为每个分组内部的元素间隔为 gap，相邻分组的起始位置间隔为 2*gap）
//        每一对 “待合并的相邻子数组” 的第一个子数组的起始下标
//这一步就是把每两个小数组合并成大一点的大数组，所以中间大数组的起点间隔就是i+* gap,小数组是2 * gap
            for (int i = 0; i < array.length; i = i + 2*gap) {
                int left = i;
                int mid = left+gap - 1;
                //因为他们会越界 mid ,right .所以在他们要越界的时候，放他们等于数组最后一个
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int right = mid+gap;
                if(right >= array.length) {
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap *= 2;
        }
    }

2.4.2 归并排序总结

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
时间复杂度：O(N*logN)
空间复杂度：O(N)
稳定性：稳定

2.4.3 海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进⾏的排序前提：内存只有1G，需要排序的数据有100G 因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

先把文件切分成200份，每个512M
分别对512M排序，因为内存已经可以放的下，所以任意排序方式都可以
进行2路归并，同时对200份有序文件做归并过程，最终结果就有序了
排序算法复杂度及稳定性分析

希尔排序写的不是很准确，上面有介绍

4. 其他非基于比较排序（了解）

1. 计数排序

注意：图片来源https://blog.csdn.net/k1234hxh/article/details/134631590

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。操作步骤： a. 统计相同元素出现次数 b. 根据统计的结果将序列回收到原来的序列中【计数排序的特性总结】 a. 计数排序在数据范围集中时，效率很高，但是使用范围及场景有限。 b. 时间复杂度：O(MAX(N,范围)) c. 空间复杂度：O(范围) d. 稳定性：稳定

2. 基数排序

注意：该图借鉴https://blog.csdn.net/m0_46975599/article/details/112174826 核心原理确定最大位数 d：找到数组中最大的数，确定其位数（如最大数是 123，则 d=3）。按位排序：从最低位（个位）到最高位（百位），对每一位进行 “分配 - 收集” 操作：

分配：将所有数按当前位的值（0-9）放入对应的 “桶”（共 10 个桶，对应 0-9）。
收集：按桶的顺序（0→9）将元素依次取出，组成新的数组，此时数组按当前位有序。
重复：完成所有位数的排序后，数组整体有序。

import java.util.Arrays;

public class RadixSort {

    // 基数排序入口
    public static void radixSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        // 1. 找到数组中的最大值，确定最大位数 d
        int max = array[0];
        for (int num : array) {
            if (num > max) {
                max = num;
            }
        }
        int d = 0; // 最大位数
        while (max > 0) {
            max /= 10;
            d++;
        }

        // 2. 按每位进行排序（从个位到高位）
        int radix = 1; // 用于提取当前位（1：个位，10：十位，100：百位...）
        int[][] buckets = new int[10][array.length]; // 10个桶，每个桶最多存放array.length个元素
        int[] bucketCounts = new int[10]; // 记录每个桶中元素的数量

        for (int i = 0; i < d; i++) { // 循环 d 次，处理每一位
            // 清空桶计数
            Arrays.fill(bucketCounts, 0);

            // 分配：将元素按当前位放入对应桶中
            for (int num : array) {
                int digit = (num / radix) % 10; // 提取当前位的值（0-9）
                buckets[digit][bucketCounts[digit]++] = num;
            }

            // 收集：按桶顺序（0-9）将元素取出，重新组成数组
            int index = 0;
            for (int j = 0; j < 10; j++) { // 遍历每个桶
                for (int k = 0; k < bucketCounts[j]; k++) { // 取出桶中所有元素
                    array[index++] = buckets[j][k];
                }
            }

            radix *= 10; // 处理下一位（个位→十位→百位...）
        }
    }

    // 测试
    public static void main(String[] args) {
        int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("排序前：" + Arrays.toString(array));
        radixSort(array);
        System.out.println("排序后：" + Arrays.toString(array));
    }
}

特点与适用场景优点：效率高（非比较排序），适合大规模整数排序。缺点：依赖数据的位数，不适用于浮点数（需特殊处理）或长度差异大的字符串，且需要额外空间（桶）。适用场景：整数排序、固定长度的字符串排序（如手机号、邮编）等。

3. 桶排序

核心原理

创建桶：根据数据范围和分布，创建 k 个空桶（通常是数组或链表）。
分配数据：遍历待排序数组，将每个元素放入对应的桶中（例如：0-9 分放桶 0，10-19 分放桶 1…）。
桶内排序：对每个非空桶内的元素单独排序（可使用快速排序、插入排序等）。
合并结果：按桶的顺序依次取出所有元素，拼接成最终的有序数组。

import java.util.*;

public class BucketSort {

    // 桶排序入口
    public static void bucketSort(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        // 1. 确定数据范围（假设数据在 [0, 100) 之间）
        int min = 0;
        int max = 100;
        int bucketCount = 10; // 创建10个桶，每个桶存放10个范围的数据（0-9, 10-19, ..., 90-99）
        int bucketSize = (max - min) / bucketCount; // 每个桶的范围大小

        // 2. 初始化桶（使用链表存储桶内元素，方便动态添加）
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new LinkedList<>());
        }

        // 3. 将元素分配到对应的桶中
        for (int num : array) {
            // 计算元素应放入的桶索引（确保索引在0~bucketCount-1之间）
            int bucketIndex = Math.min((num - min) / bucketSize, bucketCount - 1);
            buckets.get(bucketIndex).add(num);
        }

        // 4. 对每个桶内的元素排序，并合并结果
        int index = 0;
        for (List<Integer> bucket : buckets) {
            if (!bucket.isEmpty()) {
                // 桶内排序（使用Collections.sort，底层是归并排序的变种）
                Collections.sort(bucket);
                // 将排序后的桶元素放入原数组
                for (int num : bucket) {
                    array[index++] = num;
                }
            }
        }
    }

    // 测试
    public static void main(String[] args) {
        int[] array = {45, 22, 88, 35, 56, 12, 77, 9, 63};
        System.out.println("排序前：" + Arrays.toString(array));
        bucketSort(array);
        System.out.println("排序后：" + Arrays.toString(array));
    }
}

特点与适用场景优点：效率高（数据均匀时接近线性时间），可并行处理（每个桶独立排序）。缺点：依赖数据分布（分布不均时效率下降），需要额外空间存储桶。适用场景：数据范围明确且分布均匀的场景（如学生成绩、用户年龄、商品价格等）。桶排序是 “分治思想” 的典型应用，通过将大问题拆分为小问题（每个桶的排序），再合并结果，实现高效排序。