计数和基数排序

O(N)的排序算法也叫不比较的排序算法,它的思想源于桶排序,其中比较经典的两个例子计数排序和基数排序,它们的时间复杂度趋向于O(n)

你可能会纳闷,不比较也能排序?下面我们介绍一下这两种经典排序算法

计数排序

假如要给公司员工按身高排序。

  1. 我们知道员工身高大部分在160,180 之间,建立100~300一共200个桶。

  2. 遍历所有员工,按身高把员工放到匹配的桶中

  3. 分别倒出100~300号桶中的员工,这就是一个按身高排好序的序列。

基数排序

给下面序列 (124,220,044,120,334,666,001,099)排序,其中都为10进制数;

  1. 建立 0~9 共10个桶

  2. 根据上面数的个位,分别放到对应的桶中,比如124,个位是4,就放到4对应的桶中;

  3. 依次倒出所有数,再根据数的十位,分别放到对应的桶中;

  4. 依次倒出所有数,再根据数的百位,分别放到对应的桶中;

  5. 依次倒出所有的数,该序列就是从小到大的有序序列;

下面这个网站中可以给你一些好的桶排序的思想,如果有时间,不妨看一下图解
Bucket Sort
Counting Sort
Radix Sort