好玩的网站列表

上述三种排序方法的时间复杂度均为线性，因此将其称为线性排序(Linear sort).之所以能做先线性的时间复杂度，是因为他们都不是基于比较的排序算法，并不涉及到元素之间的比较操作。

1. 桶排序 Bucket Sort

• 核心思想
  • 将排序的数据分到几个有序的桶当中，每个桶的数据再单独进行排序。桶内排完序之后，再将每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
• 分析
  • 如果要排序的数据为 n个，将其均匀分到m个桶当中，每个桶就有 k=n/m个元素。每个桶内部使用快排，时间复杂度为O(k*logk)
  • m个桶的时间复杂度就为O(n*log(n/m))
  • 当m的数量非常接近n的时候，那么log(n/m)就是一个非常小的常量，这时候桶排序的时间复杂度就接近O(n)了
• 优劣势
  • 对数据本身要求比较苛刻
  • 需要足够均匀，否则桶内排序就不是常量级的复杂度了
• 桶排序 适合在外部排序当中
  • 指数据存储在外部磁盘当中，数据量比较大，内存有限，无法将数据全部加载到内存当中
  • 顺序进行划分，挨个顺次放到内存当中

2. 计数排序 Counting Sort

类似于桶排序，但是每个桶里面存储的只是个数

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

3. 基数排序 Radix Sort

排10万个手机号码，从小到大来排序？

按照位来排，需要选用稳定性的算法来做。

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 stone2paul@gmail.com