做网站的属于什么,wordpress 导出用户,seo建站,电子商务专业介绍文章目录 计数排序和桶排序一、计数排序概念#xff1a;写法一#xff1a;写法二#xff1a; 二、桶排序概念代码 计数排序和桶排序 一、计数排序 时间复杂度#xff1a;空间复杂度#xff1a;稳定性#xff1a;稳定
概念#xff1a; 非基于比较的排序 计数排序又称为… 文章目录 计数排序和桶排序一、计数排序概念写法一写法二 二、桶排序概念代码 计数排序和桶排序 一、计数排序 时间复杂度空间复杂度稳定性稳定
概念 非基于比较的排序 计数排序又称为鸽巢原理是对哈希直接定址法的变形应用 1.统计相同元素出现的个数 2.根据统计的结果将序列回收到原来的序列中 计数排序使用的场景给出指定范围内的数据进行排序 使用场景一组集中在某个范围内的数据
写法一
通过遍历计数数组循环输出计数数组存的次数 1.遍历数组找到最小值最大值2.根据最大最小值申请一个计数数组3.遍历待排数组进行计数4.遍历计数数组进行输出 /*** 计数排序*无法保证稳定* param array*/public static void countSort2(int[] array) {//1.遍历数组找到最大值和最小值int MAX array[0];int MIN array[0];for (int i 1; i array.length; i) {if (array[i] MAX) {MAX array[i];}if (array[i] MIN) {MIN array[i];}}//2.根据最大最小值申请一个计数数组int len MAX - MIN 1;//长度int[] count new int[len];//3. 遍历待排数组进行计数for (int i 0; i array.length; i) {count[array[i] - MIN];}//4.遍历计数数组进行输出int index 0;//array数组新的下标for (int i 0; i count.length; i) {while (count[i] 0) {array[index] i MIN;//最小值求出真正的数count[i]--;index;}}}写法二
写定数组的大小用临时数组存储结构计算每个元素在排序后的数组中的最终位置根据计数数组将元素放到临时数组b中实现排序从后往前根据原来数组的内容在计数数组中找到要填写在b数组中的位置计数数组记录的不再是数字出现是次数而是应该在数组中存放的位置下标 /*** 计数排序*稳定* param array*/public static void countSort(int[] array) {int len array.length;final int MAX 256;//常量确定数组大小int[] c new int[MAX];//计数数组int[] b new int[MAX];//临时数组存放结果//统计每个元素的出现次进行计数for (int i 0; i len; i) {c[array[i]];// 将a[i]作为索引对应计数数组c中的位置加1}// 计算每个元素在排序后的数组中的最终位置for (int i 1; i MAX; i) {c[i] c[i - 1];// 计数数组中每个元素的值等于它前面所有元素的值之和}// 根据计数数组将元素放到临时数组b中实现排序for (int i len - 1; i 0; i--) {b[c[array[i]] - 1] array[i];// 将a[i]放入临时数组b中的正确位置c[array[i]]--;// 对应计数数组c中的位置减1确保相同元素能够放在正确的位置}// 将临时数组b中的元素复制回原数组a完成排序for (int i 0; i len; i) {array[i] b[i];}}
二、桶排序
概念
划分多个范围相同的区间每个子区间自排序最后合并 桶排序是计数排序的扩展版本计数排序每个桶只存储单一键值 桶排序 每个桶存储一定范围的数值确定桶的个数和范围 将待排序数组中的元素映射到各个对应的桶中对每个桶进行排序 最后将非空桶中的元素逐个放入原序列中 代码 public static void bucketSort(int[] array){// 计算最大值与最小值int max Integer.MIN_VALUE;int min Integer.MAX_VALUE;for(int i 0; i array.length; i){max Math.max(max, array[i]);min Math.min(min, array[i]);}// 计算桶的数量int bucketNum (max - min) / array.length 1;ArrayListArrayListInteger bucketArr new ArrayList(bucketNum);for(int i 0; i bucketNum; i){bucketArr.add(new ArrayListInteger());}// 将每个元素放入桶for(int i 0; i array.length; i){int num (array[i] - min) / (array.length);bucketArr.get(num).add(array[i]);}// 对每个桶进行排序for(int i 0; i bucketArr.size(); i){Collections.sort(bucketArr.get(i));}// 将桶中的元素赋值到原序列int index 0;for(int i 0; i bucketArr.size(); i){for(int j 0; j bucketArr.get(i).size(); j){array[index] bucketArr.get(i).get(j);}}}
点击移步博客主页欢迎光临~
