网站建设维护多少钱,重庆建设工程信息网怎么录入备案,wordpress注册字段,建设工程规范发布网站引言
计数排序是桶排序思想的一种具体实现#xff0c;针对一些具有特殊限制的样本数据#xff0c;如公司员工年龄#xff0c;那么样本数据本身就一定在0~200之间#xff0c;针对这样的数据#xff0c;使用从0到200 的桶数组#xff0c;桶的位置已经是有序的#xff0c;…引言
计数排序是桶排序思想的一种具体实现针对一些具有特殊限制的样本数据如公司员工年龄那么样本数据本身就一定在0~200之间针对这样的数据使用从0到200 的桶数组桶的位置已经是有序的只需要将对应年龄的数据放入对应的桶比如24岁的员工有10人那么就往 24 号桶中放10个数据。将所有员工年龄数据放入桶数组中后只需要再次将它们放回到原数组就可以实现排序了 一、代码实现 public static void countSort(int[] arr) {if (arr null || arr.length 2)return;// 找到数组中的最大值int max Integer.MIN_VALUE;for (int i 0; i arr.length; i) {max Math.max(max, arr[i]);}// 为了能够覆盖到最后一个值需要1int[] buckets new int[max 1];// 桶的下标记录数据桶中的元素记录数据数量for (int i 0; i arr.length; i) {buckets[arr[i]];}int i 0;// 循环桶数组for (int j 0; j buckets.length; j) {// 如果桶中有元素那么执行放回操作并递减直到取出所有元素while (buckets[j]-- 0) {// 桶下标代表数据本身因此直接以下标作为返回的数据arr[i] j;}}}
二、计数排序的时间复杂度
计数排序是多个循环操作的累加。
首先是遍历数组求得一个最大值来决定桶的个数时间复杂度是O(N)
然后是将所有元素计数到辅助的桶数组中时间复杂度是O(N);
随后通过遍历桶数组选出存有数据的桶并依次取出累计个数的元素并返回到原数组中虽然for循环嵌套了while循环但实际上while只是把桶中的元素全部取出其for while操作的次数一定等于元素个数N因此时间复杂度同样是O(N)。
所以最后得出计数排序的时间复杂度是 O(N) O(N) O(N) O(3N) 忽略倍数即为 O(N)。
