Java 计数排序算法
最后修改时间：2025 年 4 月 16 日
排序算法简介
算法是解决问题或执行计算的逐步过程。排序算法按特定顺序排列元素，通常是数字或按字典顺序排列。高效排序对于优化其他算法至关重要。
常见的排序算法包括
- 气泡排序
- 选择排序
- 插入排序
- 归并排序
- 快速排序
- 堆排序
- 计数排序
- 基数排序
计数排序概述
计数排序是一种基于非比较的排序算法，它通过计算每个元素出现的次数来进行排序。它的时间复杂度为 O(n + k)，其中 n 是元素的数量，k 是输入的范围。
当输入数据的范围 (k) 不明显大于元素数量 (n) 时，计数排序是高效的。它通常用作诸如基数排序之类的其他算法中的子程序。
计数排序实现
这是一个用于整数数组的计数排序的基本实现
CountingSort.java
package com.zetcode;
public class CountingSort {
public static void countingSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
// Find the maximum value to determine the range
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
// Initialize count array
int[] count = new int[max + 1];
// Store count of each element
for (int num : arr) {
count[num]++;
}
// Modify count array to store cumulative counts
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// Build the output array
int[] output = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// Copy the output array to original array
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("Original array: " + Arrays.toString(arr));
countingSort(arr);
System.out.println("Sorted array: " + Arrays.toString(arr));
}
}
此实现首先找到最大值以确定范围。然后，它计算每个元素出现的次数，计算累积计数，最后构建已排序的数组。
文本数据的计数排序
计数排序也可以适用于对字符串或字符进行排序。 这是一个对字符串中的字符进行排序的示例
CharCountingSort.java
package com.zetcode;
public class CharCountingSort {
public static String countingSort(String input) {
if (input == null || input.isEmpty()) {
return input;
}
char[] arr = input.toCharArray();
int n = arr.length;
// The number of possible ASCII characters
int range = 256;
int[] count = new int[range];
// Count occurrences of each character
for (char c : arr) {
count[c]++;
}
// Build the output string
int index = 0;
for (int i = 0; i < range; i++) {
while (count[i] > 0) {
arr[index++] = (char) i;
count[i]--;
}
}
return new String(arr);
}
public static void main(String[] args) {
String text = "counting sort example";
System.out.println("Original: " + text);
System.out.println("Sorted: " + countingSort(text));
}
}
此版本计算 ASCII 字符（范围 0-255），并按排序顺序重建字符串。请注意，它基于 ASCII 值进行排序，因此大写字母将出现在小写字母之前。
降序计数排序
要按降序排序，我们可以修改计数排序算法以从最高到最低处理计数
DescendingCountingSort.java
package com.zetcode;
public class DescendingCountingSort {
public static void countingSortDescending(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max - min + 1;
int[] count = new int[range];
int[] output = new int[arr.length];
// Count occurrences
for (int num : arr) {
count[num - min]++;
}
// Modify count for descending order
for (int i = count.length - 2; i >= 0; i--) {
count[i] += count[i + 1];
}
// Build output array
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
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("Original: " + Arrays.toString(arr));
countingSortDescending(arr);
System.out.println("Sorted (descending): " + Arrays.toString(arr));
}
}
此实现计算从最小值到最大值的范围。然后，它从最高到最低处理计数以实现降序排列。
计数排序与快速排序基准测试
让我们将计数排序与快速排序进行比较，以了解它们的性能特征。我们将使用不同的输入大小和范围进行测试。
SortBenchmark.java
package com.zetcode;
import java.util.Arrays;
import java.util.Random;
public class SortBenchmark {
public static void countingSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
// Find the maximum value to determine the range
int max = arr[0];
for (int num : arr) {
if (num > max) {
max = num;
}
}
// Initialize count array
int[] count = new int[max + 1];
// Store count of each element
for (int num : arr) {
count[num]++;
}
// Modify count array to store cumulative counts
for (int i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
// Build the output array
int[] output = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// Copy the output array to original array
System.arraycopy(output, 0, arr, 0, arr.length);
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
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[] sizes = {1000, 10000, 100000};
int[] ranges = {100, 1000, 10000};
for (int size : sizes) {
for (int range : ranges) {
System.out.printf("\nBenchmark - Size: %,d,
Range: %,d\n", size, range);
int[] arr1 = generateRandomArray(size, range);
int[] arr2 = Arrays.copyOf(arr1, arr1.length);
// Counting Sort
long start = System.nanoTime();
countingSort(arr1);
long end = System.nanoTime();
System.out.printf("Counting Sort: %.3f ms\n", (end - start) / 1e6);
// Quick Sort
start = System.nanoTime();
quickSort(arr2, 0, arr2.length - 1);
end = System.nanoTime();
System.out.printf("Quick Sort: %.3f ms\n", (end - start) / 1e6);
}
}
}
private static int[] generateRandomArray(int size, int range) {
Random random = new Random();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = random.nextInt(range);
}
return arr;
}
}
基准测试表明，当范围 (k) 相对于输入大小 (n) 较小时，计数排序表现更好。 对于更大的范围或范围未知的情况，快速排序通常表现更好。
何时使用计数排序
以下情况下，计数排序是理想的：
- 输入数据的范围 (k) 不明显大于元素数量 (n)
- 你需要一个稳定的排序（保持相等元素的相对顺序）
- 你要对整数数据或可以映射到整数的数据进行排序
以下情况下，避免使用计数排序：
- 范围相对于元素数量非常大
- 内存受限（因为它需要额外的空间）
- 排序浮点数（没有特殊处理）
来源
在本教程中，我们介绍了 Java 中的计数排序算法，包括用于按升序和降序排列的数字和文本数据的实现。 我们还将它的性能与快速排序进行了比较。
作者
列出所有Java教程。