标签：复杂度 算法 考生 数组 线性 排序 数据

目录

• 线性排序算法介绍
• 桶排序（Bucket sort）
• 计数排序（Counting sort）
• 基数排序（Radix sort）
• 思考

线性排序算法介绍

1. 线性排序算法包括桶排序、计数排序、基数排序。
   因为这些排序算法的时间复杂度是线性的，所以我们把这类排序算法叫作线性排序
2. 线性排序算法的时间复杂度为O(n)。
3. 此3种排序算法都不涉及元素之间的比较操作，是非基于比较的排序算法。
4. 对排序数据的要求很苛刻，重点掌握此3种排序算法的适用场景。

桶排序（Bucket sort）

1. 算法原理：

• 核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序
• 桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

2. 时间复杂度：

• 如果要排序的数据有 n 个，我们把它们均匀地划分到m个桶内，
• 每个桶里就有k=n/m个元素。每个桶内部使用快速排序，时间复杂度为O(k * logk) 。
• m 个桶排序的时间复杂度就是 O(m * k * logk)，因为 k=n/m，所以整个桶排序的时间复杂度就是 O(n*log(n/m))。
• 当桶的个数 m 接近数据个数n时，log(n/m) 就是一个非常小的常量，这个时候桶排序的时间复杂度接近 O(n)。

3. 使用条件

• 要排序的数据需要很容易就能划分成m个桶，并且桶与桶之间有着天然的大小顺序。
• 数据在各个桶之间分布是均匀的。

3. 适用场景

• 桶排序比较适合用在外部排序中。
• 外部排序就是数据存储在外部磁盘且数据量大，但内存有限无法将整个数据全部加载到内存中。

4. 应用案例

• 需求描述：
  有10GB的订单数据，需按订单金额（假设金额都是正整数）进行排序
  但内存有限，仅几百MB

• 解决思路：
  扫描一遍文件，看订单金额所处数据范围，比如1元-10万元，那么就分100个桶。
  第一个桶存储金额1-1000元之内的订单，第二个桶存1001-2000元之内的订单，依次类推。

  每个桶对应一个文件，并按照金额范围的大小顺序编号命名（00，01，02，…，99）。
  将100个小文件依次放入内存并用快排排序。

  所有文件排好序后，只需按照文件编号从小到大依次读取每个小文件并写到大文件中即可。

• 注意点：若单个文件无法全部载入内存，则针对该文件继续按照前面的思路进行处理即可。

计数排序（Counting sort）

1. 算法原理

• 计数其实就是桶排序的一种特殊情况。
• 当要排序的n个数据所处范围并不大时，比如最大值为k，则分成k个桶
• 每个桶内的数据值都是相同的，就省掉了桶内排序的时间。

2. 应用案例:

• 需求描述：
  高考查分数系统,系统会显示我们的成绩以及所在省的排名。如果你所在的省有 50 万考生，如何通过成绩快速排序得出名次呢？
• 解决思路：
  考生的满分是900 分，最小是 0 分，这个数据的范围很小，所以我们可以分成 901 个桶，对应分数从 0 分到 900 分。根据考生的成绩，我们将这 50 万考生划分到这 901 个桶里。桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 50 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。

不过，为什么这个排序算法叫“计数”排序呢？“计数”的含义来自哪里呢？

假设只有 8 个考生，分数在 0 到 5 分之间。这 8 个考生的成绩我们放在一个数组 A[8]中，它们分别是：2，5，3，0，2，3，0，3。

考生的成绩从 0 到 5 分，我们使用大小为 6 的数组 C[6]表示桶，其中下标对应分数,不过，C[6]内存储的并不是考生，而是对应的考生个数。像我刚刚举的那个例子，我们只需要遍历一遍考生分数，就可以得到 C[6]的值。

从图中可以看出，分数为 3 分的考生有 3 个，小于 3 分的考生有 4 个，所以，成绩为 3 分的考生在排序之后的有序数组 R[8]中，会保存下标 4，5，6 的位置。

我们对 C[6]数组顺序求和，C[6]存储的数据就变成了下面这样子。C[k]里存储小于等于分数 k 的考生个数。

我们从后到前依次扫描数组 A。比如，当扫描到 3 时，我们可以从数组 C 中取出下标为 3 的值 7，也就是说，到目前为止，包括自己在内，分数小于等于 3 的考生有 7 个，也就是说 3 是数组 R 中的第 7 个元素（也就是数组 R 中下标为 6 的位置）。当 3 放入到数组 R 中后，小于等于 3 的元素就只剩下了 6 个了，所以相应的 C[3]要减 1，变成 6。

以此类推，当我们扫描到第 2 个分数为 3 的考生的时候，就会把它放入数组 R 中的第 6 个元素的位置（也就是下标为 5 的位置）。当我们扫描完整个数组 A 后，数组 R 内的数据就是按照分数从小到大有序排列的了。

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

计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

基数排序（Radix sort）

1. 算法原理（以排序10万个手机号为例来说明）

• 比较两个手机号码a，b的大小，如果在前面几位中a已经比b大了，那后面几位就不用看了。
• 借助稳定排序算法的思想，可以先按照最后一位来排序手机号码，然后再按照倒数第二位来重新排序，以此类推，最后按照第一个位重新排序。
• 经过11次排序后，手机号码就变为有序的了。
• 每次排序有序数据范围较小，可以使用桶排序或计数排序来完成。

2. 使用条件

• 要求数据可以分割独立的“位”来比较；
• 位之间由递进关系，如果a数据的高位比b数据大，那么剩下的地位就不用比较了；
• 每一位的数据范围不能太大，要可以用线性排序，否则基数排序的时间复杂度无法做到O(n)。

思考

1. 如何根据年龄给100万用户数据排序？

解答： 我们假设年龄的范围最小 1 岁，最大不超过 120 岁。我们可以遍历这 100 万用户，根据年龄将其划分到这 120 个桶里，然后依次顺序遍历这 120 个桶中的元素。这样就得到了按照年龄排序的 100 万用户数据。

标签：复杂度,算法,考生,数组,线性,排序,数据
From： https://www.cnblogs.com/xiayuxue/p/16630348.html