详解Java常用排序算法-计数排序
需积分: 1 16 浏览量
2023-08-26
15:58:26
上传
评论
收藏 14KB DOCX 举报
计数排序（Counting Sort）
计数排序是一种非比较排序算法，它的基本思想是统计数组中每个元素出现的次数，然后根
据元素出现的次数依次将元素放入有序的数组中。
计数排序时间复杂度为 O(n+k)，其中 k 为待排序的元素的最大值。
import org.junit.jupiter.api.Assertions;
import java.util.Arrays;
public class Counting {
public static void countingSort(int[] arr) {
int n = arr.length;
// 取出数组中最大值
int max = getMax(arr);
int[] count = new int[max + 1];
// 统计每个元素出现的次数
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// 计算每个元素在有序序列中的位置
for (int i = 1; i <= max; i++) {
// 因为 count 包含了每个数据出现的次数，所以从小到大，逐个往前加得到
就是原数组中每个元素在有序序列中应有的位置
count[i] += count[i - 1];
}
// 输出有序序列
int[] sortedArr = new int[n];
for (int i = n - 1; i >= 0; i--) {
sortedArr[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
// 将有序序列复制回原数组
System.arraycopy(sortedArr, 0, arr, 0, n);
}
private static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
资源评论
