没有注册公司怎么做网站,长春有几个区,wordpress产品定制插件,wordpress重新生成标签1.桶排序
桶排序#xff0c;顾名思义#xff0c;会用到“桶”#xff0c;核心思想是将要排序的数据分到几个有 序的桶里#xff0c;每个桶内的数据再单独进行排序。桶内排完序之后#xff0c;再把每个桶内的数据按照顺序依次 取出#xff0c;组成的序列就是有序的了。
…1.桶排序
桶排序顾名思义会用到“桶”核心思想是将要排序的数据分到几个有 序的桶里每个桶内的数据再单独进行排序。桶内排完序之后再把每个桶内的数据按照顺序依次 取出组成的序列就是有序的了。
桶排序对要排序数据的要求是非常苛刻的。 首先要排序的数据需要很容易就能划分成m个桶并且桶与桶之间有着天然的大小顺序。这样 每个桶内的数据都排序完之后桶与桶之间的数据不需要再进行排序。
其次数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后有些桶内的数据非常 多有些非常少很不平均那桶内数据排序的时间复杂度就不是常量级了。在极端情况下如果 数据都被划分到一个桶内那就退化为O(nlogn)的排序算法了。
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中数据量比较大内 存有限无法将数据全部加载到内存中。
/*** 桶排序* 原地排序否* 稳定排序是* 空间复杂度* 时间复杂度O(n)*/
public class BucketSort {public static void main(String[] args) {int[] arr { 1, 45, 32, 23, 22, 31, 47, 24, 4, 15 };bucketSort(arr);System.out.println(Arrays.toString(arr));}//存数区间0-9,10-19,20-29,30-39,40-49public static void bucketSort(int[] arr) {ArrayList bucket[] new ArrayList[5];//初始化桶for(int i0;ibucket.length;i) {bucket[i] new ArrayListInteger();}//像桶内放入数据for(int i0;iarr.length;i) {int index arr[i]/10;bucket[index].add(arr[i]);}int index 0;for(int i0;ibucket.length;i) {bucket[i].sort(null);//对每个桶进行排序for(int j0;jbucket[i].size();j) {arr[index] (int) bucket[i].get(j);}}}
}2.计数排序
计数排序可以理解为是桶排序的一种特殊情况。当要排序的n个数据所处的范围并不大的 时候比如最大值是k我们就可以把数据划分成k个桶。每个桶内的数据值都是相同的省掉了桶 内排序的时间。
计数排序只能用在数据范围不大的场景中如果数据范围k比要排序的数据n大很多 就不适合用计数排序了。而且计数排序只能给非负整数排序如果要排序的数据是其他类型的 要将其在不改变相对大小的情况下转化为非负整数。 假定有原始数组A[8]它们分别是25302303。数据范围从0-5
先用一个数组大小为6的数组C来存储在k值上数据有几个。
接着对数组顺序求和C数组存储的数据就变成了C[k]里存储小于等于分数k的的数据。
定义临时数组R,依次扫描数组原始数组A将数据A入到R[C[k]]位置上同时C[k]位置上的数据要减掉1最后将R数组复制到原始数组A中。
/*** 计数排序* 原地排序否* 稳定排序是* 空间复杂度O(kn) k为数据范围大小* 时间复杂度O(nk)*/
public class CountSort {public static void main(String[] args) {int[] arr new int[]{5,3,1,3,2,8,6,9,10,4,6,4,8,10,7,4,2,1,6,7};CountingSort(arr,arr.length);System.out.println(Arrays.toString(arr));}public static void CountingSort(int[] a,int n) {if(n-1) return;//查找数组中最大值int max a[0];for(int i1;ia.length;i) {if(maxa[i]) {max a[i];}}//申请一个计数数组C下标为0到maxint[] c new int[max1];for(int i0;ic.length;i) {c[i] 0;}//计算每个元素的个数放入数组C中for(int i0;ia.length;i) {c[a[i]];}//依次累加for(int i0;imax;i) {c[i1] c[i]c[i1];}//临时数组R存储排序之后的数组int[] r new int[a.length];//计数排序的关键步骤for(int ia.length-1;i0;i--) {int index c[a[i]]-1;r[index] a[i];c[a[i]]--;}//将结果拷贝给a数组for(int i0;ia.length;i) {a[i] r[i];}}
}3.基数排序
先按照数据最后以位来排序然后再按照倒数第二位重新排序以此类推最后按照第一位重新排序。经过多次排序之后数据就都有序了。如果数据长度不一致需要补齐数据到相同长短。
基数排序对要排序的数据是有要求的需要可以分割出独立的“位”来比较而且位之间有递进的关系如果a数据的高位比b数据大那剩下的低位就不需要较了。除此之外每一位的数据范围不能太大才可以用线性排序算法来排序否则基数排序的时间复杂度就无法做到O(n)了。
/*** 基数排序* 原地排序否* 稳定排序是* 空间复杂度O(dn) k为数据范围大小* 时间复杂度O(dn) d是维数*/
public class RadixSort {public static void main(String[] args) {int[] arrs new int[] {153,26,78,342,123,241,96};int max getMaxData(arrs);for(int exp1;max/exp0;expexp*10) {CountingSort(arrs,arrs.length,exp);System.out.println(Arrays.toString(arrs));}}public static int getMaxData(int[] a) {//查找数组中最大值int max a[0];for(int i1;ia.length;i) {if(maxa[i]) {max a[i];}}return max;}public static void CountingSort(int[] a,int n,int exp) {if(n-1) return;//查找数组中最大值int max (a[0]/exp)%10;for(int i1;ia.length;i) {if(max(a[i]/exp)%10) {max (a[i]/exp)%10;}}//申请一个计数数组C下标为0到maxint[] c new int[max1];for(int i0;ic.length;i) {c[i] 0;}//计算每个元素的个数放入数组C中for(int i0;ia.length;i) {c[(a[i]/exp)%10];}//依次累加for(int i0;imax;i) {c[i1] c[i]c[i1];}//临时数组R存储排序之后的数组int[] r new int[a.length];//计数排序的关键步骤for(int ia.length-1;i0;i--) {int index c[(a[i]/exp)%10]-1;r[index] a[i];c[(a[i]/exp)%10]--;}//将结果拷贝给a数组for(int i0;ia.length;i) {a[i] r[i];}}}
