算法系列之八 线性时间排序

这是“算法系列”的最后一篇,之后的算法不能和这个系列中的其他算法成体系,所以就不放在一个系列里了。

在之前介绍的算法中,算法排序和查找都依赖于数值的比较。这类算法被统称为“比较排序”。对于比较排序,有一个特征是:任何一个比较排序,在最坏的情况下都要经过 $ \Omega(nlgn) $ 次比较。

但是,有一些算法,通过运算确定元素顺序,而不是比较。这一类的算法在时间复杂度上可以达到$O(n)$,被称作 “线性时间排序”。

但是,线性时间排序,也会有一些特殊的缺陷,比如:空间占用多,对输入的分布要求高等。

下面我们详细来说下。

计数排序

计数排序的基本原理是,使用一个辅助数组,用来统计待排序的每一个元素和比其小的元素的数量,通过统计后的值,就可以知道当前的元素的位置了。

比如:当一个元素 $i$ 有3个值小于它,那么它排序后就应该在第4个位置上,需要注意的是,如果有重复的元素,需要特殊对待一下。

代码如下:

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
void counting_sort(int *a, int len, int max) {

/*
* 申请两个辅助的数组
* pos 用来存放元素应该放的位置
* a_copy 用来存放排序后的数组
*/
int *pos = (int*)malloc(sizeof(int) * (max + 1));
int *a_copy = (int*)malloc(sizeof(int) * len);

// 将数组初始化为 0
memset(pos, 0, sizeof(int) * (max + 1));

// 记录每个元素的数量
for (int i = 0; i < len; ++i) ++pos[a[i]];

// 将比每个元素小的元素数量和加入,作为位置信息
for (int i = 1; i <= max; ++i) pos[i] += pos[i - 1];

// 将元素放到该放的位置上
for (int i = len -1; i >= 0; ++i) {
// 这里 减1,是因为C语言的数组是以0开始的
a_copy[pos[a[i]]-1] = a[i];
--pos[a[i]];
}
// 将排序后的数组,拷贝回原数组
memcpy(a, a_copy, sizeof(int) * len);

free(pos);
free(a_copy);
}

可以看到,上面的排序完全没有用到比较。都是通过计算完成的。

上面的算法可以对数组$A[1..n]$, 元素数值范围在 $[0, k]$区间内的数组进行排序。其花费的时间代价如下:

  • 15行的循环所花时间为 $\Theta(n)$
  • 18行的循环所花时间为 $\Theta(k)$
  • 21~25行循环所花时间为 $\Theta(n)$

所以有,总的时间代价为 $\Theta(k+n)$;在实际中,当 $k=O(n)$ 时,一般采用计数算法,最后的复杂度为 $\Theta(n)$

对于 计数排序,有一个重要的特质,就是排序是稳定的。只要数据的长度和范围是固定的,不管数据的顺序和分布如何,它都是一个稳定的过程。这一点非常重要,后面的基数排序依赖于此。

基数排序

基数排序的基本原理是,对于一个$n$位的10进制数,我们对其从右到左每一位进行排序,当最高位排序完成之后,整个数组的排序就完成了。

15334667602393

上面说过了,计数排序在给定的范围内是稳定的,比如在这里,对于10进制数,范围都是在$[0,9]$。所以,用计数排序去给每一位排序是一个稳定的过程。

代码实现如下:

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
/*
* 这里对计数排序做了一小点改动
* 1. 去除了传入最大值的参数,改为了,取位的基数。因为,十进制每一位最大不超过9。
* 2. 添加了对于除数取余的动作
*/
void counting_sort(int *a, int len, int base) {

int pos[10] = {0};
int *a_copy = (int*)malloc(sizeof(int) * len);


for (int i = 0; i < len; ++i) ++pos[a[i] / base % 10];

for (int i = 1; i < 10; ++i) pos[i] += pos[i - 1];

for (int i = len-1; i >= 0; --i) {
int t = a[i] / base % 10;

a_copy[pos[t] - 1] = a[i];
--pos[t];
}

memcpy(a, a_copy, sizeof(int) * len);
free(a_copy);
}


void radix_sort(int *a, int len, int max) {

for(int base = 1; max/base > 0; base *= 10)
counting_sort(a, len, base);
}

根据上面的推导,给定 $n$个$d$位数,且取值范围在 $[0,k]$,则,基数排序使用了 $\Theta(n+k)$ 复杂度的稳定算法,那么,它可以在 $\Theta(d(n+k))$ 时间代价下排好序。当 $k=\Theta(n)$ 且 d为常数时,基数排序具有线性时间复杂度。

桶排序

桶排序大概的算法思路如下:

  1. 将待排序元素散列到一个数组中,数组每一个位置被称为一个桶
  2. 如果有元素被重复放入一个桶中,则使用链表将其相连
  3. 将每个桶中的元素排序
  4. 按数组顺序,将元素放回至原数列
  5. 排序完成

实现起来比较简单,代码如下:

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// 定义链表的结构体
typedef struct _node {

int data;
struct _node *next;

} Node;

// 向链表添加一个节点,在添加时,就排序
void add_node(Node *head, Node *n) {

if (head->next == NULL) {
head->next = n;
return;
}

Node *i = head->next;
Node *prev = head;

while (i != NULL) {

if (n->data <= i->data) {
prev->next = n;
n->next = i;
} else {
prev = i;
i = i->next;
}
}
}
// 释放链表
void free_list(Node *list, int len) {

for (int i = 0; i < len; ++i) {
Node *n = list[i].next;
Node *ptr = NULL;

while (n != NULL) {
ptr = n->next;
free(n);
n = ptr;
}
}
free(list);
}
// 初始化链表,头结点不存数据
void init_list(Node *list, int len){
for (int i = 0; i < len; ++i) {
list[i].next = NULL;
list[i].data = 0;
}
}

// 排序
void bucket_sort(int *a, int len, int max) {

// 下面两个参数用作散列,减少碰撞的次数
int base = max + 1;
int cap = len * 2;

Node* list = (Node*)malloc(sizeof(Node) * cap);
init_list(list, cap);

// 遍历数组,将元素放入到链表中
for(int i = 0; i < len; ++i){
Node* tmp = malloc(sizeof(Node));
tmp->next = NULL;
tmp->data = a[i];

// 简单的散列
int num = a[i] * cap / base;
add_node(&list[num], tmp);
}

// 按顺序从链表中取出数据,并放回到数组中
int j = 0;
for(int i = 0; i < cap; ++i) {

if(list[i].next != NULL) {
Node* h = list[i].next;

while(h != NULL){
a[j++] = h->data;
h = h->next;
}

}
}
// 清理链表
free_list(list, cap);

}

总结

上面的三种算法被统称为“线性时间排序”,其实我们可以看到,这三种算法为了满足其线性时间,在使用时,限制也是比较多的。

比如:计数排序,元素的值是不能太大的,否则占用的内存空间太可观了;基数排序虽然在时间复杂度上比较低,但是用到了很多除法和取余,这在一些机器上面是很耗时间的;桶排序,则需要元素尽量的接近于均匀分布。

所以,算法不一定一味的追求时间复杂度的高低。在很多时候,不同的事情上,使用不同的算法,因地制宜,才能得到好的效果。

reposkeeper wechat
关注微信公众号