数据结构入门教程：线性排序算法详解与Java实现

🚀 引言：突破比较排序的极限

想象一下学校里给学生按年龄分组的场景：我们不需要两两比较每个学生的年龄，而是准备18个箱子（代表18岁以下到35岁），让学生直接走到对应年龄的箱子前排队。这就是线性排序的思想！

传统的比较排序算法（如快排、归并排序）理论下界是 O(n log n)，但线性排序算法通过利用输入数据的特殊性质，能够在 O(n) 时间内完成排序，实现了质的突破！

流程图表

关系流向：

1
2
3
4
5
A["传统比较排序<br/>O(n log n)"] → B["理论下界限制"]
C["线性排序算法<br/>O(n)"] → D["利用数据特征"]
D → E["计数排序<br/>整数范围有限"]
D → F["桶排序<br/>数据均匀分布"]
D → G["基数排序<br/>固定位数"]

🔢 计数排序（Counting Sort）

计数排序适用于排序整数，且数值范围不大的情况。它通过统计每个值出现的次数来实现排序。

基本原理

计数排序的核心思想是：统计每个元素出现的次数，然后根据统计结果重建有序序列。

  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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
/**
 * 计数排序实现
 * 时间复杂度：O(n + k)，其中k是数据范围
 * 空间复杂度：O(k)
 * 稳定性：稳定
 */
public class CountingSort {

    /**
     * 基础计数排序（适用于非负整数）
     * @param arr 待排序数组
     * @return 排序后的新数组
     */
    public static int[] countingSortBasic(int[] arr) {
        if (arr.length == 0) return arr;

        // 找到数组中的最大值，确定计数数组大小
        int max = findMax(arr);
        System.out.println("原数组: " + Arrays.toString(arr));
        System.out.println("数据范围: 0 到 " + max);

        // 创建计数数组
        int[] count = new int[max + 1];

        // 统计每个元素出现的次数
        for (int num : arr) {
            count[num]++;
        }

        System.out.println("计数数组: " + Arrays.toString(count));

        // 根据计数数组重建排序结果
        int[] result = new int[arr.length];
        int index = 0;

        for (int i = 0; i <= max; i++) {
            while (count[i] > 0) {
                result[index++] = i;
                count[i]--;
            }
        }

        System.out.println("排序结果: " + Arrays.toString(result));
        return result;
    }

    /**
     * 稳定版本的计数排序
     * 保持相等元素的相对位置不变
     */
    public static int[] countingSortStable(int[] arr) {
        if (arr.length == 0) return arr;

        int max = findMax(arr);
        int min = findMin(arr);
        int range = max - min + 1;

        System.out.println("数据范围: " + min + " 到 " + max + " (范围大小: " + range + ")");

        // 创建计数数组
        int[] count = new int[range];

        // 统计每个元素出现的次数
        for (int num : arr) {
            count[num - min]++;
        }

        System.out.println("计数数组: " + Arrays.toString(count));

        // 计算累计计数（前缀和）
        for (int i = 1; i < range; i++) {
            count[i] += count[i - 1];
        }

        System.out.println("累计计数: " + Arrays.toString(count));

        // 从右向左扫描原数组，构建排序结果（保证稳定性）
        int[] result = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            int pos = count[num - min] - 1;
            result[pos] = num;
            count[num - min]--;
        }

        return result;
    }

    /**
     * 计数排序对象版本
     * 可以排序包含多个字段的对象
     */
    public static class Student {
        int id;
        String name;
        int score;

        public Student(int id, String name, int score) {
            this.id = id;
            this.name = name;
            this.score = score;
        }

        @Override
        public String toString() {
            return String.format("Student{id=%d, name='%s', score=%d}", id, name, score);
        }
    }

    /**
     * 按分数排序学生（保持稳定性）
     */
    public static Student[] countingSortStudents(Student[] students) {
        if (students.length == 0) return students;

        // 假设分数范围是0-100
        int[] count = new int[101];

        // 统计每个分数的学生人数
        for (Student student : students) {
            count[student.score]++;
        }

        // 计算累计计数
        for (int i = 1; i < 101; i++) {
            count[i] += count[i - 1];
        }

        // 构建排序结果
        Student[] result = new Student[students.length];
        for (int i = students.length - 1; i >= 0; i--) {
            Student student = students[i];
            int pos = count[student.score] - 1;
            result[pos] = student;
            count[student.score]--;
        }

        return result;
    }

    /**
     * 计数排序的变种：排序字符数组
     */
    public static char[] countingSortChars(char[] chars) {
        if (chars.length == 0) return chars;

        // ASCII字符范围通常是0-127，这里假设只处理可打印字符32-126
        int[] count = new int[128];

        for (char ch : chars) {
            count[ch]++;
        }

        char[] result = new char[chars.length];
        int index = 0;

        for (int i = 0; i < 128; i++) {
            while (count[i] > 0) {
                result[index++] = (char) i;
                count[i]--;
            }
        }

        return result;
    }

    private static int findMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            max = Math.max(max, num);
        }
        return max;
    }

    private static int findMin(int[] arr) {
        int min = arr[0];
        for (int num : arr) {
            min = Math.min(min, num);
        }
        return 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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * 计数排序的高级优化
 */
public class CountingSortAdvanced {

    /**
     * 内存优化版本：处理大范围稀疏数据
     * 使用HashMap替代数组，节省内存
     */
    public static int[] countingSortSparse(int[] arr) {
        if (arr.length == 0) return arr;

        Map<Integer, Integer> countMap = new HashMap<>();

        // 统计每个元素出现次数
        for (int num : arr) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }

        // 获取所有不同的值并排序
        List<Integer> uniqueValues = new ArrayList<>(countMap.keySet());
        Collections.sort(uniqueValues);

        // 重建排序结果
        int[] result = new int[arr.length];
        int index = 0;

        for (int value : uniqueValues) {
            int count = countMap.get(value);
            for (int i = 0; i < count; i++) {
                result[index++] = value;
            }
        }

        return result;
    }

    /**
     * 多线程版本的计数排序
     * 适用于大数据量的情况
     */
    public static int[] countingSortParallel(int[] arr) throws InterruptedException {
        if (arr.length == 0) return arr;

        int max = Arrays.stream(arr).max().orElse(0);
        int min = Arrays.stream(arr).min().orElse(0);
        int range = max - min + 1;

        // 使用原子整数数组保证线程安全
        AtomicIntegerArray count = new AtomicIntegerArray(range);

        // 并行统计
        Arrays.stream(arr).parallel().forEach(num ->
            count.incrementAndGet(num - min));

        // 重建结果
        int[] result = new int[arr.length];
        int index = 0;

        for (int i = 0; i < range; i++) {
            int cnt = count.get(i);
            while (cnt > 0) {
                result[index++] = i + min;
                cnt--;
            }
        }

        return result;
    }
}

🪣 桶排序（Bucket Sort）

桶排序将数据分布到多个桶中，对每个桶单独排序，最后合并所有桶。

基本原理

桶排序的思想是：将数据分散到有限数量的桶里，然后对每个桶分别排序。

  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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
/**
 * 桶排序实现
 * 时间复杂度：平均O(n + k)，最坏O(n²)
 * 空间复杂度：O(n + k)
 * 稳定性：取决于桶内排序算法
 */
public class BucketSort {

    /**
     * 基础桶排序（适用于浮点数）
     * @param arr 待排序数组（假设元素在[0, 1)范围内）
     * @param bucketCount 桶的数量
     */
    public static double[] bucketSortBasic(double[] arr, int bucketCount) {
        if (arr.length == 0) return arr;

        System.out.println("原数组: " + Arrays.toString(arr));
        System.out.println("桶数量: " + bucketCount);

        // 创建桶
        List<List<Double>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将元素分配到桶中
        for (double num : arr) {
            int bucketIndex = (int) (num * bucketCount);
            if (bucketIndex >= bucketCount) bucketIndex = bucketCount - 1; // 处理边界情况
            buckets.get(bucketIndex).add(num);
        }

        // 显示桶的分布
        for (int i = 0; i < bucketCount; i++) {
            if (!buckets.get(i).isEmpty()) {
                System.out.println("桶 " + i + ": " + buckets.get(i));
            }
        }

        // 对每个桶进行排序
        for (List<Double> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 合并所有桶
        double[] result = new double[arr.length];
        int index = 0;

        for (List<Double> bucket : buckets) {
            for (double num : bucket) {
                result[index++] = num;
            }
        }

        System.out.println("排序结果: " + Arrays.toString(result));
        return result;
    }

    /**
     * 通用桶排序（适用于任意范围的数据）
     */
    public static int[] bucketSortGeneral(int[] arr, int bucketCount) {
        if (arr.length == 0) return arr;

        int max = Arrays.stream(arr).max().orElse(0);
        int min = Arrays.stream(arr).min().orElse(0);
        int range = max - min + 1;

        System.out.println("数据范围: [" + min + ", " + max + "]");

        // 创建桶
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将元素分配到桶中
        for (int num : arr) {
            int bucketIndex = (int) ((long) (num - min) * bucketCount / range);
            if (bucketIndex >= bucketCount) bucketIndex = bucketCount - 1;
            buckets.get(bucketIndex).add(num);
        }

        // 显示桶的分布
        for (int i = 0; i < bucketCount; i++) {
            if (!buckets.get(i).isEmpty()) {
                System.out.println("桶 " + i + ": " + buckets.get(i));
            }
        }

        // 对每个桶进行排序
        for (List<Integer> bucket : buckets) {
            Collections.sort(bucket);
        }

        // 合并所有桶
        int[] result = new int[arr.length];
        int index = 0;

        for (List<Integer> bucket : buckets) {
            for (int num : bucket) {
                result[index++] = num;
            }
        }

        return result;
    }

    /**
     * 自适应桶排序
     * 根据数据分布自动调整桶的数量
     */
    public static int[] bucketSortAdaptive(int[] arr) {
        if (arr.length <= 1) return arr;

        // 计算数据的方差来决定桶的数量
        double mean = Arrays.stream(arr).average().orElse(0);
        double variance = Arrays.stream(arr)
                                .mapToDouble(x -> (x - mean) * (x - mean))
                                .average().orElse(0);

        // 根据方差调整桶的数量
        int bucketCount = Math.max(1, Math.min(arr.length, (int) Math.sqrt(variance) + 1));

        System.out.println("自适应桶数量: " + bucketCount +
                         " (基于方差: " + String.format("%.2f", variance) + ")");

        return bucketSortGeneral(arr, bucketCount);
    }

    /**
     * 桶排序应用：排序学生成绩
     */
    public static class GradeDistribution {

        public static void analyzeGrades(int[] grades) {
            System.out.println("成绩分析:");
            System.out.println("原始成绩: " + Arrays.toString(grades));

            // 按成绩等级分桶：0-59(F), 60-69(D), 70-79(C), 80-89(B), 90-100(A)
            List<List<Integer>> gradeBuckets = new ArrayList<>();
            String[] gradeLabels = {"F(0-59)", "D(60-69)", "C(70-79)", "B(80-89)", "A(90-100)"};

            for (int i = 0; i < 5; i++) {
                gradeBuckets.add(new ArrayList<>());
            }

            // 分配成绩到对应等级桶
            for (int grade : grades) {
                int bucketIndex = Math.min(grade / 10 - 6, 4);
                if (grade < 60) bucketIndex = 0;
                else if (bucketIndex < 0) bucketIndex = 0;
                else if (bucketIndex > 4) bucketIndex = 4;

                gradeBuckets.get(bucketIndex).add(grade);
            }

            // 统计和显示分布
            for (int i = 0; i < 5; i++) {
                List<Integer> bucket = gradeBuckets.get(i);
                Collections.sort(bucket);
                System.out.println(gradeLabels[i] + ": " + bucket.size() + "人 " + bucket);
            }

            // 合并排序结果
            List<Integer> sortedGrades = new ArrayList<>();
            for (List<Integer> bucket : gradeBuckets) {
                sortedGrades.addAll(bucket);
            }

            System.out.println("排序后成绩: " + sortedGrades);
        }
    }
}

🔢 基数排序（Radix Sort）

基数排序通过逐位排序来实现整体排序，是一种多轮稳定排序的组合。

基本原理

基数排序的核心思想是：从最低位开始，依次对每一位进行稳定排序。

  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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
/**
 * 基数排序实现
 * 时间复杂度：O(d × (n + k))，d是位数，k是基数
 * 空间复杂度：O(n + k)
 * 稳定性：稳定
 */
public class RadixSort {

    /**
     * LSD基数排序（最低位优先）
     * 适用于整数排序
     */
    public static int[] radixSortLSD(int[] arr) {
        if (arr.length == 0) return arr;

        // 找到最大值，确定位数
        int max = Arrays.stream(arr).max().orElse(0);
        int digits = getDigits(max);

        System.out.println("原数组: " + Arrays.toString(arr));
        System.out.println("最大值: " + max + ", 位数: " + digits);

        int[] result = arr.clone();

        // 从个位开始，依次对每一位进行计数排序
        for (int digit = 0; digit < digits; digit++) {
            result = countingSortByDigit(result, digit);
            System.out.println("第 " + (digit + 1) + " 位排序后: " + Arrays.toString(result));
        }

        return result;
    }

    /**
     * 对指定位进行计数排序
     * @param arr 待排序数组
     * @param digit 位数（0表示个位，1表示十位，以此类推）
     */
    private static int[] countingSortByDigit(int[] arr, int digit) {
        int[] count = new int[10]; // 0-9十个数字
        int[] result = new int[arr.length];

        // 计算10^digit
        int divisor = (int) Math.pow(10, digit);

        // 统计每个数字在指定位上的出现次数
        for (int num : arr) {
            int digitValue = (num / divisor) % 10;
            count[digitValue]++;
        }

        // 计算累计计数
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 从右向左构建排序结果（保证稳定性）
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            int digitValue = (num / divisor) % 10;
            result[count[digitValue] - 1] = num;
            count[digitValue]--;
        }

        return result;
    }

    /**
     * MSD基数排序（最高位优先）
     * 适用于字符串排序等场景
     */
    public static int[] radixSortMSD(int[] arr) {
        if (arr.length == 0) return arr;

        int max = Arrays.stream(arr).max().orElse(0);
        int digits = getDigits(max);

        System.out.println("MSD基数排序 - 最大值: " + max + ", 位数: " + digits);

        int[] result = arr.clone();
        radixSortMSDHelper(result, 0, result.length - 1, digits - 1);

        return result;
    }

    /**
     * MSD基数排序递归辅助函数
     */
    private static void radixSortMSDHelper(int[] arr, int left, int right, int digit) {
        if (left >= right || digit < 0) return;

        int divisor = (int) Math.pow(10, digit);

        // 使用计数排序对当前位进行排序
        int[] count = new int[11]; // 0-9 + 一个哨兵
        int[] aux = new int[right - left + 1];

        // 统计计数
        for (int i = left; i <= right; i++) {
            int digitValue = (arr[i] / divisor) % 10;
            count[digitValue + 1]++;
        }

        // 计算累计计数
        for (int i = 0; i < 10; i++) {
            count[i + 1] += count[i];
        }

        // 分配元素
        for (int i = left; i <= right; i++) {
            int digitValue = (arr[i] / divisor) % 10;
            aux[count[digitValue]++] = arr[i];
        }

        // 复制回原数组
        for (int i = left; i <= right; i++) {
            arr[i] = aux[i - left];
        }

        // 递归处理每个数字组
        for (int i = 0; i < 10; i++) {
            int start = left + count[i] - count[i + 1] + count[i];
            int end = left + count[i + 1] - 1;
            radixSortMSDHelper(arr, start, end, digit - 1);
        }
    }

    /**
     * 字符串基数排序
     * 按字典序排序定长字符串
     */
    public static String[] radixSortStrings(String[] strings, int maxLength) {
        if (strings.length == 0) return strings;

        System.out.println("字符串基数排序:");
        System.out.println("原数组: " + Arrays.toString(strings));

        String[] result = strings.clone();

        // 从右向左（从最低位开始）对每个字符位置进行排序
        for (int pos = maxLength - 1; pos >= 0; pos--) {
            result = countingSortByChar(result, pos);
            System.out.println("位置 " + pos + " 排序后: " + Arrays.toString(result));
        }

        return result;
    }

    /**
     * 按指定字符位置进行计数排序
     */
    private static String[] countingSortByChar(String[] strings, int pos) {
        int[] count = new int[257]; // ASCII + 1 (用于处理字符串长度不足的情况)
        String[] result = new String[strings.length];

        // 统计每个字符的出现次数
        for (String str : strings) {
            char ch = pos < str.length() ? str.charAt(pos) : 0; // 短字符串用0补齐
            count[ch + 1]++;
        }

        // 计算累计计数
        for (int i = 0; i < 256; i++) {
            count[i + 1] += count[i];
        }

        // 构建排序结果
        for (String str : strings) {
            char ch = pos < str.length() ? str.charAt(pos) : 0;
            result[count[ch]++] = str;
        }

        return result;
    }

    /**
     * 负数基数排序
     * 处理包含负数的数组
     */
    public static int[] radixSortWithNegatives(int[] arr) {
        if (arr.length == 0) return arr;

        // 分离正数和负数
        List<Integer> positives = new ArrayList<>();
        List<Integer> negatives = new ArrayList<>();

        for (int num : arr) {
            if (num >= 0) {
                positives.add(num);
            } else {
                negatives.add(-num); // 转为正数处理
            }
        }

        // 分别排序
        int[] sortedPositives = radixSortLSD(positives.stream().mapToInt(i -> i).toArray());
        int[] sortedNegatives = radixSortLSD(negatives.stream().mapToInt(i -> i).toArray());

        // 合并结果：负数（逆序）+ 正数
        int[] result = new int[arr.length];
        int index = 0;

        // 负数部分（需要逆序并恢复负号）
        for (int i = sortedNegatives.length - 1; i >= 0; i--) {
            result[index++] = -sortedNegatives[i];
        }

        // 正数部分
        for (int num : sortedPositives) {
            result[index++] = num;
        }

        return result;
    }

    /**
     * 计算数字的位数
     */
    private static int getDigits(int num) {
        if (num == 0) return 1;
        int digits = 0;
        while (num > 0) {
            num /= 10;
            digits++;
        }
        return digits;
    }

    /**
     * 基数排序应用：排序IP地址
     */
    public static class IPAddressSorter {

        public static String[] sortIPAddresses(String[] ips) {
            System.out.println("IP地址排序:");
            System.out.println("原IP列表: " + Arrays.toString(ips));

            // 将IP地址转换为4个字节的整数数组
            int[][] ipInts = new int[ips.length][4];
            for (int i = 0; i < ips.length; i++) {
                String[] parts = ips[i].split("\\.");
                for (int j = 0; j < 4; j++) {
                    ipInts[i][j] = Integer.parseInt(parts[j]);
                }
            }

            // 从右到左对每个字节进行基数排序
            for (int bytePos = 3; bytePos >= 0; bytePos--) {
                ipInts = countingSortByIPByte(ipInts, bytePos);
            }

            // 转换回字符串格式
            String[] result = new String[ips.length];
            for (int i = 0; i < ips.length; i++) {
                result[i] = ipInts[i][0] + "." + ipInts[i][1] + "." +
                           ipInts[i][2] + "." + ipInts[i][3];
            }

            System.out.println("排序后IP: " + Arrays.toString(result));
            return result;
        }

        private static int[][] countingSortByIPByte(int[][] ips, int bytePos) {
            int[] count = new int[256]; // 0-255
            int[][] result = new int[ips.length][4];

            // 统计计数
            for (int[] ip : ips) {
                count[ip[bytePos]]++;
            }

            // 累计计数
            for (int i = 1; i < 256; i++) {
                count[i] += count[i - 1];
            }

            // 构建结果
            for (int i = ips.length - 1; i >= 0; i--) {
                int byteValue = ips[i][bytePos];
                result[count[byteValue] - 1] = ips[i];
                count[byteValue]--;
            }

            return result;
        }
    }
}

📊 线性排序算法对比分析

性能对比工具

  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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/**
 * 线性排序算法性能对比分析
 */
public class LinearSortingAnalyzer {

    /**
     * 算法适用性分析
     */
    public static class AlgorithmSuitability {

        public static void analyzeDataSuitability() {
            System.out.println("线性排序算法适用性分析");
            System.out.println("=".repeat(80));

            String[][] suitabilityTable = {
                {"算法", "时间复杂度", "空间复杂度", "适用数据", "限制条件", "稳定性"},
                {"计数排序", "O(n+k)", "O(k)", "整数，范围小", "k不能太大", "稳定"},
                {"桶排序", "O(n+k)", "O(n+k)", "均匀分布", "需要均匀分布", "看桶内算法"},
                {"基数排序", "O(d(n+k))", "O(n+k)", "整数，固定位数", "位数不能太多", "稳定"}
            };

            for (String[] row : suitabilityTable) {
                System.out.printf("%-12s %-12s %-12s %-15s %-15s %-10s%n",
                                row[0], row[1], row[2], row[3], row[4], row[5]);
            }
        }
    }

    /**
     * 不同数据分布下的性能测试
     */
    public static void benchmarkWithDifferentDistributions() {
        System.out.println("\n不同数据分布下的性能测试");
        System.out.println("=".repeat(60));

        int[] sizes = {1000, 10000, 100000};

        for (int size : sizes) {
            System.out.println("\n数据规模: " + size);
            System.out.println("-".repeat(40));

            // 测试均匀分布数据
            testUniformDistribution(size);

            // 测试正态分布数据
            testNormalDistribution(size);

            // 测试小范围整数
            testSmallRangeIntegers(size);
        }
    }

    private static void testUniformDistribution(int size) {
        System.out.println("均匀分布数据:");

        Random random = new Random(42);
        double[] uniformData = new double[size];
        for (int i = 0; i < size; i++) {
            uniformData[i] = random.nextDouble();
        }

        long start = System.nanoTime();
        BucketSort.bucketSortBasic(uniformData, (int) Math.sqrt(size));
        long bucketTime = System.nanoTime() - start;

        System.out.printf("  桶排序: %.2f ms%n", bucketTime / 1_000_000.0);
    }

    private static void testNormalDistribution(int size) {
        System.out.println("正态分布数据:");

        Random random = new Random(42);
        int[] normalData = new int[size];
        for (int i = 0; i < size; i++) {
            normalData[i] = (int) (random.nextGaussian() * 1000 + 5000);
            normalData[i] = Math.max(0, Math.min(10000, normalData[i]));
        }

        long start = System.nanoTime();
        BucketSort.bucketSortGeneral(normalData, (int) Math.sqrt(size));
        long bucketTime = System.nanoTime() - start;

        System.out.printf("  桶排序: %.2f ms%n", bucketTime / 1_000_000.0);
    }

    private static void testSmallRangeIntegers(int size) {
        System.out.println("小范围整数 (0-99):");

        Random random = new Random(42);
        int[] smallRangeData = new int[size];
        for (int i = 0; i < size; i++) {
            smallRangeData[i] = random.nextInt(100);
        }

        // 计数排序
        long start = System.nanoTime();
        CountingSort.countingSortBasic(smallRangeData.clone());
        long countingTime = System.nanoTime() - start;

        // 基数排序
        start = System.nanoTime();
        RadixSort.radixSortLSD(smallRangeData.clone());
        long radixTime = System.nanoTime() - start;

        System.out.printf("  计数排序: %.2f ms%n", countingTime / 1_000_000.0);
        System.out.printf("  基数排序: %.2f ms%n", radixTime / 1_000_000.0);
    }

    /**
     * 算法选择决策树
     */
    public static String selectOptimalAlgorithm(DataCharacteristics characteristics) {
        if (characteristics.isSmallRange && characteristics.dataType == DataType.INTEGER) {
            return "计数排序 - 整数范围小，最适合计数排序";
        }

        if (characteristics.isUniformlyDistributed) {
            return "桶排序 - 数据均匀分布，桶排序效果最佳";
        }

        if (characteristics.dataType == DataType.INTEGER && characteristics.hasFixedDigits) {
            return "基数排序 - 整数位数固定，基数排序稳定高效";
        }

        if (characteristics.dataType == DataType.STRING && characteristics.hasFixedLength) {
            return "基数排序 - 定长字符串，使用字符基数排序";
        }

        if (characteristics.needsStability) {
            return "归并排序 - 需要稳定性但数据不适合线性排序时的后备选择";
        }

        return "快速排序 - 通用情况下的最佳选择";
    }

    /**
     * 数据特征描述类
     */
    public static class DataCharacteristics {
        boolean isSmallRange;
        boolean isUniformlyDistributed;
        boolean hasFixedDigits;
        boolean hasFixedLength;
        boolean needsStability;
        DataType dataType;

        public DataCharacteristics(DataType dataType) {
            this.dataType = dataType;
        }
    }

    public enum DataType {
        INTEGER, FLOAT, STRING, OBJECT
    }
}

🧪 完整测试示例

  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
 96
 97
 98
 99
100
101
102
103
/**
 * 线性排序算法综合测试
 */
public class LinearSortingTest {
    public static void main(String[] args) {
        System.out.println("=== 线性排序算法综合测试 ===");

        testCountingSort();
        testBucketSort();
        testRadixSort();
        testSpecialApplications();
        LinearSortingAnalyzer.benchmarkWithDifferentDistributions();
    }

    private static void testCountingSort() {
        System.out.println("\n1. 计数排序测试:");

        // 基础测试
        int[] basicData = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("基础计数排序:");
        CountingSort.countingSortBasic(basicData);

        // 稳定性测试
        int[] stableData = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("\n稳定版计数排序:");
        int[] result = CountingSort.countingSortStable(stableData);
        System.out.println("结果: " + Arrays.toString(result));

        // 学生成绩排序
        CountingSort.Student[] students = {
            new CountingSort.Student(1, "Alice", 85),
            new CountingSort.Student(2, "Bob", 92),
            new CountingSort.Student(3, "Charlie", 85),
            new CountingSort.Student(4, "Diana", 78)
        };
        System.out.println("\n学生成绩排序:");
        CountingSort.Student[] sortedStudents = CountingSort.countingSortStudents(students);
        for (CountingSort.Student student : sortedStudents) {
            System.out.println(student);
        }
    }

    private static void testBucketSort() {
        System.out.println("\n2. 桶排序测试:");

        // 浮点数桶排序
        double[] floatData = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
        System.out.println("浮点数桶排序:");
        BucketSort.bucketSortBasic(floatData, 3);

        // 整数桶排序
        int[] intData = {29, 25, 3, 49, 9, 37, 21, 43};
        System.out.println("\n整数桶排序:");
        int[] result = BucketSort.bucketSortGeneral(intData, 4);
        System.out.println("结果: " + Arrays.toString(result));

        // 成绩分析
        int[] grades = {85, 92, 78, 96, 85, 89, 76, 91, 88, 94};
        System.out.println("\n成绩分析:");
        BucketSort.GradeDistribution.analyzeGrades(grades);
    }

    private static void testRadixSort() {
        System.out.println("\n3. 基数排序测试:");

        // LSD基数排序
        int[] lsdData = {170, 45, 75, 90, 2, 802, 24, 66};
        System.out.println("LSD基数排序:");
        int[] lsdResult = RadixSort.radixSortLSD(lsdData);
        System.out.println("最终结果: " + Arrays.toString(lsdResult));

        // 字符串排序
        String[] strings = {"abc", "def", "aba", "xyz", "aaa"};
        System.out.println("\n字符串基数排序:");
        String[] strResult = RadixSort.radixSortStrings(strings, 3);
        System.out.println("结果: " + Arrays.toString(strResult));

        // 负数排序
        int[] negativeData = {-5, 3, -2, 8, -1, 0, 7};
        System.out.println("\n包含负数的基数排序:");
        int[] negResult = RadixSort.radixSortWithNegatives(negativeData);
        System.out.println("结果: " + Arrays.toString(negResult));
    }

    private static void testSpecialApplications() {
        System.out.println("\n4. 特殊应用测试:");

        // IP地址排序
        String[] ips = {
            "192.168.1.1",
            "10.0.0.1",
            "192.168.1.100",
            "172.16.0.1",
            "192.168.0.1"
        };
        System.out.println("IP地址排序:");
        RadixSort.IPAddressSorter.sortIPAddresses(ips);

        // 算法选择建议
        System.out.println("\n算法选择建议:");
        LinearSortingAnalyzer.AlgorithmSuitability.analyzeDataSuitability();
    }
}

🎯 总结

线性排序算法通过利用数据的特殊性质，突破了比较排序 O(n log n) 的理论下界：

核心优势

时间复杂度优势：在适合的场景下达到 O(n) 线性时间
稳定性保证：大多数线性排序算法都是稳定的
预测性能：时间复杂度不依赖于输入数据的排列

适用场景

计数排序：整数排序，数值范围不大
桶排序：数据均匀分布，浮点数排序
基数排序：整数排序，位数固定，字符串排序

使用建议

数据分析先行：了解数据的分布特征和范围
权衡空间时间：线性排序通常需要额外空间
稳定性考虑：某些应用场景稳定性很重要
实际测试验证：理论分析要结合实际数据验证

线性排序算法展示了算法设计中"以空间换时间"和"利用问题特性"的重要思想。掌握这些算法不仅能解决特定的排序问题，更能帮你培养分析问题特征、设计专用算法的能力！

下一篇：《数据结构入门教程：排序优化技术详解与Java实现》

🚀 引言：突破比较排序的极限#

流程图表#

🔢 计数排序（Counting Sort）#

基本原理#

计数排序的优化版本#

🪣 桶排序（Bucket Sort）#

基本原理#

🔢 基数排序（Radix Sort）#

基本原理#

📊 线性排序算法对比分析#

性能对比工具#

🧪 完整测试示例#

🎯 总结#

核心优势#

适用场景#

使用建议#

🚀 引言：突破比较排序的极限

流程图表

🔢 计数排序（Counting Sort）

基本原理

计数排序的优化版本

🪣 桶排序（Bucket Sort）

基本原理

🔢 基数排序（Radix Sort）

基本原理

📊 线性排序算法对比分析

性能对比工具

🧪 完整测试示例

🎯 总结

核心优势

适用场景

使用建议