基数排序算法的实现与优化

基数排序过程

假设输入元素为:10,21,17,34,44,11,654,123,我们选择 10 作为基数进行基数排序。

首先,我们根据个位对元素进行分类:

0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9: 

依次收集元素,得到序列 10,21,11,123,24,44,654,17,再根据十位对元素分类:

0:
1: 10 11 17
2: 21 123
3: 34
4: 44
5: 654
6:
7:
8:
9: 

依次收集元素,得到序列 10,11,17,21,123,34,44,654,最后根据百位对元素分类:

0: 010 011 017 021 034 044
1: 123
2:
3:
4:
5:
6: 654
7:
8:
9: 

依次收集元素,得到最终的有序序列 10,11,17,21,34,44,123,654。

基数排序的基本实现(基于桶排序)

上面所给的例子中,我们用 0~9 这 10 个桶来存放元素。在这个基本实现中,每个桶都用一个链表来存储。而这 10 个桶的头结点,用一个一维数组来存放,便于根据下标来访问桶。

在元素的分配过程中,我们始终将元素插入到桶的末尾,而收集的时候只需依次从前往后收集,这样能确保先进先出(本质上就是队列)。如果通过遍历的方式找到链表的末尾,时间复杂度将会变得相当高。因此我们在桶这一结构中加入了一个尾指针 tail,用于指向桶的最后一个结点,这样就能在 O(1) 的时间内将元素插入到链表末尾。

改进后的结构如下:

具体代码

// -----------------------------------------------------
// Copyright (c) 2017, Wray Zheng. All Rights Reserved.
// Distributed under the BSD License.
// -----------------------------------------------------

#include <iostream>
#include <algorithm>
#include <ctime>
#define RADIX 1000

using namespace std;


/* 定义桶内的结点 */
struct node {
    int num;
    node* next;

    node(int num = 0, node* next = nullptr): num(num), next(next) {}
};


/* 定义每个桶的结构
 * head为链表的头结点
 * tail指向链表的尾结点 */
struct bucket {
    node head;
    node* tail;

    bucket() : tail(nullptr) {}
};


/* bitIndex 表示当前作为关键字的位
 * 根据 bitIndex 所对应的位将元素分配到桶中 */
void Distribute(int* data, int n, bucket* B, int bitIndex) {
    int divider = 1;
    for(int i = 0; i < bitIndex; i++) divider *= RADIX;

    int bit;
    node* p;
    for(int i = 0; i < n; i++) {
        bit = (data[i] / divider) % RADIX;
        //将元素分配到对应桶中
        //若尾指针为null,则插入到头结点后面
        //若尾指针不为null,则插入到尾结点后面
        p = B[bit].tail ? B[bit].tail : &B[bit].head;
        p->next = new node(data[i], p->next);
        B[bit].tail = p->next;
    }
}


/* 从各个桶中收集元素到数组中 */
void Collect(int* data, int n, bucket* B) {
    int index = 0;
    //扫描每一个桶
    for(int i = 0; i < RADIX; i++) {
        node* p = &B[i].head;
        //遍历收集桶内的所有元素
        while(p->next) {
            node* temp = p->next;
            data[index] = temp->num;
            index++;
            p->next = temp->next;
            delete temp;
        }
        B[i].tail = nullptr;
    }
}


/* 获取最大数字的位数 */
int GetMaxBits(int* data, int n) {
    int max = data[0];

    for(int i = 1; i < n; i++) {
        if(data[i] > max) max = data[i];
    }

    int t;
    for(t = 0; max != 0; t++) max /= RADIX;
    return t;
}


/* 基数排序 */
void radixSort(int* data, int n) {
    bucket* B = new bucket[RADIX];

    int maxBits= GetMaxBits(data, n);

    for(int i = 0; i < maxBits; i++) {
        //根据当前位将元素分配到各桶中
        Distribute(data, n, B, i);
        //从桶中依次收集各元素
        Collect(data, n, B);
    }

    delete[] B;
}


/* 随机数产生函数
 * 产生指定长度的随机序列,用于快速排序的测试 */
int* randomNums(int n) {
    int* array = new int[n];

    for (int i = 0; i < n; i++)
    {
        array[i] = i;
    }

    //将数组中元素的顺序打乱
    random_shuffle(array, array + n - 1);

    return array;
}


int main() {
    int n = 1000000;
    int* array = randomNums(n);

    int start = clock();
    radixSort(array, n);
    int time_used = clock() - start;

    cout << "Array Size: " << n << endl;
    cout << "Time Used: " << time_used << " ms" << endl;

    return 0;
}

假设有 n 个元素进行排序,最大元素有 d 位,基数为 r。理论上,该算法每趟排序的时间复杂度位 O(n+r),总的时间复杂度为 O(d(n+r))。当元素的位数较少时,该算法效率非常高。

但是理论的分析与具体实现时遇到的问题并不完全一致。因为真正实现时,还需要考虑分配和收集元素时,频繁的内存分配问题。上述实现需要在元素分配时为每个元素都申请内存,在收集时为每个元素释放内存,即共需要进行 nd 次内存申请和 nd 次内存释放。由于内存的申请和释放是相对复杂的操作,耗时较长,这种频繁的内存分配无疑严重降低了算法的效率。

要优化该算法的实现,有两种思路:

  • 一种是避免频繁地向系统申请和释放内存,可以采用内存池来实现;
  • 另一种是弃用链表这一数据结构,采用其它方式来完成元素的分配收集。

基数排序的高效实现(基于计数排序)

如上面提到的,优化该算法有两个方向,这里我们要探讨的是第二种思路,即弃用链表,采用其它方式来完成元素的分配收集。

链表实现与我们的直观感受相同:分配与收集元素,分配时将元素添加到对应的桶中,收集时从对应桶中删除元素。为了更高效地实现该算法,我们将牺牲这种直观,采用一种类似计数排序的方式来直接完成分类的过程。

假设基数为 r,我们创建一个大小为 r 的数组 count,count 数组的作用是统计当前位每个数字出现的次数。

每一趟排序的过程如下:

  • 将 count 数组的每个元素初始化为 0
  • 遍历所有元素,把每个元素的当前位 k 作为 count 数组的下标,count[k]++
  • 从 count 的第二项开始,count[i] = count[i] + count[i-1]
  • 从后往前遍历待排序数组,假设元素当前位为 k,则 count[k] 中存的是当前位小于等于 k 的元素个数,因此当前元素最终的位置应该是第 count[k] 个,下标j = count[k] - 1,故令 output[j] = 当前元素

具体代码

// -----------------------------------------------------
// Copyright (c) 2017, Wray Zheng. All Rights Reserved.
// Distributed under the BSD License.
// -----------------------------------------------------

#include <iostream>
#include <algorithm>
#include <ctime>
#define RADIX 1000

using namespace std;


/* 获取最大数字的位数 */
int GetMaxBits(int* data, int n) {
    int max = data[0];

    for(int i = 1; i < n; i++) {
        if(data[i] > max) max = data[i];
    }

    int t;
    for(t = 0; max != 0; t++) max /= RADIX;
    return t;
}


/* 基数排序中对每一位调用的计数排序 */
void countSort(int *data, int n, int bitIndex)
{
    int bit;
    int exp = 1;
    for(int i = 0; i < bitIndex; i++) exp *= RADIX;

    int* output = new int[n];
    int count[RADIX] = {0};

    //count数组用于记录每个基数出现的次数
    for (int i = 0; i < n; i++) {
        bit = (data[i] / exp) % RADIX;
        count[bit]++;
    }

    //将count数组转换成output数组中对应的下标
    for (int i = 1; i < RADIX; i++)
        count[i] += count[i-1];

    //将结果输出到 output 数组
    for (int i = n - 1; i >= 0; i--)
    {
        bit = (data[i] / exp) % RADIX;
        output[count[bit]-1] = data[i];
        count[bit]--;
    }

    //将结果复制回 data 数组
    for (int i = 0; i < n; i++)
        data[i] = output[i];

    delete[] output;
}


/* 基数排序 */
void radixSort(int* data, int n) {
    int maxBits = GetMaxBits(data, n);

    for(int i = 0; i < maxBits; i++) {
        countSort(data, n, i);
    }
}


/* 随机数产生函数
 * 产生指定长度的随机序列,用于快速排序的测试 */
int* randomNums(int n) {
    int* array = new int[n];

    for (int i = 0; i < n; i++)
    {
        array[i] = i;
    }

    //将数组中元素的顺序打乱
    random_shuffle(array, array + n - 1);

    return array;
}


int main() {
    int n = 1000000;
    int* array = randomNums(n);

    int start = clock();
    radixSort(array, n);
    int time_used = clock() - start;

    cout << "Array Size: " << n << endl;
    cout << "Time Used: " << time_used << " ms" << endl;

    return 0;
}

两种算法实际花费的时间比较:

可以看到,优化后的基数排序速度要远远快于优化前的速度,而且随着问题规模的增大,优化后花费时间的增长趋势要比优化前平缓得多。

相关文章

Loading Likes...

发表评论

电子邮件地址不会被公开。 必填项已用*标注