现在个人做网站还能盈利,宁夏网站建设哪家好,杭州百度网站建设,网站内容上传冒泡、插入、选择 O(n^2) 基于比较 快排、归并 O(nlogn) 基于比较 计数、基数、桶 O(n) 不基于比较
桶排序–分区间桶快速排序#xff08;归并排序#xff08;稳定性#xff09;#xff09;–取出结果 计数排序#xff08;特殊的桶排序#xff09;–分单个桶…冒泡、插入、选择 O(n^2) 基于比较 快排、归并 O(nlogn) 基于比较 计数、基数、桶 O(n) 不基于比较
桶排序–分区间桶快速排序归并排序稳定性–取出结果 计数排序特殊的桶排序–分单个桶计数– 先统计计数再取出来实现排序 基数排序–在每个位上桶排序–
一、线性排序算法介绍
1.线性排序算法包括桶排序、计数排序、基数排序。 2.线性排序算法的时间复杂度为O(n)。 3.此3种排序算法都不涉及元素之间的比较操作是非基于比较的排序算法。 4.对排序数据的要求很苛刻重点掌握此3种排序算法的适用场景。
二、桶排序Bucket sort
1.算法原理 1将要排序的数据分到几个有序的桶里每个桶里的数据再单独进行快速排序。 2桶内排完序之后再把每个桶里的数据按照顺序依次取出组成的序列就是有序的了。 2.使用条件 1要排序的数据需要很容易就能划分成m个桶并且桶与桶之间有着天然的大小顺序。 2数据在各个桶之间分布是均匀的。 3.适用场景 1桶排序比较适合用在外部排序中。 2外部排序就是数据存储在外部磁盘且数据量大但内存有限无法将整个数据全部加载到内存中。 4.应用案例 1需求描述 有10GB的订单数据需按订单金额假设金额都是正整数进行排序 但内存有限仅几百MB 2解决思路 扫描一遍文件看订单金额所处数据范围比如1元-10万元那么就分100个桶。 第一个桶存储金额1-1000元之内的订单第二个桶存1001-2000元之内的订单依次类推。 每个桶对应一个文件并按照金额范围的大小顺序编号命名000102…99。 将100个小文件依次放入内存并用快排排序。 所有文件排好序后只需按照文件编号从小到大依次读取每个小文件并写到大文件中即可。 3注意点若单个文件无法全部载入内存则针对该文件继续按照前面的思路进行处理即可。
三、计数排序Counting sort
1.算法原理 1计数其实就是桶排序的一种特殊情况。 2当要排序的n个数据所处范围并不大时比如最大值为k则分成k个桶 3每个桶内的数据值都是相同的就省掉了桶内排序的时间。 2.代码实现 // 计数排序a是数组n是数组大小。假设数组中存储的都是非负整数。
public void countingSort(int[] a, int n) {if (n 1) return;// 查找数组中数据的范围int max a[0];for (int i 1; i n; i) {if (max a[i]) {max a[i];}}int[] c new int[max 1]; // 申请一个计数数组c下标大小[0,max]for (int i 0; i max; i) {c[i] 0;}// 计算每个元素的个数放入c中for (int i 0; i n; i) {c[a[i]];}// 依次累加for (int i 1; i max; i) {c[i] c[i-1] c[i];}// 临时数组r存储排序之后的结果int[] r new int[n];// 计算排序的关键步骤有点难理解for (int i n - 1; i 0; --i) {int index c[a[i]]-1;r[index] a[i];c[a[i]]--;}// 将结果拷贝给a数组for (int i 0; i n; i) {a[i] r[i];}
}案例分析 假设只有8个考生分数在0-5分之间成绩存于数组A[8] [25302303]。 使用大小为6的数组C[6]表示桶下标对应分数即012345。 C[6]存储的是考生人数只需遍历一边考生分数就可以得到C[6] [202301]。 对C[6]数组顺序求和则C[6][224778]c[k]存储的是小于等于分数k的考生个数。 数组R[8] [00223335]存储考生名次。那么如何得到R[8]的呢 从后到前依次扫描数组A比如扫描到3时可以从数组C中取出下标为3的值7也就是说到目前为止包括自己在内分数小于等于3的考生有7个也就是说3是数组R的第7个元素也就是数组R中下标为6的位置。当3放入数组R后小于等于3的元素就剩下6个了相应的C[3]要减1变成6。 以此类推当扫描到第二个分数为3的考生时就会把它放入数组R中第6个元素的位置也就是下标为5的位置。当扫描完数组A后数组R内的数据就是按照分数从小到大排列的了。 3.使用条件 1只能用在数据范围不大的场景中若数据范围k比要排序的数据n大很多就不适合用计数排序 2计数排序只能给非负整数排序其他类型需要在不改变相对大小情况下转换为非负整数比如如果考试成绩精确到小数后一位就需要将所有分数乘以10转换为整数。
四、基数排序Radix sort
1.算法原理以排序10万个手机号为例来说明 1比较两个手机号码ab的大小如果在前面几位中a已经比b大了那后面几位就不用看了。 2借助稳定排序算法的思想可以先按照最后一位来排序手机号码然后再按照倒数第二位来重新排序以此类推最后按照第一个位重新排序。 3经过11次排序后手机号码就变为有序的了。 4每次排序有序数据范围较小可以使用桶排序或计数排序来完成。 2.使用条件 1要求数据可以分割**独立的“位”**来比较(不够补‘0’) 2位之间由递进关系如果a数据的高位比b数据大那么剩下的地位就不用比较了 3每一位的数据范围不能太大要可以用线性排序否则基数排序的时间复杂度无法做到O(n)。
五、思考
1.如何根据年龄给100万用户数据排序 实际上根据年龄给 100 万用户排序就类似按照成绩给 50 万考生排序。我们假设年龄的范围最小 1 岁最大不超过 120 岁。我们可以遍历这 100 万用户根据年龄将其划分到这 120 个桶里然后依次顺序遍历这 120 个桶中的元素。这样就得到了按照年龄排序的 100 万用户数据。
2.对DaFBcAz这几个字符串进行排序要求将其中所有小写字母都排在大写字母前面但是小写字母内部和大写字母内部不要求有序。比如经过排序后为aczDFBA这个如何实现呢如果字符串中处理大小写还有数字将数字放在最前面又该如何解决呢 用两个指针a、ba指针从头开始往后遍历遇到大写字母就停下b从后往前遍历遇到小写字母就停下交换a、b指针对应的元素重复如上过程直到a、b指针相交。 对于小写字母放前面数字放中间大写字母放后面可以先将数据分为小写字母和非小写字母两大类进行如上交换后再在非小写字母区间内分为数字和大写字母做同样处理
笔记整理来源 王争 数据结构与算法之美
