线性排序算法总结

排序是程序设计中的最为基础也是最为重要的算法，从程序设计这一行业开始，便有了对排序的研究，至今到了人工智能大行其道的时代，算法科学家们对排序的探索仍未停止。这是因为计算机是处理信息的最为高效的工具，如何高效的处理信息则是计算机科学的重中之重，而要想高效的处理信息，就必须先对信息进行排序，因为各种高效率的信息检索必须要基于已排序的数据。

总的来说排序算法分为三大类：

常规排序，也称为低效排序，如冒泡排序，插入排序，选择排序等，复杂度是O(n²)，空间复杂度都为O(1)
高效排序，如谢尔排序，快速排序，归并排序，堆排序等，复杂度是O(nlogn)，空间复杂度一般为O(logn)
线性排序，或者叫做非比较排序，仅针对特定数据集（有固定范围的整数集合）有效，如计数排序，基数排序，桶排序等，复杂度是O(n)，但至少需要O(n)的空间复杂度

排序算法属于编程的基础，相关的文章一大把，集大成者有Yu神的十大排序从入门到入赘。今天重点整理一下线性排序算法。

计数排序

计数排序的核心思想是统计输入数组每个元素的频次，然后按照频次表的顺序把原始数据都输出出来。它的输入必须是一组有固定范围的整数，而且范围不应该太大，否则空间浪费严重。具体步骤如下：

找出输入数据的范围，即其最大值max，创建一个长度为max + 1的整数数组，这是频次数组freq
遍历输入数组，对其元素进行频次统计，也就是把元素当作频次数组的下标，来统计freq[arr[i]]++
遍历频次数组，按频次输出元素，得到的就是一个有序数组

伪码如下：

def countSort(arr):
  len = max(arr) + 1
  freq = [0] * len
  for x in arr:
      freq[x]++
  res = []
  for i in range(len):
      for k in range(freq[i]):
          res.append(i)
  return res

具有稳定特质的计数排序

默认的方法（上面描述）的是不稳定的，所谓排序的稳定性是指对于比较起来相等的两个元素能否在结果数组中保留它们在原数组的先后顺序。一般情况下，不需要稳定时也不用管。但当在其他地方使用计数排序时，如在基数排序中使用计数排序，那么稳定性就相当重要了。

如果想要稳定，就需要额外做些事情：要保证先放入的数先输出（在前面），后放的后输出（在后面），可以对频次数组求前缀和，然后遍历频次时是从后往前遍历，同时更新频次：

def stableCoutingSort(arr):
  n = len(arr)
  # find max to determine the range of input array
  len = max(arr) + 1
  freq = [0] * len
  # count the frequency
  for x in arr:
      freq[x]++
  # presum the frequency
  for i in range(1, len):
      freq[i] += frq[i - 1]
  # output by iterating backwardly
  out = [0] * n
  for i in range(n - 1, -1, -1):
      out[freq[arr[i]] - 1] = arr[i]
      freq[arr[i]]--
  return out

应用条件

需要十分注意，计数排序可应用的条件很严格，只有数据集是范围不大的正整数时才可以使用，要不然空间浪费严重。最适合应用计数排序的场景是数组数值范围很小，但元素数量很多，也就是说元素数量远大于数值范围，比如说基数排序中，针对每一数位排序时，就是典型应用计数排序的地方，这时数值范围只有0~9，元素数量可能很多，非常适合计数排序。

当然，有负数时也可以使用，这时需要把数据加上最小的负数，平移到0以后就可以了，比如最小值（负数）是min，那么转化为arr[i]-min即可。

基数排序是以整数数制的数位为依据来排序，比如123，一共有3个数位分别是1，2和3。把数组中的每个元素都按照它们的每一个数位进行排序，之后即是结果，可以从低位到位的顺序（右到左），也可以从高位到低位的顺序（左到右）。针对每个数位排元素时可以应用计数排序。但要是稳定版本的计数排序，比如{11, 23, 25}三个数，先按最低位排序后是{11, 23, 25}，这时再按十分位排序时，如果不稳定就可能会排出{11, 25, 23}这样的结果，因此需要稳定版本的排序。具体过程如下：

求出最大数位，或者说最宽的数，对于整数来说也就是找出最大值，然后求出其数位宽度width
对每个数位进行循环，循环次数就是width，每一轮就是针对一个数位排序，可以用稳定版本的计数排序
结束后就得到了结果

def radixSort(arr):
  n = len(arr)
  m = max(arr)
  width = 0
  base = 10
  while m != 0:
      width++
      m /= base
  out = [0] * n
  for i in range(width):
      freq = [0] * 10
      for x in arr:
          ridx = (x % base) / (base / 10)
          freq[ridx]++
      
      for j in range(1, 10):
          freq[j] += freq[j - 1]
      for j in range(n - 1, -1, -1):
          idx = (arr[j] % base) / (base / 10)
          out[freq[idx] - 1] = arr[j]
          freq[idx]--
      arr = out
      base *= 10
  
  return arr

复杂度和应用范围

跟三个变量有关，输入数组长度n，最大宽度width，以及数制数位的范围d，时间复杂度为O(width * (n + d))，对于常规整数来说d是10，而width顶多也就10左右（整数有范围的），都可忽略，因此时间复杂度是O(n)。空间复杂度也是O(n)。

基数排序可以应用于整数，对于有负数的情况，只需要把数平移到0以右就可以了。

另外，可以拓展到其他数制，比如16进制，8进制，甚至字符串也都可以。

桶排序

桶排序其实是分治，它的核心思想是把数据以一定的数据范围分成若干个桶，每个桶再应用其他的排序算法，然后再按照桶的顺序把桶里的数据接在一起就是结果了：

确定数值范围min, max和桶数量k，然后得到一些区间
以这些区间来把数据进行分桶
每个桶单独排序
以桶的顺序把结果连接在一起

def bucketSort(arr):
  n = len(arr)
  k = n / 4
  min = min(arr)
  max = max(arr)
  buckets = [[] for _ in range(k)]
  interval = (max - min) / (k - 1)
  for x in arr:
      bidx = int((x - min) / interval)
      buckets[bidx].append(x)
  
  for b in buckets:
      sort(b)
  out = []
  for b in buckets:
      out.extend(b)
  return out

复杂度与适用范围

复杂度取决于桶的个数k以及每个桶的排序方法，如果采用O(n²)，那么就会是O(n² / k)，如果采用O(nlogn)就会是O(nlog(n/k))，空间复杂度是O(n)。

需要注意，桶排序适用于浮点型，只要是数就可以。至于稳定性，则要看桶内排序算法的选择。

其实，如果是整数，无论范围是啥样的，都没有必要采用桶排序，因为桶排序的复杂度不会估于O(nlogn)的。而如果桶内再采用计数或者基数排序的话（假如输入的是整数数组）就相当于脱了裤子放屁，因为本可以不用分桶的，直接采用计数排序或者基数排序。

桶排序适用于数据在桶中分布较均匀的场景，这样性能会达到最优。因为如果桶分配的不均匀，假如某一个桶中集中了绝大部分数据，其他桶几乎没有，这跟不分桶有啥区别（就像一个极不平衡的二叉树一样）。

典型问题

题目	题解	说明
220. 存在重复元素 III	题解
	题解
	题解

总结

今天重点学习了三种非比较排序算法，都是线性复杂度的，但它们并不是普适的算法，都有着特定的应用场景。要深刻理解它的原理和适用范围，以在实际运用中能够根据实际的问题灵活选择。

对于整数集合而言，如果元数数量远大于其数值范围，那么就用计数排序；否则就用基数排序。

对于浮点数，可以考虑使用桶排序。

当然不可以死学，这些算法背后的核心思想也是可以用来解其他的题目的，比如桶的分治思想，以及像基数的以数位来处理问题的思想，可以拓展到字符排序等等。

稀有猿诉

十年磨一剑，历炼出锋芒，说话千百句，不如码二行。