计数排序,java代码
时间: 2023-11-20 10:50:38 浏览: 25
好的,以下是计数排序的Java代码:
```
public static void countingSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int max = arr[0], min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
int[] count = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
arr[index++] = i + min;
count[i]--;
}
}
}
```
相关问题
桶排序和计数排序java
桶排序和计数排序是两种不同的排序算法。
桶排序的基本思想是将数组分到有限数量的桶里,再对每个桶中的元素进行排序,最后按照桶的顺序将元素依次列出来,形成有序序列。桶排序的时间复杂度取决于对每个非空桶进行排序时所选择的排序算法。当要排序的数据均匀分布时,桶排序可以达到线性时间复杂度。
计数排序是一种记录数据出现次数的排序算法。它的原理类似于桶排序,可以看作是一种特殊的桶排序算法。计数排序遍历序列,并将每个元素放入对应的桶中。然后按照桶的顺序将元素依次放回原来的序列中。计数排序是一种稳定的排序算法,适用于数据范围较小的情况。
对于Java语言,你可以使用以下代码实现桶排序和计数排序:
桶排序的Java实现代码示例:
```
public void bucketSort(int[] arr, int bucketSize) {
if (arr.length == 0) {
return;
}
// 寻找数组的最大值和最小值
int min = arr[0], max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
} else if (arr[i] > max) {
max = arr[i];
}
}
// 桶的数量
int bucketCount = (max - min) / bucketSize + 1;
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
buckets.add(new ArrayList<>());
}
// 将数组中的元素放入对应的桶中
for (int i = 0; i < arr.length; i++) {
int bucketIndex = (arr[i] - min) / bucketSize;
buckets.get(bucketIndex).add(arr[i]);
}
// 对每个桶中的元素进行排序,并放回原来的序列中
int index = 0;
for (int i = 0; i < bucketCount; i++) {
List<Integer> bucket = buckets.get(i);
Collections.sort(bucket);
for (int j = 0; j < bucket.size(); j++) {
arr[index++] = bucket.get(j);
}
}
}
```
计数排序的Java实现代码示例:
```
public void countingSort(int[] arr) {
if (arr.length == 0) {
return;
}
// 寻找数组的最大值和最小值
int min = arr[0], max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
} else if (arr[i] > max) {
max = arr[i];
}
}
// 计算数组中每个元素的出现次数
int[] counts = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
counts[arr[i] - min]++;
}
// 将计数数组中的元素依次放回原来的序列中
int index = 0;
for (int i = 0; i < counts.length; i++) {
while (counts[i] > 0) {
arr[index++] = i + min;
counts[i]--;
}
}
}
```
java 计数排序
好的,关于 Java 实现计数排序,可以按照以下步骤进行:
1. 找出待排序数组中的最大值和最小值。
2. 创建一个计数数组,长度为最大值和最小值之差加 1。
3. 遍历待排序数组,将每个元素出现的次数记录在计数数组中。
4. 遍历计数数组,将每个元素的值累加前面所有元素的值,得到每个元素在排序后数组中的位置。
5. 创建一个与待排序数组长度相同的结果数组,遍历待排序数组,根据计数数组中该元素的位置,将其放入结果数组中。
6. 返回结果数组。
以下是 Java 代码实现:
```java
public static int[] countingSort(int[] arr) {
int max = arr[0], min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
int[] count = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
count[arr[i] - min]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
int[] res = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
res[--count[arr[i] - min]] = arr[i];
}
return res;
}
```