排序——桶排序、计数排序、基数排序

桶排序、计数排序、基数排序

桶排序:

核心思想（含计算时间复杂度）

1
2
3
4
5
6
7
1.将数据(假设n个)分到几个(假设m个)彼此有序的桶里 O(n) 

2.每个桶里的数据再单独进行快速排序 O(m * n/m * log(n/m)) = O(nlogn/m) 

3.桶内排完序后，再把每个桶里的数据，按照彼此顺序依次取出，组成的就是有序的 O(n)

4.从 O(nlog(n/m)) 到 O(n): 上面3步是相加，所以取最大值，T(nlog(n/m)) 当 log2(n/m) 中 n/m = 2 时，log2(2) = 1, 这时 T(n) = O(n)

使用条件：

桶排序对要排序数据的要求是非常苛刻的

1
2
3
4
5
1.要排序数据容易划分m个桶，桶之间有天然的大小关系 

2.数据在之间分布比较均匀 ,平均分配性好

使用场景：外部排序（外部存储，数据量大，内存有限）,比如10GB的数据，但内存只有几百MB,无法一次性加载

例子：订单数据按订单金额排序。

计数排序：

高考的成绩数据不存储mysql?,mysql直接排序不行吗，一定要拿出来作桶排序？或者mysql内部是用到了桶排序？

计数排序：

计数排序其实是桶排序的一种特殊情况，是一种稳定排序算法

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

比如，数据为精确到小数后一位，则数据*10转化为整数后排序，若数据范围是-1000~1000，则每个数据+1000转为非负整数

例子：高考排名次，900分，分901个桶。（实际上高考分数相同，依次比较小数点后的语文、数学、英语、理综成绩）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
2 5 3 0 2 3 0 3 


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

基数排序：

手机号排序

11位bigint数据能在 变量数据有没有区分32位和64位系统的说法，比如32位的bignit数据太大，可能溢出

基数排序的命门：下面（底层）的排序算法得是稳定的

基数排序对要排序的数据是有要求的：

1
2
3
1需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。

2除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了

例子：比如手机号码的排序

排序算法优化

1.快排时间复杂度就会退化为 O(n2)：

如果数据原来就是有序的或者接近有序的，每次分区点都选择最后一个数据，那快速排序算法就会变得非常糟糕，时间复杂度就会退化为O(n2)。这种O(n2)时间复杂度出现的主要原因还是因为我们分区点选得不够合理。

1
2
3
1三数取中法:我们从区间的首、尾、中间，分别取出一个数，然后对比大小，取这 3 个数的中间值作为分区点

2随机法:每次从要排序的区间中，随机选择一个元素作为分区点.概率上来说，间复杂度退化为最糟糕的 O(n<sup>2</sup>)的情况，出现的可能性不大。

快排递归，警惕堆栈溢出

1
2
3
1是限制递归深度。一旦递归过深，超过了我们事先设定的阈值，就停止递归

2通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程，这样就没有了系统栈大小的限制。

2.C 语言中 qsort()

1
2
3
qsort() 会优先使用归并排序来排序输入数据，需额外的内存空间，适合于小数据量的排序（1KB、2KB等），空间换时间

数据量比较大时，qsort() 会改为用快速排序算法来排序，比如100KB。其源码的采用的就是三数取中和手动模拟递归。快排的时，元素的个数 小于等于4时，采用插入排序（在小规模数据面前，O(n2) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长）

3.哨兵来简化代码，少做一些判断

序函数是非常常用、非常基础的函数，性能的优化要做到极致

以上学于极客时间，做的笔记