基数排序

  基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数; 基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。 取得数组中的最大数,并取得位数; arr为原始数组,从最低位开始取每个位组成radix数组; 对radix进行计数排序(利用计数排序适用于小范围数的特点);

动图演示

基数排序

C代码

#include<stdio.h>

#define Max_ 10      //数组个数
#define RADIX_10 10    //整形排序
#define KEYNUM_31 10     //关键字个数,这里为整形位数

// 打印结果
void Show(int  arr[], int n)
{
    int i;
    for ( i=0; i<n; i++ )
        printf("%d  ", arr[i]);
    printf("\n");
}

// 找到num的从低到高的第pos位的数据
int GetNumInPos(int num,int pos)
{
    int temp = 1;
    for (int i = 0; i < pos - 1; i++)
        temp *= 10;

    return (num / temp) % 10;
}


//基数排序  pDataArray 无序数组;iDataNum为无序数据个数
void RadixSort(int* pDataArray, int iDataNum)
{
    int *radixArrays[RADIX_10];    //分别为0~9的序列空间
    for (int i = 0; i < 10; i++)
    {
        radixArrays[i] = (int *)malloc(sizeof(int) * (iDataNum + 1));
        radixArrays[i][0] = 0;    //index为0处记录这组数据的个数
    }

    for (int pos = 1; pos <= KEYNUM_31; pos++)    //从个位开始到31位
    {
        for (int i = 0; i < iDataNum; i++)    //分配过程
        {
            int num = GetNumInPos(pDataArray[i], pos);
            int index = ++radixArrays[num][0];
            radixArrays[num][index] = pDataArray[i];
        }

        for (int i = 0, j =0; i < RADIX_10; i++)    //收集
        {
            for (int k = 1; k <= radixArrays[i][0]; k++)
                pDataArray[j++] = radixArrays[i][k];
            radixArrays[i][0] = 0;    //复位
        }
    }
}

int main()
{   //测试数据
    int arr_test[Max_] = { 8, 4, 2, 3, 5, 1, 6, 9, 0, 7 };
    //排序前数组序列
    Show( arr_test, Max_ );
    RadixSort( arr_test, Max_);
    //排序后数组序列
    Show( arr_test, Max_ );
    return 0;

}

分析:

  最佳情况:T(n) = O(n k) 最差情况:T(n) = O(n k) 平均情况:T(n) = O(n * k) 基数排序有两种方法: MSD 从高位开始进行排序 LSD 从低位开始进行排序 基数排序 vs 计数排序 vs 桶排序 这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异: 基数排序:根据键值的每位数字来分配桶 计数排序:每个桶只存储单一键值 桶排序:每个桶存储一定范围的数值

Copyright © zs0813.com 2020 all right reserved,powered by Gitbook该文件修订时间: 2020-10-09 10:41:12

results matching ""

    No results matching ""