基数排序(桶排序)C/C++

2018/04/17 22:06
阅读数 128
int GetNumInPos(int value,int pos);
int GetMaxPos(int a[],int n);
void RadixSort(int a[],int left,int right);

//获得整数value从低位到高位的第pos(1-->)位数值
int GetNumInPos(int value,int pos)
{
    int i;
    int temp = 1;
    for(i=0;i<pos-1;i++)
        value /= 10;
    return value%10;
}

//获取数组a[]中所有元素的最长位数
int GetMaxPos(int a[],int n)
{
    int i,npos;
    int maxpos = 0;        //记录最大位数
    int temp;
    for(i=0;i<n;i++){
        npos = 0;
        temp = a[i];
        while(temp!=0){
            npos++;
            temp /= 10;
        }
        if(maxpos<npos)
            maxpos = npos;
    }
    return maxpos;
}


//基数radix排序(桶t排序bucketsort)  (对a[left]到a[right]由小到大排序)
void RadixSort(int a[],int left,int right)
{
    int len = right-left+1;
    int i,j,pos,maxpos;
    int **bucket;        //[10][len+1]    bucket[i][0]用来记录编号为i(0-->9)桶的元素个数
    bucket = (int**)malloc(sizeof(int*)*10);
    for(i=0;i<10;i++)
        bucket[i] = (int*)malloc(sizeof(int)*(len+1));
    //初始化桶
    for(i=0;i<10;i++)
        bucket[i][0] = 0;
    //桶按照队列的方式存储收集数据
    maxpos = GetMaxPos(a,len);
    for(pos=1;pos<=maxpos;pos++){
        //开始存储一次
        for(i=0;i<len;i++){
            int num = GetNumInPos(a[i],pos);
            int count = bucket[num][0];
            count++;
            bucket[num][count] = a[i];       //放入对应序号的桶中
            bucket[num][0] = count;           //写回
        }
        //开始收集一次
        int cur = 0;
        for(i=0;i<=9;i++){
            for(j=1;j<=bucket[i][0];j++)
                    a[cur++] = bucket[i][j];
            bucket[i][0] = 0;
        }
    }
}

 

展开阅读全文
c++
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部