排序算法之计数排序
程序员文章站
2022-04-16 16:30:47
思想: 计数排序,顾名思义,计算待排序元素中每个元素的数量来排序,用数组的下标作为元素,数组下标对应的值作为该元素出现的次数。实现逻辑:1、获取数组中的最大值来创建一个计数数组用于计数2、遍历待排序数组-----》计算每个元素出现的次数3、建立一个原数组长度的数组作为排序结果4、按计数数组的下标和值将结果放入结果数组import java.util.Arrays;public class CountSort { /** * 1、稳定排序 * 2、时间复杂度O(n...
思想: 计数排序,顾名思义,计算待排序元素中每个元素的数量来排序,用数组的下标作为元素,数组下标对应的值作为该元素出现的次数。
实现逻辑:
1、获取数组中的最大值来创建一个计数数组用于计数
2、遍历待排序数组-----》计算每个元素出现的次数
3、建立一个原数组长度的数组作为排序结果
4、按计数数组的下标和值将结果放入结果数组
5、优化: 假设待排序数组中元素最大100007,最小100000,那么其实我们只需要一个空间为7的数组即可
import java.util.Arrays;
public class CountSort {
/**
* 1、稳定排序
* 2、时间复杂度O(n+K)
* 3、非原地排序
* 4、空间复杂度O(K)
*/
public static void main(String[] args) {
int[] arr = new int[]{2,3,3,3,3,2,2,2,4,5,6,7,7,8,9,17};
int[] sortedArr = CountSort.countSort(arr);
System.out.println(Arrays.toString(sortedArr));
}
public static int[] countSort(int[] arr) {
// 1、获取数组中的最大值
int maxValue = arr[0];
int minValue = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > maxValue) {
maxValue = arr[i];
}
if (arr[i] < minValue) {
minValue = arr[i];
}
}
//2、创建大小合适的数组作为统计数组
int[] countdArr = new int[maxValue+1-minValue];
//3、遍历待排序数组统计
for (int i = 0; i < arr.length; i++) {
countdArr[arr[i]-minValue]++;
}
//4、遍历统计数组,输出结果
int index = 0;
int[] sortedArr = new int[arr.length];
for (int i= 0; i < countdArr.length; i++) {
for(int j = 0; j < countdArr[i]; j++) {
sortedArr[index++] = i + minValue;
}
}
return sortedArr;
}
}
本文地址:https://blog.csdn.net/H838071332/article/details/107684666