本文共 1454 字,大约阅读时间需要 4 分钟。
import java.util.Arrays;/** * 计数排序,属于稳定排序 * 时间复杂度:代码1、2、4步都涉及遍历原始数列,运算量都是n,第3步遍历统计数列,运算量是m,所以总体运算量是m,所以总体的运算量是3n+m,去掉系数,时间复杂度是O(n+m) * 空间复杂度:如果不考虑结果数组,只考虑统计数组大小的划,空间复杂度是O(m) * 局限性: * 1、当数列最大和最小值差距过大时,并不适合使用计数排序(例如给出20个随机数,范围在0-1亿之间,这时如果使用计数排序需要使用长度为1亿的数组。不但浪费空间、时间复杂度也会提升) * 2、当数列不是整数时,也不适用于计数排序(消暑无法创建对应的统计数组) */public class CountSort { public static int[] countSort(int[] arr) { //1、得到数列的最大值和最小值,并算出差值d int min = arr[0]; int max = arr[0]; for (int i : arr) { if (i > max) { max = i; } if (i < min) { min = i; } } int d = max - min; //2、创建统计数组并统计对应元素的个数 int[] countArray = new int[d + 1]; for (int i : arr) { countArray[i - min]++; } //3、统计数组做变形,后面的元素等于前面元素之和.累加的原因:让统计数组存储的元素值,等于相应整数的最终排序位置序号 for (int i = 1; i < countArray.length; i++) { countArray[i] += countArray[i - 1]; } //4、倒序遍历原始数列,从统计数组找到正确位置,输出结果数组 int[] sortArray = new int[arr.length]; for (int i = arr.length-1; i >= 0; i--) { sortArray[countArray[arr[i] - min] - 1] = arr[i]; countArray[arr[i] - min] -- ; } return sortArray; } public static void main(String[] args) { int[] array = new int[]{95,94,91,98,99,90,99,93,91,92}; int[] sortArray = countSort(array); System.out.println(Arrays.toString(sortArray)); }}
转载地址:http://jqsvi.baihongyu.com/