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

  • 2018-08-04
  • 113
  • 0

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

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

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

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

下面我们详细来说下。

计数排序

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

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

代码如下:

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进制数,我们对其从右到左每一位进行排序,当最高位排序完成之后,整个数组的排序就完成了。

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

代码实现如下:


/*
 * 这里对计数排序做了一小点改动
 * 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. 排序完成

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

// 定义链表的结构体
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) 授权分享 By CC BY-SA 4.0 Creative Commons License

关注微信公众号,获取新文章的推送!
qrcode

评论

还没有任何评论,你来说两句吧

发表评论

*

code