|
桶排序、计数排序和基数排序这三种算法的时间复杂度都为 O ( n ) ，因此，它们也被叫作线性排序（Linear Sort）。之所以能做到线性，是因为这三个算法是非基于比较的排序算法，都不涉及元素之间的比较操作。
1. 桶排序（Bucket Sort）
1.1. 原理
核心思想是将要排序的数据分到几个有序的桶里，每个桶的数据再单独进行排序。桶内排完序后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
1.2. 时间复杂度分析
如果要排序的数据有 n 个，我们把它们均匀地划分到 m 个桶内，每个桶内就有 k = n/m 个元素。对每个桶内的数据进行快速排序，时间复杂度为 O ( k l o g k ) 。m 个桶排序时间复杂度就为 O ( m ? k l o g k ) = O ( n ? l o g n /m )。当桶的个数接近数据个数时，O ( l o g n /m ) 就是一个非常小的数，这个时候通排序的时间复杂度接近于 O ( n ) 。
1.3. 桶排序的适用条件
桶排序看起来很优秀，但事实上，桶排序对排序数据的要求是非常苛刻的。
首先，要排序的数据需要很容易就能划分为 m 个桶，并且桶与桶之间有着天然的大小顺序。
其次，数据在各个桶之间的分布是比较均匀的。
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据比较大而内存有限，无法将数据全部加载到内存中去。
1.4. 一个桶排序的实例
假如我们有 10 GB 的订单数据需要按照金额进行排序，但内存只有几百 MB ，这时候该怎么办呢？
我们先扫描一遍文件，确定订单金额的数据范围。
如果扫描后发现订单金额处于 1 万元到 10 万元之间，我们将所有订单按照金额划分到 100 个桶内，第一个桶数据范围为[1, 1000]，第二个桶数据范围为[1001, 2000]…，每个桶对应一个文件，同时将文件按照金额范围的大小顺序编号命名（如00、01、02…99）。
如果订单金额分布均匀，则每个文件包含大约 100 MB 的数据，我们可以将每个小文件读入到内存中，进行快速排序。然后，再按顺序从各个小文件读取数据，写入到另外一个文件，即是排序好的数据了。如果订单分布不均，某一范围内数据特别多无法一次读入内存，则可以继续对此区间再进行划分，直到所有的文件都可以读入内存为止。
2. 计数排序（Counting Sort）
2.1. 计数排序算法实现
public class DemoApplication {
public static void main(String[] args) {
int arr = new int[]{2, 5, 3, 0, 2, 3, 0, 3};
//计数排序
countingSort(arr);
for(int k = 0; k < arr.length; k++){
System.out.print(arr[k] + ",");
}
}
//计数排序
public static void countingSort(int[] arr) {
int[] count = new int[10];
for(int i = 0; i < arr.length; i++){
count[arr[i]]++;
}
for(int i = 1; i < count.length; i++){
count[i] += count[i - 1];
}
int[] t = new int[arr.length];
for(int i = arr.length - 1; i >= 0; i--){
t[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for(int i = 0; i < arr.length; i++){
arr[i] = t[i];
}
}
}
2.2. 计数排序的适用范围
计数排序只适用于数据范围不大的场景中，如果数据范围 K 比排序的数据 n 大很多，就不适合用计数排序了。
计数排序能给非负整数排序，如果数据是其他类型的，需要将其在不改变相对大小的情况下，转化为非负整数。比如数据有一位小数，我们需要将数据都乘以 10；数据范围为 [-1000, 1000]，我们需要对每个数据加 1000。
3. 基数排序（Radix Sort）
假设要对 10 万个手机号码进行排序，显然桶排序和计数排序都不太适合，那怎样才能做到时间复杂度为 O(n) 呢?
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
public class DemoApplication {
public static void main(String[] args) {
int arr[] = new int[]{50, 123, 543, 187, 49, 30, 0, 2, 11, 100};
//基数排序
arr = radixSort(arr);
for(int k = 0; k < arr.length; k++){
System.out.print(arr[k] + ",");
}
}
/**
* 获取数组最大位数
* @param arr
* @return
*/
public static int maxBit(int[] arr){
int max = arr[0];
for(int i = 1; i < arr.length; i++){
if(arr[i] > max){
max = arr[i];
}
}
int bit = 0;
if(max == 0){
bit = 1;
}else{
while(max > 0){
bit++;
max /= 10;
}
}
return bit;
}
/**
* 返回指定位数上的值
* @param num
* @param bit
* @return
*/
public static int digit(int num, int bit){
int pow = 1;
while(--bit > 0){
pow *= 10;
}
return num / pow % 10;
}
/**
* 基数排序
*/
public static int[] radixSort(int[] arr) {
int maxBit = maxBit(arr);
int count[] = new int[10];
int t[] = new int[arr.length];
for(int i = 1; i <= maxBit; i++){
for(int j = 0; j < count.length; j++){
count[j] = 0;
}
for(int j = 0; j < arr.length; j++){
count[digit(arr[j], i)]++;
}
for(int j = 1; j < count.length; j++){
count[j] += count[j - 1];
}
for(int j = arr.length - 1; j >= 0; j--){
t[--count[digit(arr[j], i)]] = arr[j];
}
for(int j = 0; j < arr.length; j++){
arr[j] = t[j];
}
}
return arr;
}
}
参考地址：排序算法(8) -- 桶排序、计数排序和基数排序_Dby_freedom的博客-CSDN博客
|