排序算法整理

一、插入排序类

直接插入排序

示例代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
	/**
     * 插入排序
     * @param arr
     * i   6 7 9 2 3
     * 1-> 6 7 9 2 3
     * 2-> 6 7 9 2 3
     * 3-> 6 7 2 9 3
     *  -> 6 2 7 9 3
     *  -> 2 6 7 9 3
     * 4-> 2 6 7 3 9
     *  -> 2 6 3 7 9
     *  -> 2 3 6 7 9
     */
    public static void insertionSort(int[] arr){
        //外层循环: 遍历未排序部分 (从第二个元素开始)
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i]; //当前需要插入的元素
            int j = i - 1; //已排序部分的最后一个元素

            //内层循环: 从已排序部分最后一个元素开始, 向前遍历, 寻找插入的位置
            for (; j >= 0; j--) {
                if (arr[j] > temp) {
                    arr[j + 1] = arr[j]; //将大于当前元素的元素向后移动一位
                } else {
                    break;
                }
            }
            arr[j + 1] = temp;//将当前元素插入到找到的位置
        }
    }

关键说明

算法核心逻辑
- 外层循环 (for)遍历数组中未排序的元素(从第二个元素开始)
- 内层循环将当前元素temp与已排序部分的元素从后往前比较
- 如果发现更大的元素，则将其向后移动，直到找到插入位置
时间复杂度
- 最优情况(已经排序好的数组): O(n)
- 最差/平均情况(完全逆序)：O($n^2$)
- 适合小规模数据或基本有序的数据
关键特点
- 原地排序：不需要额外的内存空间
- 稳定排序：相同值的元素相对位置不变
- 逐步构建有序序列：每次处理一个元素，逐步扩大有序空间

希尔排序

代码示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
    /**
     * 希尔排序
     * @param arr
     *  初始数据   6 7 9 2 3  n=5
     *  外循环：gap=2
     *  次循环：gap=2 ,i=2 ,temp=9 ,j=2 array:[6, 7, 9, 2, 3]
     *  内循环：gap=2 ,i=3 ,temp=2 ,j=1 array:[6, 7, 9, 7, 3]
     *  次循环：gap=2 ,i=3 ,temp=2 ,j=1 array:[6, 2, 9, 7, 3]
     *  内循环：gap=2 ,i=4 ,temp=3 ,j=2 array:[6, 2, 9, 7, 9]
     *  内循环：gap=2 ,i=4 ,temp=3 ,j=0 array:[6, 2, 6, 7, 9]
     *  次循环：gap=2 ,i=4 ,temp=3 ,j=0 array:[3, 2, 6, 7, 9]
     *
     *  外循环：gap=1
     *  内循环：gap=1 ,i=1 ,temp=2 ,j=0 array:[3, 3, 6, 7, 9]
     *  次循环：gap=1 ,i=1 ,temp=2 ,j=0 array:[2, 3, 6, 7, 9]
     *  次循环：gap=1 ,i=2 ,temp=6 ,j=2 array:[2, 3, 6, 7, 9]
     *  次循环：gap=1 ,i=3 ,temp=7 ,j=3 array:[2, 3, 6, 7, 9]
     *  次循环：gap=1 ,i=4 ,temp=9 ,j=4 array:[2, 3, 6, 7, 9]
     */
    public static void shellSort(int[] arr) {
        int n = arr.length;
        // 初始间隔（gap）设置为数组长度的一半，逐步缩小间隔直到1
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // 对每个间隔分组进行插入排序
            System.out.println("外循环：gap="+gap);
            for (int i = gap; i < n; i++) {
                int temp = arr[i]; // 当前待插入元素
                int j = i;
                boolean flag = false;
                // 插入排序逻辑（按间隔分组）
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap]; // 将较大的元素向后移动
                    j -= gap;
                    flag = true;
                    System.out.println("内循环：gap="+gap+" ,i="+i+" ,temp="+temp+" ,j="+j+" array:"+Arrays.toString(arr));
                }
                arr[j] = temp; // 插入元素到正确位置
                System.out.println("次循环：gap="+gap+" ,i="+i+" ,temp="+temp+" ,j="+j+" array:"+Arrays.toString(arr));
            }
        }
    }

关键说明

算法思想
- 希尔排序是 插入排序的改进版，通过将数组按间隔 (gap) 分组，对每组进行插入排序。
- 逐步缩小间隔(如从 n/2 到 1 )，最终对整个数组进行一次插入排序。
时间复杂度
- 最优情况：O(n log n) (取决于间隔序列)
- 最差情况：O($n^2$) (取决于间隔序列)
- 平均性能：优于插入排序，适合中等规模数据。
空间复杂度
- O(1) （原地排序，无需额外空间)
稳定性
- 不稳定排序 (分组插入可能导致相同值的元素相对位置改变)

二、交互排序类

冒泡排序

示例代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
	/**
     * 冒泡排序实现（带优化）
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped; // 优化标志

        // 外层循环：控制遍历轮次（最多需要 n-1 轮）
        for (int i = 0; i < n - 1; i++) {
            swapped = false;

            // 内层循环：比较相邻元素并交换（每轮减少一个末尾已排序元素）
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换元素
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            // 如果本轮未发生交换，说明数组已完全有序，提前终止
            if (!swapped) break;
        }
    }

关键特性说明

算法核心逻辑
- 双循环结构：外层循环控制排序轮次，内层循环执行相邻元素比较和交换
- 元素交换：通过临时变量 temp实现相邻元素的位置交换
- 优化标志：swapped标记本轮是否发生交换，若无交换则提前终止排序
时间复杂度
- 最优情况，输入数组已经完全有序，O(n)
- 最差情况，输入数组完全逆序，O($n^2$)
- 平均情况，O($n^2$) ，适用于小型数据集
空间复杂度
- O(1) 原地排序，仅需常数级额外空间
稳定性
- 稳定排序：相等元素不会发生位置交换

快速排序

代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    public static void quickSort(int[] arr, int start, int end) {
        if (start >= end) return; // 递归终止条件
        
        // 选择中间元素作为基准值
        int pivot = arr[(start + end) / 2];
        int i = start;
        int j = end;
        
        // 双指针分区操作
        while (i <= j) {
            // 找到左边大于等于基准的元素
            while (arr[i] < pivot) i++;
            // 找到右边小于等于基准的元素
            while (arr[j] > pivot) j--;
            // 交换并移动指针
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        
        // 递归处理左右子数组
        quickSort(arr, start, j);
        quickSort(arr, i, end);
    }

    // 交换数组元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

关键步骤说明：

基准选择：选择数组中间位置的元素作为基准值(pivot)
双指针分区：
- 左指针(i)：从左边开始寻找大于等于基准值的元素。
- 右指针(j): 从右边开始寻找小于等于基准值的元素。
- 当找到这样的元素时，交换他们并移动指针，直到指针交叉（i>j）.
递归排序: 将数组分为左右两个子数组 (start到j和i到end),分别递归调用快速排序。

时间复杂度：

平均情况： O(n log n)
最坏情况： (如数组已有序且基准选择不当) ：O($n^2$),但通过合理选择基准（如三数取中法)可优化。

特点：

**原地排序：**不需要额外空间。
**不稳定排序：**相等元素的顺序可能被打乱。
**高效性：**实际应用通常优于其他O(n log n) 算法。

三、选择排序类

简单选择排序

代码示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // 外层循环：每一轮确定一个最小值的位置
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;  // 记录最小值的位置
            
            // 内层循环：在未排序区间寻找最小值
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            
            // 将最小值交换到已排序区间的末尾
            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;
    }

算法特点说明：

工作原理：
- 每次从未排序区间中选择最小值，放到已排序区间的末尾
- 时间复杂度始终为 O($n^2$) (无论数据是否有序)
- 不稳定排序: 可能改变相等元素的原始顺序
核心步骤:
- **外层循环：**控制已排序区间的增长（从0到n-2）
- **内层循环：**遍历未排序区间，寻找最小值的位置
- **交换操作：**将最小值与当前未排序区间的第一个元素交换
性能对比：
特性选择排序快速排序
时间复杂度 $O(n^2)$ 平均$O(n log n)$
空间复杂度 $O(1)$ $O(log n)到O(n)$
稳定性不稳定不稳定
适用场景小数据量/内存敏感大规模数据

特性	选择排序	快速排序
时间复杂度	$O(n^2)$	平均$O(n log n)$
空间复杂度	$O(1)$	$O(log n)到O(n)$
稳定性	不稳定	不稳定
适用场景	小数据量/内存敏感	大规模数据

堆排序

示例代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 1. 构建最大堆（初始堆化）
        for (int i = n/2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 2. 逐个提取堆顶元素（最大值）
        for (int i = n-1; i > 0; i--) {
            swap(arr, 0, i);    // 将当前最大值移到数组末尾
            heapify(arr, i, 0);  // 调整剩余元素的堆结构
        }
    }

    // 调整以节点i为根的子树为最大堆
    private static void heapify(int[] arr, int heapSize, int i) {
        int largest = i;        // 初始化最大元素为根节点
        int left = 2*i + 1;     // 左子节点索引
        int right = 2*i + 2;    // 右子节点索引

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

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

        // 如果最大值不是根节点，则交换并递归调整
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, heapSize, largest);  // 递归调整被破坏的子堆
        }
    }

    // 交换数组元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

核心步骤解析：

堆的构建 (heapify)
- 时间复杂度：O(n)
- 从最后一个非叶子节点开始（索引n/2-1）
- 自底向上调整每个子树为最大堆
排序过程
- 时间复杂度：O(n log n)
- 每次将堆顶最大值交换到数组末尾
- 重新调整剩余元素为最大堆
- 堆大小每次减少1

执行过程示例 (数组【5,3,8,4,2】)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
初始数组：5 3 8 4 2

构建最大堆：
        5           -> 调整后：
       / \                 8
      3   8              / \
     / \               5   3
    4   2            / \
                    4   2

第一次交换：8 <-> 2
堆大小减1，调整堆：[2,5,3,4] + [8]

后续步骤：
5 <-> 4 -> 调整堆 [4,3,2]+ [5,8]
4 <-> 3 -> 调整堆 [3,2]+ [4,5,8]
3 <-> 2 -> 调整堆 [2] + [3,4,5,8]
最终结果：2 3 4 5 8

算法特性：

特性	堆排序
时间复杂度	始终 O(n log n)
空间复杂度	O(1)
稳定性	不稳定
适用场景	大数据量、优先队列

关键优化点：

非叶子节点计算： n/2-1保证从最后一个有子节点的元素开始调整
**递归调整：**当发生节点交换时，需要递归调整被破坏的子堆结构
**原地排序：**直接原数组上操作，无需额外空间

该实现通过构建最大堆实现升序排序，若需要降序排序只需改为构建最小堆。堆排序虽然时间复杂度优秀，但实际应用中由于频繁的堆调整操作，其常数因子较大，通常在小数据量时性能不如快速排序。

四、归并排序类

归并排序

代码示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
package com.sort;

/**
 * 原始数组: [12, 11, 13, 5, 6, 7]
 * mergeSort: [12, 11, 13, 5, 6, 7] ,left=0 ,right=5
 * mergeSort: [12, 11, 13, 5, 6, 7] ,left=0 ,right=2
 * mergeSort: [12, 11, 13, 5, 6, 7] ,left=0 ,right=1
 * merge : [12, 11, 13, 5, 6, 7] ,left=0 ,mid=0 ,right=1
 * merge : [11, 12, 13, 5, 6, 7] ,left=0 ,mid=1 ,right=2
 * mergeSort: [11, 12, 13, 5, 6, 7] ,left=3 ,right=5
 * mergeSort: [11, 12, 13, 5, 6, 7] ,left=3 ,right=4
 * merge : [11, 12, 13, 5, 6, 7] ,left=3 ,mid=3 ,right=4
 * merge : [11, 12, 13, 5, 6, 7] ,left=3 ,mid=4 ,right=5
 * merge : [11, 12, 13, 5, 6, 7] ,left=0 ,mid=2 ,right=5
 * 排序后数组: [5, 6, 7, 11, 12, 13]
 *
 */
import java.util.Arrays;

public class MergeSort {

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

    private static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            System.out.println("mergeSort: " + Arrays.toString(arr) +" ,left="+left+" ,right="+right);// 合并两个有序子数组
            int mid = left + (right - left) / 2; // 防止整数溢出
            mergeSort(arr, left, mid);          // 递归排序左半部分
            mergeSort(arr, mid + 1, right);      // 递归排序右半部分
            merge(arr, left, mid, right);

        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        System.out.println("merge : " + Arrays.toString(arr) +" ,left="+left+" ,mid="+mid+" ,right="+right);
        // 计算左右子数组的长度
        int n1 = mid - left + 1;
        int n2 = right - mid;

        // 创建临时数组并拷贝数据
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }

        // 合并临时数组到原数组
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 拷贝剩余元素
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("原始数组: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后数组: " + Arrays.toString(arr));
    }
}

代码说明

sort方法：入口方法，检查数组有效性后调用递归排序
mergeSort方法：
- **递归分解：**将数组分成左右两部分，直到子数组长度为1
- **合并操作：**调用merge方法合并两个已排序的子数组。
merge方法：
- **创建临时数组：**存储左右子数组的数据。
- **合并逻辑：**通过双指针遍历临时数组，将顺序将比较小值放回原数组。
- **剩余元素处理：**将未遍历完的子数组剩余元素直接复制到原数组。

特点：

**时间复杂度：**O(n log n),适用于大规模数据。
**空间复杂度：**O(n),需要额外空间存储临时数组
**稳定性：**相等元素的顺序在排序后保持不变。

五、线性时间排序类

计数排序

代码示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package com.sort;

import java.util.Arrays;

/**
 * 原始数组: [4, -2, 2, 8, 3, 3, 1]
 * max:8 min:-2 range:11 ,counts:[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 * counts1:[1, 0, 0, 1, 1, 2, 1, 0, 0, 0, 1]
 * counts2:[1, 1, 1, 2, 3, 5, 6, 6, 6, 6, 7]
 * output:[-2, 1, 2, 3, 3, 4, 8]
 * 排序后数组: [-2, 1, 2, 3, 3, 4, 8]
 */
public class CountingSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 找到数组中的最大值和最小值
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();

        // 计算数值范围并初始化计数数组
        int range = max - min + 1;
        int[] counts = new int[range];
        System.out.println("max:"+max+" min:"+min+" range:"+range+" ,counts:"+Arrays.toString(counts));

        // 统计每个元素的出现次数
        for (int num : arr) {
            counts[num - min]++;
        }
        System.out.println("counts1:"+Arrays.toString(counts));

        // 将计数数组转换为累加形式（表示元素的最后位置）
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }
        System.out.println("counts2:"+Arrays.toString(counts));

        // 创建临时数组保存排序结果
        int[] output = new int[arr.length];

        // 反向填充保证稳定性
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            int index = counts[num - min] - 1; // 计算实际存储位置
            output[index] = num;
            counts[num - min]--;
        }
        System.out.println("output:"+Arrays.toString(output));

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

    public static void main(String[] args) {
        // 测试包含负数的数组
        int[] arr = {4, -2, 2, 8, 3, 3, 1};
        System.out.println("原始数组: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后数组: " + Arrays.toString(arr));
    }
}

代码说明：

核心思想
通过统计每个元素的出现次数，直接计算元素在有序数组中的位置
- 时间复杂度：O(n + k) (**K**为数据范围) ，适合数据范围较小的整数排序。
- 空间复杂度：O(n + k) ,需要额外空间存储计数数组和临时结果。
- **稳定排序：**通过反向填充保证相同元素的元素顺序不变。
关键步骤
- **确定数值范围：**通过最大值和最小值计算数据范围，处理负数。
- **统计频率：**用计数数组记录每个元素出现的次数。
- **累加计数：**将计数数组转换为累加形式，表示元素的最后位置。
- **反向填充：**从原数组末尾开始遍历，确保稳定性。

注意事项

**适用场景：**适用于整数且数据范围较小的情况(如年龄、分数等)
**优化点：**若数据范围过大(例如超过 $10^7$)，需考虑其他排序算法。
**负数处理：**通过计算偏移量 num-min,将负数映射到计数数组的合法索引。

桶排序

代码示例:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;

public class BucketSort {

    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        // 找到数组中的最大值和最小值
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();
        int range = max - min;

        // 处理所有元素相同的情况
        if (range == 0) return;

        // 1. 确定桶的数量（可根据需求调整公式）
        int bucketNum = (int) Math.sqrt(arr.length) + 1;
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(bucketNum);

        // 初始化所有桶
        for (int i = 0; i < bucketNum; i++) {
            buckets.add(new ArrayList<>());
        }

        // 2. 分配元素到桶中
        for (int num : arr) {
            // 计算桶的索引（处理负数）
            int bucketIndex = (int) ((num - min) * (bucketNum - 1) / (double) range);
            buckets.get(bucketIndex).add(num);
        }

        // 3. 对每个桶进行排序，并合并结果
        int index = 0;
        for (ArrayList<Integer> bucket : buckets) {
            Collections.sort(bucket); // 使用内置排序
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {-3, 5, 2, -1, 4, 7, 9, 0, 12, -5};
        System.out.println("原始数组: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后数组: " + Arrays.toString(arr));
    }
}

代码说明

核心思想
- 将元素分配到有限数量的桶中
- 对每个桶单独排序(可使用任意排序算法)
- 按桶顺序合并结果
关键步骤
- **确定桶数量：**取数组长度的平方根
- 元素分配公式： **(num-min)*(n-1)/range**保证均匀分布
- 处理负数：通过num-min 将数据偏移到非负区间
- **桶内排序：使用Collections.sort**保证代码简洁性
时间复杂度
- 平均：O(n + k) （k为桶数量)
- 最佳：O(n) （均匀分布时）
- 空间复杂度：O(n+k)

算法特点：

特性	说明
适用场景	数据均匀分布的浮点数/整数排序
稳定性	取决于桶内使用的排序算法(本例使用稳定排序Collections.sort)
优化方向	动态调整桶数量、桶内改用插入排序优化小数据排序性能

扩展说明：

动态桶数量：可根据数据分布特征使用更智能的分配策略
混合排序：当桶内元素少于阈值时，使用插入排序提高性能
浮点数支持：通过调整映射公式可支持浮点数排序

基数排序

以下是使用Java实现基数排序的代码示例，包含对负数的处理：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import java.util.ArrayList;
import java.util.Arrays;

public class RadixSort {

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

        // 分离正负数
        ArrayList<Integer> negatives = new ArrayList<>();
        ArrayList<Integer> positives = new ArrayList<>();
        for (int num : arr) {
            if (num < 0) negatives.add(-num);  // 负数取绝对值
            else positives.add(num);
        }

        // 处理负数部分：绝对值排序 -> 反转 -> 恢复符号
        int[] negArr = listToArray(negatives);
        radixSort(negArr);
        reverse(negArr);
        for (int i = 0; i < negArr.length; i++) {
            negArr[i] = -negArr[i];  // 恢复负数符号
        }

        // 处理正数部分
        int[] posArr = listToArray(positives);
        radixSort(posArr);

        // 合并结果
        mergeResults(arr, negArr, posArr);
    }

    // 对非负整数进行基数排序（LSD实现）
    private static void radixSort(int[] arr) {
        if (arr.length == 0) return;

        int max = Arrays.stream(arr).max().getAsInt();
        int exp = 1;  // 当前位数
        int[] output = new int[arr.length];

        while (max / exp > 0) {
            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);
            exp *= 10;  // 处理更高位
        }
    }

    // 工具方法：反转数组
    private static void reverse(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int temp = arr[left];
            arr[left++] = arr[right];
            arr[right--] = temp;
        }
    }

    // 工具方法：合并正负数结果
    private static void mergeResults(int[] arr, int[] negatives, int[] positives) {
        int index = 0;
        for (int num : negatives) arr[index++] = num;
        for (int num : positives) arr[index++] = num;
    }

    // 工具方法：将List转换为数组
    private static int[] listToArray(ArrayList<Integer> list) {
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) {
        int[] arr = {-123, 45, -7, 0, 234, -789, 999, 2, -2};
        System.out.println("原始数组: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后数组: " + Arrays.toString(arr));
    }
}

代码说明：

核心思想
- 按位数从低到高（LSD）依次进行稳定排序
- 负数处理：取绝对值排序 -> 反转结果 -> 恢复符号
- 时间复杂度：O(d(n + k))*（d为最大位数，k为基数10）
关键步骤
- 分离正负数：将负数转换为正数处理
- 基数排序核心：
  - 统计当前位频率 -> 计算前缀和 -> 反向填充保证稳定性
- 合并结果：处理后的负数在前，正数在后
执行结果：

1
2
原始数组: [-123, 45, -7, 0, 234, -789, 999, 2, -2]
排序后数组: [-789, -123, -7, -2, 0, 2, 45, 234, 999]

算法特点：

特性	说明
适用场景	整数排序（包括负数），尤其适合位数较少的场景
稳定性	稳定排序（每轮使用计数排序保证顺序）
空间复杂度	O(n + k)（k为基数10）
优化方向	动态调整基数（如按字节处理）、并行化高位排序

扩展说明：

混合基数：使用256基数（按字节处理）可减少排序轮次
MSD变体：最高位优先排序适合字符串排序，可提前终止分支
并行优化：高位排序完成后，可对低位进行并行排序

一 、插入排序类#

直接插入排序#

关键说明#

希尔排序#

关键说明#

二、交互排序类#

冒泡排序#

关键特性说明#

快速排序#

关键步骤说明：#

时间复杂度：#

特点：#

三、选择排序类#

简单选择排序#

算法特点说明：#

堆排序#

核心步骤解析：#

四、归并排序类#

归并排序#

代码说明#

特点：#

五、线性时间排序类#

计数排序#

代码说明：#

注意事项#

桶排序#

代码说明#

算法特点：#

扩展说明：#

基数排序#

代码说明：#

算法特点：#

扩展说明：#

一、插入排序类

直接插入排序

关键说明

希尔排序

关键说明

二、交互排序类

冒泡排序

关键特性说明

快速排序

关键步骤说明：

时间复杂度：

特点：

三、选择排序类

简单选择排序

算法特点说明：

堆排序

核心步骤解析：

四、归并排序类

归并排序

代码说明

特点：

五、线性时间排序类

计数排序

代码说明：

注意事项

桶排序

代码说明

算法特点：

扩展说明：

基数排序

代码说明：

算法特点：

扩展说明：