数据结构与算法(10)-排序(桶排序 计数排序 基数排序)

  1. 1. 桶排序 Bucket Sort
  2. 2. 计数排序 Counting Sort
  3. 3. 基数排序 Radix Sort

上述三种排序方法的时间复杂度均为线性,因此将其称为线性排序(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

文章标题:数据结构与算法(10)-排序(桶排序 计数排序 基数排序)

文章字数:649

本文作者:Leilei Chen

发布时间:2020-02-10, 01:55:16

最后更新:2020-02-10, 01:55:34

原始链接:https://www.llchen60.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-10-%E6%8E%92%E5%BA%8F-%E6%A1%B6%E6%8E%92%E5%BA%8F-%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F-%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏