java数组计数排序
时间: 2023-11-20 15:52:21 浏览: 45
Java数组计数排序是一种简单的排序算法,它的基本思想是对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数,利用这一信息将x直接存放到最终的输出序列的正确位置上。具体实现步骤如下:
1. 找出待排序的数组中最大和最小的元素;
2. 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
3. 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
4. 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。
下面是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[] countArray = new int[max - min + 1];
for (int i = 0; i < arr.length; i++) {
countArray[arr[i] - min]++;
}
int index = 0;
for (int i = 0; i < countArray.length; i++) {
while (countArray[i] > 0) {
arr[index++] = i + min;
countArray[i]--;
}
}
}
```
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)