前言:
如今兄弟们对“数据结构算法找最值的比较次数怎么求”大约比较讲究,咱们都想要分析一些“数据结构算法找最值的比较次数怎么求”的相关文章。那么小编也在网摘上搜集了一些关于“数据结构算法找最值的比较次数怎么求””的相关内容,希望大家能喜欢,小伙伴们一起来学习一下吧!目录
非比较类排序计数排序场景基数排序场景计数排序基数排序
非比较类排序
十大经典排序算法江山图
十大排序分类
终于来到了最后两个算法,非比较类的线性时间复杂度算法,计数排序和基数排序。上一篇也提到过,这几种排序算法理解起来都不难,时间、空间复杂度分析起来也很简单,但是对要排序的数据要求很苛刻,上一篇提到的桶排序就是适用于外部排序中,即所谓的外部排序就是数据存储在外部磁盘中,数据量比较大,内存有限,无法将数据全部加载到内存中。
计数排序其实是桶排序的一种特殊情况。当要排序的n个数据,所处的范围并不大的时候,比如最大值是k,我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的,省掉了桶内排序的时间。
计数排序场景
例如高考查分系统,系统会显示我们的成绩以及所在省的排名。如果你所在的省有50万考生,如何通过成绩快速排序得出名次呢?
❝
考生的满分是900分,最小是0分,这个数据的范围很小,所以我们可以分成901个桶,对应分数从0分到900分。根据考生的成绩,我们将这50万考生划分到 这901个桶里。桶内的数据都是分数相同的考生,所以并不需要再进行排序。我们只需要依次扫描每个桶,将桶内的考生依次输出到一个数组中,就实现了50万考生的排序。因为只涉及扫描遍历操作,所以时间复杂度是O(n)。
❞
计数排序的算法思想就是这么简单跟桶排序非常类似,只是桶的大小粒度不一样。
基数排序场景
假设我们有10万个手机号码,希望将这10万个手机号码从小到大排序,用什么方法快速排序?
❝
对于桶排序、计数排序,手机号码有11位,范围太大,显然不适合用这两 种排序算法。手机号码有这样的规律:假设要比较两个手机号码a,b的大小,如果在前面几位中,a手机号码已经比b手机号码大了,那后面的几位就不用看了。根据这个思路,先按照最后一位来排序手机号码,然后,再按照倒数第二位重新排序,以此类推,最后按照第一位重新排序。经过11次排序之后,手机号码就都有序了。
❞
这就是基数排序的算法思路,基数排序对要排序的数据是有要求的,需要可以分割出独立的“位”来比较,而且位之间有递进的关系,如果「a」数据的高位比「b」数据大,那剩下的低 位就不用比较了。除此之外,每一位的数据范围不能太大,要可以用线性排序算法来排序,否则,基数排序的时间复杂度就无法做到 O(n) 了。
计数排序算法思想
就是把数组元素值作为数组的下标,然后用一个临时数组统计该元素出现的次数,例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来,此时汇总起来是数据是有序的。
动图演示
计数排序
由图可知,计数排序需要开辟一个临时数组来存储,先遍历原数组一个个放入,然后再遍历临时数组一个个取出。
代码实现
public class CountSort { public static int[] countSort(int[] arr) { if (arr == null || arr.length < 2) { return arr; } int length = arr.length; int max = arr[0]; int min = arr[0]; // 数组的最大值与最小值 for (int i = 1; i < arr.length; i++) { if(arr[i] < min) { min = arr[i]; } if(max < arr[i]) { max = arr[i]; } } // 创建大小为max的临时数组 int[] temp = new int[max + 1]; // 统计元素i出现的次数 for (int i = 0; i < length; i++) { temp[arr[i]]++; } // 把临时数组统计好的数据汇总到原数组 int k = 0; for (int i = 0; i <= max; i++) { for (int j = temp[i]; j > 0; j--) { arr[k++] = i; } } return arr; } public static void main(String[] args) { int[] arr = {21,4,12,42,46,23,27,11,6,5,33,29,41,46,40,13,31}; arr = countSort(arr); System.out.print("数组排序之后:"); for (int i=0; i<arr.length; i++) { System.out.print(arr[i] + ","); } }}时间复杂度分析
O(n+k)
空间复杂度分析
O(n+k)
稳定性分析
稳定
适用条件
计数排序只能用在数据范围不大的场景中,如果数据范围「k」比要排序的数据「n」大很多,就不适合用计数排序了。而且,计数排序只能给非负整数排序,如果要排序的数据是其他类型的,要将其在不改变相对大小的情况下,转化为非负整数。
比如,还是拿考生这个例子。如果考生成绩精确到小数后一位,我们就需要将所有的分数都先乘以10,转化成整数,然后再放到9010个桶内。再比如,如果要排序的数据中有负数,数据的范围是[-1000, 1000],那我们就需要先对每个数据都加1000,转化成非负整数,因为数组的下边不可能是负数。
基数排序算法思想
分别以个,十,百...位上数字大小对数组进行排序,最后归纳汇总得到整体有序的数组。
动图演示
基数排序
这里的数最多两位数,少于两位数的比较十位数的时候,可以十位数补0比较:
第一遍是按照个位数排的,得到的数组是个位数有序;
第二遍再按照十位数排,得到的数组全部有序;
代码实现
import java.util.ArrayList;public class RadixSort { public static int[] radixSort(int[] arr) { if(arr == null || arr.length < 2) return arr; int n = arr.length; int max = arr[0]; // 最大值 for (int i = 1; i < n; i++) { if (max < arr[i]) { max = arr[i]; } } // 计算最大值是几位数 int num = 1; while (max / 10 > 0) { num++; max = max / 10; } // 创建10个桶 ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(10); //初始化桶 for (int i = 0; i < 10; i++) { bucketList.add(new ArrayList<Integer>()); } // 进行每一趟的排序,从个位数开始排 for (int i = 1; i <= num; i++) { for (int j = 0; j < n; j++) { // 获取每个数最后第 i 位是数组 int radio = (arr[j] / (int)Math.pow(10,i-1)) % 10; //放进对应的桶里 bucketList.get(radio).add(arr[j]); } //合并放回原数组 int k = 0; for (int j = 0; j < 10; j++) { for (Integer t : bucketList.get(j)) { arr[k++] = t; } //取出来合并了之后把桶清光数据 bucketList.get(j).clear(); } } return arr; } public static void main(String[] args) { int[] arr = {21,4,12,42,46,23,27,11,6,5,33,29,41,46,40,13,31}; arr = radixSort(arr); System.out.print("数组排序之后:"); for (int i=0; i<arr.length; i++) { System.out.print(arr[i] + ","); } }}时间复杂度分析
O(n*k),k代表桶的个数
空间复杂度分析
O(n+k),k代表桶的个数
稳定性分析
稳定。
适用条件
需要可以分割出独立的“位”来比较,而且位之间有递进的关系,如果「a」数据的高位比「b」数据大,那剩下的低位就不用比较了。除此之外,每一位的数据范围不能太大,要可以用线性排序算法来排序,否则,基数排序的时间复杂度就无法做到O(n)了。
欢迎点赞分享在看,关注公众号《阿甘的码路》看更多内容,有问题可以加我微信私我指正,各大平台也会同步只不过排版可能有些会不太一样~
参考资料: 极客算法训练营,数据结构与算法之美
标签: #数据结构算法找最值的比较次数怎么求