CLRS笔记8，线性时间排序(counting、radix、bucket sort)

线性时间排序即时间复杂度为Θ(n)的排序，主要有计数排序、基数排序和桶排序
以前的排序都涉及到元素比较，称为比较排序，渐近最优的为merge sort和heap sort，时间复杂度为Θ(nlogn)
而这种排序都不是用比较的操作来排序，所以下届Θ(nlogn)对它们不适用

计数排序
1，假设数组a所有元素i满足1<=i<=k，建立数组b且初始值为0
2，读取数列每个元素，如果元素为i，则b[i]的值加一
3，遍历数组b，如果b[i]=j，就输出j次i，这样输出的序列就是已经排好序的
时间复杂度为Θ(n+k)，k为常数
计数排序适合所需排序的数组元素取值范围不大的情况，如果每个元素都不一样，则效率不高

def counting_sort(a)
  min = a.min
  max = a.max
  counts = Array.new(max-min+1, 0)

  a.each do |n|
    counts[n-min] += 1
  end

  (0...counts.size).map{|i| [i+min]*counts[i]}.flatten
end

基数排序
1，假设数组a所有元素i为十进制整数且位数不超过d位
2，递归对数组a的个位、十位、...、d位排序
当没位数字都界于1到k之间时，对n个d位数的每一位处理的时间为Θ(n+k)，共d次处理，所以时间复杂度为Θ(dn+dk)，d为常数
基数排序分LSD(Least significant digital)和MSD(Most significant digital)，前者从最低位开始排，后者从最高位开始排
LSD需要保持较低位的位置，而MSD则不需要
LSD排序图示：
数列内容：421 240 35 532 305 430 124
第1次分组
组0 240 430
组1 421
组2 532
组3
组4 124
组5 35 305
组6
组7
组8
组9
数列内容：240 430 421 532 124 35 305
第2次分组
组0 305
组1
组2 421 124
组3 430 532 35
组4 240
组5
组6
组7
组8
组9
数列内容：305 421 124 430 532 35 240
第3次分组
组0 35
组1 124
组2 240
组3 305
组4 421 430
组5 532
组6
组7
组8
组9
数列内容：35 124 240 305 421 430 532
LSD的Ruby代码实现：

def kth_digit(n, i)  # 求数字number的第kth位数字
  while(i > 1)
    n = n / 10
    i = i - 1
  end
  n % 10
end

def radix_sort(a)
  max = a.max  # 最大元素
  d = Math.log10(max).floor + 1  # 最大元素的位数

  (1..d).each do |i|
    tmp = []  # 分配10个桶
    (0..9).each do |j|
      tmp[j] = []
    end

    a.each do |n|
      kth = kth_digit(n, i)
      tmp[kth] << n  # 把元素放入桶中
    end
    a = tmp.flatten  # 把桶中元素串起来并放回原数组
  end
  return a
end

桶排序
1，假设数组a中的数字是平均分布的
2，把数组分组，放到一个个的桶中，然后对每个非空的桶排序
假设有n个数字，m个桶，平均每个桶有n/m个数字，整个算法的时间复杂度为Θ(n + m*(n/m)*log(n/m))=Θ(n+n*log(n/m))，当m接近n时复杂度接近Θ(n)
如果所有的数字都落在同一个桶中，就退化成比较排序了

def quick_sort(a)  # 快速排序
  (x=a.pop) ? quick_sort(a.select{|i| i <= x}) + [x] + quick_sort(a.select{|i| i > x}) : []
end

def first_number(n)  # 小数点后第1个数
  (n * 10).to_i
end

def bucket_sort(a)
  tmp = []  # 分配10个桶
  (0..9).each do |i|
    tmp[i] = []
  end
  
  a.each do |n|
    k = first_number(n)
    tmp[k] << n  # 把元素放入桶中
  end

  (0..9).each do |j|
    tmp[j] = quick_sort(tmp[j])  # 对每个桶快速排序
  end

  tmp.flatten
end

a = [0.75, 0.13, 0, 0.44, 0.55, 0.01, 0.98, 0.1234567]
p bucket_sort(a)

# Result: 
[0, 0.01, 0.1234567, 0.13, 0.44, 0.55, 0.75, 0.98]