基数排序

首先来看两个经典引理:

引理1:给定n个d位数,每一个数位可以取k种可能的值。基数排序算法能以 θ(d(n+k))的时间正确地对这些数进行排序。

引理2:给定n个b位数和任何正整数r<=b,randix-sort能在 θ((b/r)(n+2^r))时间内正确地对这些数进行排序。

下面是基数排序的LSD法(最低位优先)程序实现:

#include<iostream>
#include<malloc.h>
using namespace std;

//返回数字的第d位
int getdigit(int num, int d)  
{   
    int temp = 1;
	for(int i=0; i<d-1; i++)
		temp = temp * 10;
    return (num/temp) % 10;  
}

//输出
void  printArr(int arr[], int n)
{
    for(int i=0; i<n; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

//基数排序算法
void radix_sort(int arr[], int begin, int end, int d)  
{    
    const int radix = 10;	//桶的个数   
    int count[radix], i, j; 

    int* bucket = (int*)malloc((end-begin+1)*sizeof(int));  //开辟桶空间   
   
    //从第1位到第d位,执行d次.按第k位数字大小,把所有的数据放到编号为0-9的桶中
    for(int k=1; k<=d; k++)  
    {  
        //初始化
        for(i=0; i<radix; i++)  
        {
            count[i] = 0;        
        }               
        //统计各个桶中元素个数
        for(i=begin; i<=end; i++) 
        {
           count[getdigit(arr[i], k)]++;
        }
        //count[i]表示第i个桶的右边界索引
        for(i=1; i<radix; i++) 
        {
            count[i] = count[i] + count[i-1];
        }
        //把数据依次装入桶
        for(i=end; i>=begin; i--)        //从右向左扫描,保证排序稳定性   
        { 
            j = getdigit(arr[i], k); //求出关键码的第k位的数字,例如:576的第3位是5   
            bucket[count[j]-1] = arr[i]; //放入对应的桶中,count[j]-1是第j个桶的右边界索引 
            --count[j];               //对应桶的装入数据索引减一  
        }

        //注意:此时count[i]为第i个桶左边界  
        
        //每次分配结束后,将所有桶中的数据从小到大重新收集,为下一次分配做准备
        for(i=begin,j=0; i<=end; i++, j++)  
        {
            arr[i] = bucket[j];    
        }        
    }     
    free(bucket);   
}  

int  main()
{
    int  num[16] = {73, 2, 931, 4213, 4455, 445314, 3428, 765, 539, 481,
					2542, 3, 476, 34237, 3412, 299};
    cout<<"原数据如下:"<<endl;
    printArr(num,16);
    radix_sort(num, 0, 15, 6);
    cout<<"排序后数据如下:"<<endl;
    printArr(num, 16);
	return 0;
}
下面简要讨论一下3中线性时间排序:

1. 基数排序是否比基于比较的排序算法(例如快速排序)更好呢?实际上哪一种排序算法更好取决于底层机器的实现特性(例如:快速排序通常比基数排序更为有效的利用硬件缓存),同时还取决于输入的数据;

2. 利用计数排序作为中间稳定排序的基数排序不是原地排序,而很多θ(nlgn)时间的比较排序算法则可以做到原地排序。因此,当内存容量比较宝贵时,像快速排序这样的原地排序算法可能更为可取;

3. 基数排序是在假设输入是由一个小范围内的整数构成,而桶排序则假设输入的元素均匀地分布在区间[0, 1)上。

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。