做推广赚钱的网站有哪些,高校校园网站建设的要求,恒丰建设集团有限公司 网站,wordpress提货下载大家好#xff0c;我是 方圆。本文介绍线性排序#xff0c;即时间复杂度为 O(n) 的排序算法#xff0c;包括桶排序#xff0c;计数排序和基数排序#xff0c;它们都不是基于比较的排序算法#xff0c;大家重点关注一下这些算法的适用场景。
桶排序
桶排序是分治策略的一…大家好我是 方圆。本文介绍线性排序即时间复杂度为 O(n) 的排序算法包括桶排序计数排序和基数排序它们都不是基于比较的排序算法大家重点关注一下这些算法的适用场景。
桶排序
桶排序是分治策略的一个典型应用。它通过设置一些具有大小顺序的桶每个桶对应一个数据范围将数据平均分配到各个桶中然后在每个桶内部分别执行排序最终按照桶的顺序将所有数据依次取出合并组成的序列就是有序的了如下图所示 桶排序的算法流程我将其分成三个步骤 初始化桶以范围为 0 - 49 的数据为例分为 5 个桶 分桶将要排序数组中的元素加入桶中 出桶该步骤需要在桶中完成排序后依次出桶合并 /*** 桶排序指定数据范围为0 - 49分桶为5个每10个数为一个桶*/public void sort(int[] nums) {// 声明5个桶ListArrayListInteger buckets new ArrayList();for (int i 0; i 5; i) {buckets.add(new ArrayList());}// 数组元素分桶intoBucket(buckets, nums);// 出桶outOfBucket(buckets, nums);}/*** 分桶*/private void intoBucket(ListArrayListInteger buckets, int[] nums) {for (int num : nums) {int bucketIndex num / 10;buckets.get(bucketIndex).add(num);}}/*** 出桶*/private void outOfBucket(ListArrayListInteger buckets, int[] nums) {// 出桶覆盖原数组值int numsIndex 0;for (ArrayListInteger bucket : buckets) {// 先排序 再出桶bucket.sort(Comparator.comparingInt(x - x));for (Integer num : bucket) {nums[numsIndex] num;}}}算法特性 空间复杂度O(n k) 自适应排序与桶划分情况和桶内使用的排序算法有关 稳定排序/非稳定排序与桶内使用的排序算法有关 非原地排序
桶排序比较适用于 外部排序所谓的外部排序就是数据存储在外部磁盘中数据量很大但是内存又有限无法将所有数据全部加载进来比如有 1G 的数据需要排序但是内存只有几百MB的情况。我们可以根据数据范围将其划分到 N 个桶中划分完成后每个桶的大小不超过可用内存大小对每个桶内的数据进行排序排序完成后生成 N 个小文件最后我们再将这 N 个小文件写入到一个大文件中即可。如果数据在某些范围内并不是均匀分布的话有些范围内的数据特别多那么这就需要我们再对其划分成更细粒度的桶直到满足内存的使用要求但是这样我们的桶就不是按照范围均匀划分的了。
计数排序
计数排序是桶排序的一种特殊情况只是它定义的“桶”的粒度更细每个桶中只包含一个单位范围的数字那么每个“桶”内的数值都是相等的。它适合数据范围不大但数据量很大的排序场景比如高考考生成绩排名86 万考生满分 750 分需要划分 751 个桶将这些考生的成绩划分到各个桶中后依次取出即可。
看到这里你可能会觉得这不就是桶排序吗计数排序的计数体现在哪里呢别急我们看下下面这个排序的例子简单起见假设有 8 个考生他们的分数为 [2, 5, 3, 0, 2, 3, 0, 3]分数范围为 0 ~ 5那么我们需要创建 6 个桶规定桶中保存的不是对应的元素而是对应分数元素出现的数量并根据分数将桶中的计数值累加如下图所示 我们先看分数 0 的桶它是该数据范围内最小的分数它的计数为 2根据计数值我们可以确定分数为 0 的两个元素占用该数据范围的前两个索引位置所以计数表示的是对应数值的索引位置。我们再看看其他的桶来验证一下可以发现分数 2 的桶计数也为 2但是前两个索引位置已经被分数 0 占用了呀分数 2 的计数应该是 4 才对所以我们还需要一步操作叠加前面分数出现的次数这样分数 2 的计数值便为 4可以发现计数值其实表示的是某数字占用的第 N 个索引如果我们想知道其中分数 2 的索引位置将计数值 4 进行减 1 即可即它的索引值为 3而且每取完某数字一次需要将该计数值减 1。排序流程如下 这样一步步操作完成之后最终数组是有序的。计数排序的代码如下 /*** 计数排序的计数体现在小于等于某个数出现的次数 - 1 即为该数在原数组排序后的位置*/public void sort(int[] nums) {if (nums.length 1) {return;}// 寻找数组中的最大值来以此定义max 1个桶int max Arrays.stream(nums).max().getAsInt();// 定义桶索引范围即数组值的最大范围每个桶中保存的是该数字出现的次数计数排序的计数概念出现int[] bucket new int[max 1];// 计算每个数的个数在桶中累加Arrays.stream(bucket).forEach(x - bucket[x]);// 依次累加桶中的数该数表示小于等于该索引值的数量for (int i 1; i bucket.length; i) {bucket[i] bucket[i - 1];}// 创建临时数组来保存排序结果值int[] res new int[nums.length];// 倒序遍历原数组不改变相同元素的相对顺序for (int i nums.length - 1; i 0; i--) {// 根据桶中的 计数 找出该数的索引int index bucket[nums[i]] - 1;// 根据索引在结果数组中赋值res[index] nums[i];// 该数分配完成后需要将桶中的计数-1bucket[nums[i]]--;}// 结果数组覆盖原数组System.arraycopy(res, 0, nums, 0, res.length);}基数排序
基数排序对待排序数据是有特殊要求的需要数据可以分割出独立的“位”并且位与位之间要有递进关系根据递进关系对每一位进行排序获得最终排序结果。
我们先来看一下使用基数排序处理 [3, 4, 100, 11, 33] 数组的过程 因为整数每位取数范围为 0 ~ 9所以创建了 10 个桶这 10 个桶已经有了从大到小的顺序。排序时从整数的个位开始到最高位终止排序的轮次为最大整数的位数在每轮排序中根据当前位数值大小入桶完成后再按顺序出桶最终结果即为排序结果。代码如下 private void sort(int[] nums) {if (nums.length 1) {return;}// 1. 整数的每位取值范围为 0-9因此需要创建10个桶QueueInteger[] buckets createBuckets();// 2. 获取基数排序的执行轮次int radixRounds getRadixRounds(nums);// 3. 根据执行轮次处理各个位eg: 第一轮处理个位...for (int round 1; round radixRounds; round) {for (int num : nums) {// 获取所在桶的索引int bucketIndex getBucketIndex(num, round);// 进桶buckets[bucketIndex].offer(num);}// 出桶赋值当前结果为根据当前位排序的结果int numsIndex 0;for (QueueInteger bucket : buckets) {while (!bucket.isEmpty()) {nums[numsIndex] bucket.poll();}}}}/*** 创建大小为10的数组作为桶每个桶都是一个队列*/SuppressWarnings(unchecked)private QueueInteger[] createBuckets() {QueueInteger[] buckets new Queue[10];for (int i 0; i buckets.length; i) {buckets[i] new LinkedList();}return buckets;}/*** 获取基数排序的执行轮次*/private int getRadixRounds(int[] nums) {return String.valueOf(Arrays.stream(nums).max().getAsInt()).length();}/*** 获取该数所在桶的索引*/private int getBucketIndex(int num, int round) {int bucketIndex 0;while (round ! 0) {bucketIndex num % 10;num / 10;round--;}return bucketIndex;}基数排序比较适用于数据范围比较大且位数相对均匀的数据排序比如排序手机号或者学号它的时间复杂度接近于 O(n)。 巨人的肩膀 《数据结构与算法之美》第 3.6 章 线性排序如何根据年龄给 100 万个用户排序 《Hello 算法》第 11.8、11.9 和 11.10 章 《算法导论》第 8 章 线性时间排序
