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

Dawnzhang

发布于 2018-12-05 10:46:01

5210

发布于 2018-12-05 10:46:01

文章被收录于专栏：Dawnzhang的开发者手册

前言

　　在高考结束以后，所有人都在等着成绩，政府部门面对几百万的数据，你知道他们是怎么算名次的么？上一次学到递归排序以及快排，确实，用他们可以实现，可是他们的时间复杂度最低都是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];
  }
}