【排序】计数排序、桶排序与基数排序

一、计数排序(Counting Sort)

  计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。计数排序的时间复杂度为 O(n + m ),m指的是数据量,说的简单点,计数排序算法的时间复杂度约等于O(n),快于任何比较型的排序算法。

1.算法描述

  1. 找出待排序的数组中最大和最小的元素;

  2. 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;

  3. 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);

  4. 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

2.动图演示

3.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int[] countingSort(int[] arr) {
int maxValue = 0;
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}

int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];

for (int value : arr) {
bucket[value]++;
}

int sortedIndex = 0;
for (int i = 0; i < bucketLen; i++) {
while (bucket[i] > 0) {
arr[sortedIndex++] = i;
bucket[i]--;
}
}
return arr;
}

4.算法分析

  计数排序是一个稳定的排序算法。当输入的元素是 n 个 0 到 m 之间的整数时,时间复杂度是O(n+m),空间复杂度也是O(n+m),其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时,计数排序是一个很有效的排序算法。

二、桶排序(Bucket Sort)

  桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。

为了使桶排序更加高效,我们需要做到这两点:

  1. 在额外空间充足的情况下,尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。

什么时候最快?当输入的数据可以均匀的分配到每一个桶中。

什么时候最慢?当输入的数据被分配到了同一个桶中。

1.算法描述

  1. 设置一个定量的数组当作空桶;

  2. 遍历输入数据,并且把数据一个一个放到对应的桶里去;

  3. 对每个不是空的桶进行排序;

  4. 从不是空的桶里把排好序的数据拼接起来。

2.动图演示

3.代码实现

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
public static int[] bucketSort(int[] arr, int bucketSize){
if (arr.length == 0) {
return arr;
}

int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
//桶的数量
int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
int[][] buckets = new int[bucketCount][0];

//利用映射函数将数据分配到各个桶中
for (int i = 0; i < arr.length; i++) {
int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
buckets[index] = arrAppend(buckets[index], arr[i]);
}

int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
//对每个桶进行排序,这里使用了插入排序
InsertionSort.insertionSort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
return arr;
}
//自动扩容,并保存数据
public static int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}

  桶的数量我认为设置为原数组的长度是合理的,因为理想情况下每个数据装一个桶。

  数据入桶的映射算法其实是一个开放性问题。

  桶内排序为了方便起见使用了当前语言提供的排序方法,如果对于稳定排序有所要求,可以选择使用自定义的排序算法。

4.算法分析

  桶排序最好情况下使用线性时间O(n)。桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。

三、基数排序(Radix Sort)

  基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

  基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

  假设说,我们要对 100 万个手机号码进行排序,应该选择什么排序算法呢?排的快的有归并、快排时间复杂度是 O(nlogn)。计数排序和桶排序虽然更快一些,但是手机号码位数是11位,那得需要多少桶?内存条表示不服。这个时候,我们使用基数排序是最好的选择。

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

  • 计数排序:每个桶只存储单一键值
  • 桶排序:每个桶存储一定范围的数值
  • 基数排序:根据键值的每位数字来分配桶

1.算法描述

  1. 取得数组中的最大数,并取得位数;

  2. arr为原始数组,从最低位开始取每个位组成radix数组;

  3. 对radix进行计数排序(利用计数排序适用于小范围数的特点);

2.动图演示

3.代码实现

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public static void main(String[] args) {
int[] arr = {22,1,55,7,20};
int maxDigit = getMaxDigit(arr);
arr = radixSort(arr, maxDigit);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}

//获取最高位数
public static int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
//获取最大值
public static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
public static int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}

public static int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;

for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}

int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
//自动扩容,并保存数据
private static int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}

参考:

hustcc/JS-Sorting-Algorithm

1.0 十大经典排序算法

十大经典排序算法(动图演示)

这或许是东半球分析十大排序算法最好的一篇文章

(完)
谢谢你请我吃糖果!
0%