数据结构与算法学习笔记之为用于高考名次排序的排序算法

  在高考结束以后,所有人都在等着成绩,政府部门面对几百万的数据,你知道他们是怎么算名次的么?上一次学到递归排序以及快排,确实,用他们可以实现,可是他们的时间复杂度最低都是O(nlogn)。今天我们来看看有没有更快捷的排序方法?

正文   桶排序   原理:

将需要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行排序,排序完成,再将每个桶的数据都取出来,组成新的有序的数据。

  时间复杂度:

  排序的数据有n个,分在m个桶里,每一个桶就有k=n/m个元素,每个桶都进行快排,时间复杂度为O(k*lognk),m个桶时间复杂度就为O(m*k*lognk),因为k=n/m,所以整个桶排序的时间复杂度就O(n*log(n/m)),当桶的个数m接近n时,桶排序的时间复杂度接近O(n)

 

   局限性

   在桶排序的过程中,划分桶时,需要桶和桶之间有着天然的大小顺序,这样桶内元素排序完成以后就不需要在外部排序。

   数据在桶之间的分布是较均匀的。划分不均,桶内数据,有些太多,有些太小。时间复杂度就不是常量级的。

   适用环境:

  适用于外部排序中,外部排序就是数据存储在外部磁盘中,数据量比较大内存有限,无法将数据全部加载到内存中。假如我们有30G的数据,内存只有8G,怎么办,我们可以使用桶排序的思想,将30G的数据分成6份,每个桶数据都足够在内存中运行,依次排好序然后合并,就都是有序的。

 

  计数排序

 

  原理: 

例如有8个年龄不同的人,年龄范围为0-5之间,这8个人的考生的成绩,我们放在A[8]数组中,分别为2.5.3.0.2.3.0.3,我们分为6个桶,然后在新的数组B[6]中,遍历A数组,在B中存储对应年龄的个数。然后把数组B[6]数组,顺序求和,变成数组C[6].

B[6]数组:

数据结构与算法学习笔记之为用于高考名次排序的排序算法

C[6]数组:

 

数据结构与算法学习笔记之为用于高考名次排序的排序算法

 

后续求解如下图

数据结构与算法学习笔记之为用于高考名次排序的排序算法

  java代码实现:

// 计数排序,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]; } }

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wssjpx.html